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-àireamhan sònraichte \(q\) agus \(r\) ann a tha a’ ciallachadh:
\[
a = bq + r, ≤ r < b] An seo, canar an co-mheas ri q agus canar an còrr ri r. Eisimpleir: ma tha a = 29 agus b = 5, an uairsin tha 29 = 5 + 4, agus mar sin tha q = 5 agus r = 4. Tha am bun-bheachd seo cudromach oir is e sin am bunait obrachadh modulo agus algairim Euclid gus GCD a lorg. 3. An Roinneadair Coitcheann as Motha (GCD) agus algairim Euclid Airson dà shlàn-àireamh _(a) agus _(b) (nach eil an dà chuid neoni), is e an roinneadair coitcheann as motha no GCD—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 GCD obrachadh a-mach. Leis an teòirim roinneadh, ma tha: [a = bq + r \] an uairsin: [\gcd(a,b) = _gcd(b,r) \] Tha am pròiseas seo air ath-aithris gus am bi an còrr _(r\) 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 àireamhachadh. 4. Measgachaidhean loidhneach agus dearbh-aithne Bézout Is e aon thoradh bunaiteach dearbh-aithne Bézout: 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 mhodulo inbhir a lorg (cudromach ann an crioptagrafaidheachd). 5. Prìomh àireamhan agus factaradh Is e prìomh àireamh slàn deimhinneach nas motha na 1 aig a bheil dìreach dà roinneadair deimhinneach: 1 agus i fhèin. Tha àireamhan leithid 2, 3, 5, 7, 11 nam prìomh àireamhan. Canar àireamhan co-dhèanta ri àireamhan nas motha na 1 ach nach eil nam prìomh àireamhan, mar eisimpleir 12, 21, 35. Is e am bun-bheachd as ainmeile Teoirim Bhunasach Àireamhachd: faodar gach slàn \(n>1\) a sgrìobhadh gu sònraichte (suas gu òrdugh) mar thoradh de phrìomh àireamhan:
\[
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.
