Metheo ea Khopolo-taba ea Lipalo
Khopolo-taba ea linomoro ke lekala la lipalo le ithutang litšobotsi tsa linomoro tse felletseng. Leha ho bonahala ho le bonolo—kaha linomoro tse felletseng li kenyelletsa feela …, -2, -1, 0, 1, 2, …—khopolo-taba ea linomoro e na le sebopeho se ruileng ka mokhoa o makatsang. Likhopolo tse ngata tsa bohlokoa lipalo tsa sejoale-joale, cryptography, le saense ea khomphutha li thehiloe mehopolong ea motheo ea khopolo-taba ea linomoro, joalo ka karohano, boqapi, le ho lumellana. Sengoloa sena se hlahloba metheo e meholo ea khopolo-taba ea linomoro: karohano le algorithm ea Euclid, lipalo tse kholo le factorization, modulo arithmetic, le lits'ebetso tse ling tse tsoetseng pele le litaelo.
1. Lipalo tse felletseng le mesebetsi ea motheo
Khopolo-taba ea linomoro hangata e sebetsa holim'a sete ea linomoro tse felletseng, tse bontšitsoeng ke ℤ. Mesebetsi ea motheo e sebelisoang ke ho eketsa, ho ntša le ho atisa. Ho fapana le linomoro tse utloahalang kapa tsa 'nete, karohano ka linomoro tse felletseng ha se kamehla e fellang ka palo e felletseng. Mona ke moo khopolo ea karohano e nang le masala e bang bohareng.
Kamano e le 'ngoe ea bohlokoa khopolo-taba ea linomoro ke karohano. Bakeng sa linomoro tse felletseng \(a\) le \(b\), re ngola \(a \mid b\) haeba ho na le palo e felletseng \(k\) e le hore \(b = ak\). Mohlala, \(3 \mid 12\) hobane \(12 = 3 \makhetlo a 4\), empa \(5 \nmid 12\) hobane ha ho na palo e felletseng \(k\) eo \(12 = 5k\) bakeng sa eona.
Karohano e na le litšobotsi tse latelang tsa motheo:
– Haeba \(a \mid b\) le \(a \mid c\), joale \(a \mid (b+c)\) le \(a \mid (bc)\).
– Haeba \(a \mid b\), joale bakeng sa kakaretso e 'ngoe le e 'ngoe ea \(k\), \(a \mid (bk)\).
– Haeba \(a \mid b\) le \(b \mid c\), joale \(a \mid c\).
Matlotlo ana a bonolo a sebetsa e le disebediswa tsa ho paka dipolelo tse ngata mabapi le di-integer.
2. Algorithm ea karohano
Teori ea karohano e re: bakeng sa palo e 'ngoe le e 'ngoe e felletseng \(a\) le palo e ntle \(b\), ho na le linomoro tse ikhethang \(q\) le \(r\) tse kang:
\[
a = bq + r,\quad 0 \le r < b \] Mona \(q\) e bitsoa quotient mme \(r\) e bitsoa masala. Mohlala: haeba \(a=29\) le \(b=5\), joale \(29 = 5\cdot 5 + 4\), kahoo \(q=5\) le \(r=4\). Khopolo ena e bohlokoa hobane ke motheo oa ts'ebetso ea modulo le algorithm ea Euclid bakeng sa ho fumana GCD. 3. Greatest Common Factor (GCD) le algorithm ea Euclid Bakeng sa linomoro tse peli \(a\) le \(b\) (eseng ka bobeli lefela), major common factor kapa GCD—e bontšang \(\gcd(a,b)\)—ke nomoro e kholo ka ho fetisisa e ntle e arolang ka bobeli. Tsela e sebetsang ka ho fetisisa ea ho bala GCD ke algorithm ea Euclid. Ho ya ka theorem ya karohano, haeba: \[ a = bq + r \] ebe: \[ \gcd(a,b) = \gcd(b,r) \] Ts'ebetso ena e phetwa ho fihlela karolo e setseng \(r\) e fetoha 0. Mohatong wa ho qetela, GCD ke karohano ya ho qetela e seng ya lefela. Mohlala o potlakileng: fumana \(\gcd(48,18)\). - \(48 = 18\cdot 2 + 12\) - \(18 = 12\cdot 1 + 6\) - \(12 = 6\cdot 2 + 0\) Ebe \(\gcd(48,18)=6\). Algorithm ya Euclid e bohlokwa haholo hobane e potlakile esita le bakeng sa dipalo tse kgolo, e leng se etsang hore e be molemo haholo ho dikhomphutheng. 4. Metswako e otlolohileng le boitsebiso ba Bézout E 'ngoe ea liphetho tsa motheo ke boitsebiso ba Bézout: bakeng sa linomoro tse felletseng \(a\) le \(b\) tseo ka bobeli e seng zero, ho na le linomoro tse felletseng \(x\) le \(y\) tse kang: \[ \gcd(a,b) = ax + by \] Sena se bolela hore GCD e ka ngoloa e le motsoako o otlolohileng oa \(a\) le \(b\). Boleng ba \(x\) le \(y\) bo ka fumanoa ka mokhoa o atolositsoeng oa Euclid algorithm. Boitsebiso ba Bézout ke ba bohlokoa ho rarolleng: - equation ea linear Diophantine \(ax+by=c\), - ho fumana modulo e fapaneng (ea bohlokoa ho cryptography).
\[
n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}
\]
Misalnya:
\[
360 = 2^3 \cdot 3^2 \cdot 5
\]
Ho ikhetha hona ha ho etsa hore di-factorization di be teng ke motheo wa dihlooho tse ngata tse tswetseng pele, ho kenyeletswa le RSA cryptography e itshetlehileng hodima bothata ba ho etsa di-factor dipalo tse kgolo.
6. Lipalopalo tse lumellanang le tsa modulo
Lipalo tsa Modulo li ithuta linomoro ho latela karolo e setseng ea karohano. Re re:
\[
a \equiv b \pmod{m}
\]
haeba \(m \mid (ab)\), ho bolela hore \(a\) le \(b\) di na le masalla a tshwanang ha di arolwa ka \(m\).
Mohlala: \(17 \equiv 5 \pmod{12}\) hobane \(17-5=12\) e aroloa ka 12. Modulong 12, 17 le 5 di nkuwa di lekana.
Ho lumellana ho na le litšobotsi tse tšoanang le tsa ts'ebetso e tloaelehileng:
– Haeba \(a \equiv b \pmod{m}\) le \(c \equiv d \pmod{m}\), joale
\(a+c \equiv b+d \pmod{m}\) le \(ac \equiv bd \pmod{m}\).
Lipalo tsa modulo li molemo haholo bakeng sa:
– fumana dipaterone tsa nako le nako,
– hlahloba dipalopalo,
– ho rala li-algorithms tse sebetsang hantle tsa k'homphieutha,
– le mongolo wa sejwalejwale.
7. Di-equation tse fapaneng tsa Modulo le tse lumellanang
Nomoro \(a\) e na le modulo e fapaneng \(m\) haeba ho na le nomoro \(x\) e kang:
\[
ax \equiv 1 \pmod{m}
\]
Phapang ena e teng haeba le haeba feela \(\gcd(a,m)=1\). Mohlala, 3 e na le modulo e fapaneng 7 hobane \(3\cdot 5=15\equiv 1 \pmod{7}\), kahoo phapang ea eona ke 5.
Khopolo ea modulo e fapaneng e etsa hore ho be bonolo ho rarolla li-equation tse kang:
\[
ax \equiv b \pmod{m}
\]
Haeba ho na le phapang ea \(a^{-1}\) e teng, tharollo e ka fumanoa ka ho atisa mahlakore ka bobeli:
\[
x \equiv a^{-1} b \pmod{m}
\]
8. Khopolo-taba e nyane ea Fermat le Khopolo-taba ea Euler
Liphetho tse peli tse tummeng khopolo-taba ea lipalo tsa mathomo ke:
1. Khopolo-taba e Nyenyane ea Fermat: haeba \(p\) e le prime 'me \(a\) e sa aroloe ke \(p\), joale:
\[
a^{p-1} \equiv 1 \pmod{p}
\]
2. Khopolo-taba ea Euler (kakaretso): haeba \(\gcd(a,m)=1\), joale:
\[
a^{\varphi(m)} \equiv 1 \pmod{m}
\]
moo \(\varphi(m)\) e leng mosebetsi wa Euler wa totien (palo ya dinomoro tse pakeng tsa 1 le \(m\) tse batlang di le ka pele ho \(m\)).
Likhopolo-taba tsena li tšehetsa mekhoa e fapaneng ea cryptographic le mekhoa ea ho bala ka potlako ea modulo.
9. Lisebelisoa le litaelo tse tsoetseng pele
Leha e qalile e le potso e bonolo mabapi le linomoro tse felletseng, khopolo-taba ea linomoro joale e se e fetohile tšimo e pharaletseng. Ts'ebeliso ea eona e kenyelletsa:
– Cryptography: RSA, Diffie–Hellman, le di-curve tse elliptic di sebedisa thepa ya prime, congruence, le modulo inverse.
– Saense ea khomphutha: ho hashing, lijenereithara tsa linomoro tse sa reroang, le li-algorithms tsa ho bala palo e kholo.
– Khopolo-taba ea ho kopanya le ho ngola khoutu: ho haha likhoutu tsa ho lokisa liphoso le meaho e arohaneng.
Lihlooho tse tsoetseng pele tse atisang ho ithutoa ka mor'a metheo ena li kenyelletsa li-equation tsa Diophantine tse seng tsa mola, masala a quadratic, khopolo-taba ea linomoro tsa algebraic, le kabo ea linomoro tsa prime.
Ho koala
Metheo ea khopolo-taba ea linomoro e itšetlehile ka likhopolo tsa karohano, GCF, linomoro tsa mantlha, le congruence. Ho tloha ho algorithm ea Euclid ho ea ho modulo arithmetic, mohopolo o mong le o mong o theha motheo oa ho utloisisa sebopeho sa linomoro tse felletseng 'me o bula tsela bakeng sa lits'ebetso tsa lefats'e la nnete, haholo-holo mehleng ea dijithale. Ho tseba likhopolo tsena tsa motheo ho fana ka lisebelisoa tse matla tsa ho sekaseka mathata a lipalo a arohaneng le ho teba ka lihlooho tse tebileng khopolo-taba ea linomoro ea sejoale-joale.
