Bun-bheachdan Teòiridh Àireamhan
’S e meur de mhatamataig a th’ ann an teòiridh àireamhan a bhios a’ sgrùdadh feartan àireamhan slàn. Ged a tha e coltach gu bheil e sìmplidh – leis gu bheil na h-àireamhan slàn dìreach a’ toirt a-steach …, -2, -1, 0, 1, 2, … – tha structar air leth beairteach aig teòiridh àireamhan. Tha mòran bhun-bheachdan cudromach ann am matamataig an latha an-diugh, crioptagrafaidheachd, agus saidheans coimpiutaireachd stèidhichte ann am beachdan bunaiteach teòiridh àireamhan, leithid roinneadh, prìomhachd, agus co-chòrdadh. Tha an t-artaigil seo a’ dèanamh ath-sgrùdadh air prìomh bhunait teòiridh àireamhan: roinneadh agus algairim Euclid, prìomh àireamhan agus factaradh, àireamhachd modulo, agus cuid de thagraidhean agus stiùiridhean adhartach.
1. Àireamhan slàn agus obrachaidhean bunaiteach
Mar as trice, bidh teòiridh àireamhan ag obair air an t-seata de shlàna-àireamhan, air an comharrachadh le ℤ. Is e cur-ris, toirt-air-falbh, agus iomadachadh na prìomh obrachaidhean a thathar a’ cleachdadh. Eu-coltach ri àireamhan reusanta no fìor, chan eil roinneadh le slàna-àireamhan an-còmhnaidh a’ leantainn gu slàn-àireamh. Seo far a bheil bun-bheachd roinneadh leis a’ chòrr a’ tighinn gu bhith na phrìomh rud.
Is e roinneadh aon dàimh chudromach ann an teòiridh àireamhan. Airson slàn-àireamhan _(a) agus _(b)_, sgrìobhaidh sinn _(a \mid b)_ ma tha slàn-àireamh _(k) ann a tha _(b = ak)_. Mar eisimpleir, _(3 \mid 12)_ leis gu bheil _(12 = 3 \times 4)_, ach _(5 \mid 12)_ leis nach eil slàn-àireamh _(k) ann airson _(12 = 5k)_.
Tha na feartan bunaiteach a leanas aig roinneadh:
– Ma tha ∫(a) agus ∫(c), an uairsin ∫(b+c) agus ∫(bc)).
– Ma tha \(a \mid b\), an uairsin airson gach slàn-àireamh \(k\), tha \(a \mid (bk)\).
– Ma tha \(a \mid b\) agus \(b \mid c\), an uairsin \(a \mid c\).
Tha na feartan sìmplidh seo nan innealan airson mòran aithrisean mu shlàna-àireamhan a dhearbhadh.
2. Algairim roinneadh
Tha teòirim an roinneadh ag ràdh: airson gach slàn-àireamh \(a\) agus slàn-àireamh dheimhinneach \(b\), tha slàn-àireamh sònraichte \(q\) agus \(r\) ann a tha a’ ciallachadh:
\[
a = bq + r,\quad 0 \le r < b \] An seo, canar \(q\) ris an co-roinn agus canar \(r\) ris an còrr. Mar eisimpleir: ma tha \(a\=29\) agus \(b\=5\), an uairsin \(29 = 5\cdot 5 + 4\), agus mar sin \(q\=5\) agus \(r\=4\). Tha a’ bhun-bheachd seo cudromach oir is e seo bunait an obrachaidh modulo agus algairim Euclid airson an Fèill Choitcheann as Motha (FCC) a lorg. 3. Am Factar Coitcheann as Motha (FCC) agus algairim Euclid Airson dà shlàn-àireamh \(a\) agus \(b\) (chan eil an dà chuid neoni), is e am factar cumanta as motha no FCC—air a chomharrachadh le \(\gcd(a,b)\)—an slàn-àireamh dheimhinneach as motha a roinneas an dà chuid. Is e algairim Euclid an dòigh as èifeachdaiche air FCC obrachadh a-mach. A rèir teòirim an roinneadh, ma tha: [a = bq + r] an uairsin: [gcd(a,b) = gcd(b,r)] Thèid am pròiseas seo ath-aithris gus am bi an còrr r co-ionann ri 0. Anns a’ cheum mu dheireadh, is e an GCD an roinneadair mu dheireadh nach eil na neoni. Eisimpleir luath: lorg (gcd(48,18)). - (48 = 18² + 12) - (18 = 12¹ + 6) - (12 = 6² + 0) An uairsin (gcd(48,18)=6). Tha algairim Euclid glè chudromach oir tha e luath eadhon airson àireamhan mòra, ga dhèanamh glè fheumail ann an coimpiutaireachd. 4. Measgachaidhean loidhneach agus dearbh-aithne Bézout Is e dearbh-aithne Bézout aon de na toraidhean bunaiteach: airson slàn-àireamhan \(a\) agus \(b\) nach eil le chèile neoni, tha slàn-àireamhan \(x\) agus \(y\) ann a leithid: \[ \gcd(a,b) = ax + by \] Tha seo a’ ciallachadh gun gabh an GCD a sgrìobhadh mar mheasgachadh loidhneach de \(a\) agus \(b\). Gheibhear luachan \(x\) agus \(y\) leis an algairim Euclid leudaichte. Tha dearbh-aithne Bézout deatamach ann a bhith a’ fuasgladh: - co-aontar Diophantine loidhneach \(ax+by=c\), - a’ lorg an modulo inbhir (cudromach ann an crioptagrafaidheachd).
\[
n = p_1^{α1} p_2^{α2} ⋅ p_k^{αk}
\]
Misalnya:
\[
360 = 2^3 ⋅ 3^2 ⋅ 5
\]
’S e an rud sònraichte seo a tha an lùib factaraidh bunait mòran chuspairean adhartach, a’ gabhail a-steach crioptagrafaireachd RSA a tha an urra ri cho duilich ’s a tha e àireamhan mòra a fhactarachadh.
6. Co-chòrdadh agus àireamhachd modulo
Bidh àireamhachd modulo a’ sgrùdadh àireamhan stèidhichte air a’ chòrr de roinneadh. Canaidh sinn:
\[
a \equiv b \pm{m}
\]
ma tha \(m \mid(ab)\), tha sin a’ ciallachadh gu bheil an aon fhuigheall aig \(a\) agus \(b\) nuair a thèid an roinn le \(m\).
Eisimpleir: 17 = 5 mod 12 oir tha 17-5 = 12 ri roinn le 12. Ann am modulo 12, thathas a’ meas gu bheil 17 agus 5 co-ionann.
Tha na h-aon fheartan aig co-chòrdadh ri obrachaidhean àbhaisteach:
– Ma tha (a = b = m) agus (c = d = m), an uairsin
(a+c \equiv b\pmod{m}) agus (ac \equiv bd \pmod{m}).
Tha àireamhachd modulo glè fheumail airson:
– pàtrain cunbhalach a dhearbhadh,
- thoir sùil air iomadan,
– dealbhadh algairimean coimpiutaireachd èifeachdach,
– agus crioptagrafaireachd ùr-nodha.
7. Co-aontaran modulo inbhir agus co-chòrdalachd
Tha modulo inbhireach m aig àireamh \(a\) ma tha àireamh \(x\) ann a tha:
\[
ax \equiv 1 \pmod{m}
\]
Tha an tionndadh seo ann ma tha agus dìreach ma tha \(\gcd(a,m)=1\). Mar eisimpleir, tha modulo tionndaidh 7 aig 3 oir \(3\cdot 5=15\equiv 1 \pmod{7}\), agus mar sin tha an tionndadh aige 5.
Tha bun-bheachd modulo inverse ga dhèanamh nas fhasa co-aontaran leithid: fhuasgladh:
\[
ax \equiv b \pmod{m}
\]
Ma tha an taobh eile de \(a^{-1}\) ann, gheibhear am fuasgladh le bhith ag iomadachadh an dà thaobh:
\[
x \equiv a^{-1} b \pmod{m}
\]
8. Teoirim bheag Fermat agus teòirim Euler
Is iad seo dà thoradh ainmeil ann an teòiridh àireamhachd bhunasach:
1. Teoirim Bheag Fermat: ma tha \(p\) na phrìomh àireamh agus nach gabh \(a\) a roinn le \(p\), an uairsin:
\[
a^{p-1} \equiv 1 \pmod{p}
\]
2. Teoirim Euler (coitcheannachadh): ma tha \(\gcd(a,m)=1\), an uairsin:
\[
a^{\varphi(m)} \equiv 1 \pmod{m}
\]
far a bheil \(\varphi(m)\) na ghnìomh totien Euler (an àireamh de dh'àireamhan eadar 1 agus \(m\) a tha an coimeas ri \(m\)).
Tha na teòirimean seo aig bonn diofar dhòighean cripteagrafach agus dhòighean-obrach coimpiutaireachd modulo luath.
9. Aplacaidean agus stiùiridhean adhartach
Ged a thòisich e mar cheist shìmplidh mu àireamhan slàn, tha teòiridh àireamhan a-nis air fàs gu bhith na raon farsaing. Am measg nan cleachdaidhean aige tha:
– Crioptagrafaireachd: Bidh RSA, Diffie–Hellman, agus lùban eliptigeach a’ cleachdadh feartan prìomh, co-chòrdalachd, agus modulo inverse.
– Saidheans coimpiutaireachd: hashing, gineadairean àireamhan air thuaiream, agus algairim coimpiutaireachd àireamhan mòra.
– Teòiridh cho-mheasgaichte agus còdaidh: a’ togail chòdan ceartachaidh-mhearachd agus structaran fa leth.
Am measg nan cuspairean adhartach a thèid a sgrùdadh gu tric às dèidh nam bunaitean seo tha co-aontaran Diophantine neo-loidhneach, fuigheallan ceàrnagach, teòiridh àireamhan ailseabra, agus sgaoileadh phrìomh àireamhan.
Penutup
Tha bunaitean teòiridh àireamhan stèidhichte air bun-bheachdan roinneadh, GCF, prìomh àireamhan, agus co-chòrdadh. Bho algairim Euclid gu àireamhachd modulo, tha gach beachd a’ cruthachadh a’ bhunait airson tuigse fhaighinn air structar slàn-àireamhan agus a’ rèiteachadh na slighe airson tagraidhean san t-saoghal fhìor, gu sònraichte san aois dhidseatach. Le bhith a’ maighstireachd nam bun-bheachdan sin tha innealan cumhachdach ann airson a bhith a’ sgrùdadh dhuilgheadasan matamataigs fa leth agus a’ sgrùdadh chuspairean nas doimhne ann an teòiridh àireamhan an latha an-diugh.
