Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Diskr´etn´ı matematika – 1. t´yden Element´arn´ı teorie ˇc´ısel – dˇelitelnost Jan Slov´ak Masarykova univerzita Fakulta informatiky
jaro 2015
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Obsah pˇredn´aˇsky
1
Probl´emy teorie ˇc´ısel
2
Dˇelitelnost
3
Spoleˇcn´ı dˇelitel´e a spoleˇcn´e n´asobky Faktorizace
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Doporuˇcen´e zdroje Jan Slov´ak, Martin Pan´ak, Michal Bulant Matematika drsnˇ e a sviˇ znˇ e, e-text na www.math.muni.cz/Matematika_drsne_svizne.
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Doporuˇcen´e zdroje Jan Slov´ak, Martin Pan´ak, Michal Bulant Matematika drsnˇ e a sviˇ znˇ e, e-text na www.math.muni.cz/Matematika_drsne_svizne. Michal Bulant, v´yukov´y text k pˇredn´aˇsce Element´ arn´ı teorie ˇ c´ısel, http://is.muni.cz/el/1431/podzim2012/M6520/ um/main-print.pdf ˇ sa, Metody ˇreˇsen´ı Jiˇr´ı Herman, Radan Kuˇcera, Jarom´ır Simˇ matematick´ ych u ´loh. MU Brno, 2001. William Stein, Elementary Number Theory: Primes, Congruences, and Secrets, Springer, 2008. Dostupn´e na http://wstein.org/ent/ent.pdf Radan Kuˇcera, v´yukov´y text k pˇredn´aˇsce Algoritmy teorie ˇ c´ısel, http://www.math.muni.cz/~kucera/texty/ATC10.pdf
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Pl´an pˇredn´aaky
1
Probl´emy teorie ˇc´ısel
2
Dˇelitelnost
3
Spoleˇcn´ı dˇelitel´e a spoleˇcn´e n´asobky Faktorizace
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Pˇrirozen´a a cel´a ˇc´ısla jsou nejjednoduˇsˇs´ı matematickou strukturou, zkoum´an´ı jejich vlastnost´ı vˇsak postavilo pˇred generace matematik˚ u celou ˇradu velice obt´ıˇzn´ych probl´em˚ u. ˇ Casto jsou to probl´emy, kter´e je moˇzno snadno formulovat, pˇresto vˇsak dodnes nezn´ame jejich ˇreˇsen´ı. V nˇekolika pˇredn´aˇsk´ach se ted’ budeme zab´yvat u ´lohami o cel´ych ˇc´ıslech. Pˇrev´aˇznˇe v nich p˚ ujde o dˇelitelnost cel´ych ˇc´ısel, popˇr´ıpadˇe o ˇreˇsen´ı rovnic v oboru cel´ych nebo pˇrirozen´ych ˇc´ısel.
God made integers, all else is the work of man. (L. Kronecker)
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Pˇr´ıklady probl´em˚ u teorie ˇc´ısel
probl´em prvoˇc´ıseln´ych dvojˇcat – rozhodnout, zda existuje nekoneˇcnˇe mnoho prvoˇc´ısel p takov´ych, ˇze i p + 2 je prvoˇc´ıslo,
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Pˇr´ıklady probl´em˚ u teorie ˇc´ısel
probl´em prvoˇc´ıseln´ych dvojˇcat – rozhodnout, zda existuje nekoneˇcnˇe mnoho prvoˇc´ısel p takov´ych, ˇze i p + 2 je prvoˇc´ıslo, probl´em existence lich´eho dokonal´eho ˇc´ısla – tj. ˇc´ısla jehoˇz souˇcet dˇelitel˚ u je roven dvojn´asobku tohoto ˇc´ısla
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Pˇr´ıklady probl´em˚ u teorie ˇc´ısel
probl´em prvoˇc´ıseln´ych dvojˇcat – rozhodnout, zda existuje nekoneˇcnˇe mnoho prvoˇc´ısel p takov´ych, ˇze i p + 2 je prvoˇc´ıslo, probl´em existence lich´eho dokonal´eho ˇc´ısla – tj. ˇc´ısla jehoˇz souˇcet dˇelitel˚ u je roven dvojn´asobku tohoto ˇc´ısla Goldbachova hypot´eza (rozhodnout, zda kaˇzd´e sud´e ˇc´ıslo vˇetˇs´ı neˇz 2 je moˇzno ps´at jako souˇcet dvou prvoˇc´ısel),
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Pˇr´ıklady probl´em˚ u teorie ˇc´ısel
probl´em prvoˇc´ıseln´ych dvojˇcat – rozhodnout, zda existuje nekoneˇcnˇe mnoho prvoˇc´ısel p takov´ych, ˇze i p + 2 je prvoˇc´ıslo, probl´em existence lich´eho dokonal´eho ˇc´ısla – tj. ˇc´ısla jehoˇz souˇcet dˇelitel˚ u je roven dvojn´asobku tohoto ˇc´ısla Goldbachova hypot´eza (rozhodnout, zda kaˇzd´e sud´e ˇc´ıslo vˇetˇs´ı neˇz 2 je moˇzno ps´at jako souˇcet dvou prvoˇc´ısel), velk´a Fermatova vˇeta (Fermat’s Last Theorem) – rozhodnout, zda existuj´ı pˇrirozen´a ˇc´ısla n, x, y , z tak, ˇze n > 2 a plat´ı x n + y n = z n ; Pierre de Fermat jej formuloval cca 1637, vyˇreˇsil Andrew Wiles v roce 1995.
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
diofantick´e rovnice V kouzeln´em mˇeˇsci m´ame neomezen´e mnoˇzstv´ı dvoukorun a pˇetikorun. Jak´e ˇc´astky m˚ uˇzeme zaplatit tak, aby nebylo potˇreba vracet?
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
diofantick´e rovnice V kouzeln´em mˇeˇsci m´ame neomezen´e mnoˇzstv´ı dvoukorun a pˇetikorun. Jak´e ˇc´astky m˚ uˇzeme zaplatit tak, aby nebylo potˇreba vracet? Pt´ame se tedy, pro kter´a pˇrirozen´a ˇc´ısla n existuj´ı pˇrirozen´a k, ` tak, aby 2k + 5` = n. Asi se d´a vcelku snadno uvˇeˇrit, ˇze libovolnou vyˇsˇs´ı ˇc´astku takto zaplat´ıme, po pravdˇe jakoukoliv ˇcastku s v´yjimkou 1 Kˇc a 3 Kˇc.
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
diofantick´e rovnice V kouzeln´em mˇeˇsci m´ame neomezen´e mnoˇzstv´ı dvoukorun a pˇetikorun. Jak´e ˇc´astky m˚ uˇzeme zaplatit tak, aby nebylo potˇreba vracet? Pt´ame se tedy, pro kter´a pˇrirozen´a ˇc´ısla n existuj´ı pˇrirozen´a k, ` tak, aby 2k + 5` = n. Asi se d´a vcelku snadno uvˇeˇrit, ˇze libovolnou vyˇsˇs´ı ˇc´astku takto zaplat´ıme, po pravdˇe jakoukoliv ˇcastku s v´yjimkou 1 Kˇc a 3 Kˇc. S vracen´ım pak zvl´adneme zaplatit libovolnou ˇc´astku, tj. kaˇzd´e n lze vyj´adˇrit jako 2k + 5` = n pro nˇejak´a cel´a k, `. Um´ıme to pro jak´ekoliv hodnoty minc´ı? Jak by to dopadlo tˇreba pro 7k + 11` = n? A jak pro 2k + 4` = n?
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Pl´an pˇredn´aaky
1
Probl´emy teorie ˇc´ısel
2
Dˇelitelnost
3
Spoleˇcn´ı dˇelitel´e a spoleˇcn´e n´asobky Faktorizace
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Definice ˇ Rekneme, ˇze cel´e ˇc´ıslo a dˇel´ı cel´e ˇc´ıslo b (neboli ˇc´ıslo b je dˇeliteln´e ˇc´ıslem a, t´eˇz b je n´asobek a), pr´avˇe kdyˇz existuje cel´e ˇc´ıslo c tak, ˇze plat´ı a · c = b. P´ıˇseme pak a | b.
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Definice ˇ Rekneme, ˇze cel´e ˇc´ıslo a dˇel´ı cel´e ˇc´ıslo b (neboli ˇc´ıslo b je dˇeliteln´e ˇc´ıslem a, t´eˇz b je n´asobek a), pr´avˇe kdyˇz existuje cel´e ˇc´ıslo c tak, ˇze plat´ı a · c = b. P´ıˇseme pak a | b. ˇ ıslo nula je Pˇr´ımo z definice plyne nˇekolik jednoduch´ych tvrzen´ı : C´ dˇeliteln´e kaˇzd´ym cel´ym ˇc´ıslem; jedin´e cel´e ˇc´ıslo, kter´e je dˇeliteln´e nulou, je nula; pro libovoln´e ˇc´ıslo a plat´ı a | a;
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Definice ˇ Rekneme, ˇze cel´e ˇc´ıslo a dˇel´ı cel´e ˇc´ıslo b (neboli ˇc´ıslo b je dˇeliteln´e ˇc´ıslem a, t´eˇz b je n´asobek a), pr´avˇe kdyˇz existuje cel´e ˇc´ıslo c tak, ˇze plat´ı a · c = b. P´ıˇseme pak a | b. ˇ ıslo nula je Pˇr´ımo z definice plyne nˇekolik jednoduch´ych tvrzen´ı : C´ dˇeliteln´e kaˇzd´ym cel´ym ˇc´ıslem; jedin´e cel´e ˇc´ıslo, kter´e je dˇeliteln´e nulou, je nula; pro libovoln´e ˇc´ıslo a plat´ı a | a; pro libovoln´a ˇc´ısla a, b, c plat´ı tyto ˇctyˇri implikace:
a | b ∧ b | c =⇒ a | c a | b ∧ a | c =⇒ a | b + c ∧ a | b − c c 6= 0 =⇒ (a | b ⇐⇒ ac | bc) a | b ∧ b > 0 =⇒ a ≤ b
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Pˇr´ıklad Zjistˇete, pro kter´a pˇrirozen´a ˇc´ısla n je ˇc´ıslo n2 + 1 dˇeliteln´e ˇc´ıslem n + 1.
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Pˇr´ıklad Zjistˇete, pro kter´a pˇrirozen´a ˇc´ısla n je ˇc´ıslo n2 + 1 dˇeliteln´e ˇc´ıslem n + 1. ˇ Reaen´ ı Plat´ı n2 − 1 = (n + 1)(n − 1), a tedy ˇc´ıslo n + 1 dˇel´ı ˇc´ıslo n2 − 1. Pˇredpokl´adejme, ˇze n + 1 dˇel´ı i ˇc´ıslo n2 + 1. Pak ovˇsem mus´ı dˇelit i rozd´ıl (n2 + 1) − (n2 − 1) = 2. Protoˇze n ∈ N, plat´ı n + 1 ≥ 2, a tedy z n + 1 | 2 plyne n + 1 = 2, proto n = 1. Uvedenou vlastnost m´a tedy jedin´e pˇrirozen´e ˇc´ıslo 1.
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Dˇelen´ı se zbytkem Vˇeta (o dˇelen´ı cel´ych ˇc´ısel se zbytkem) Pro libovolnˇe zvolen´a ˇc´ısla a ∈ Z, m ∈ N existuj´ı jednoznaˇcnˇe urˇcen´a ˇc´ısla q ∈ Z, r ∈ {0, 1, . . . , m − 1} tak, ˇze a = qm + r .
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Dˇelen´ı se zbytkem Vˇeta (o dˇelen´ı cel´ych ˇc´ısel se zbytkem) Pro libovolnˇe zvolen´a ˇc´ısla a ∈ Z, m ∈ N existuj´ı jednoznaˇcnˇe urˇcen´a ˇc´ısla q ∈ Z, r ∈ {0, 1, . . . , m − 1} tak, ˇze a = qm + r . D˚ ukaz. Dokaˇzme nejprve existenci ˇc´ısel q, r . Pˇredpokl´adejme, ˇze pˇrirozen´e ˇc´ıslo m je d´ano pevnˇe a dokaˇzme u ´lohu pro libovoln´e a ∈ Z. Nejprve budeme pˇredpokl´adat, ˇze a ∈ N0 a existenci ˇc´ısel q, r dok´aˇzeme indukc´ı:
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Dˇelen´ı se zbytkem Vˇeta (o dˇelen´ı cel´ych ˇc´ısel se zbytkem) Pro libovolnˇe zvolen´a ˇc´ısla a ∈ Z, m ∈ N existuj´ı jednoznaˇcnˇe urˇcen´a ˇc´ısla q ∈ Z, r ∈ {0, 1, . . . , m − 1} tak, ˇze a = qm + r . D˚ ukaz. Dokaˇzme nejprve existenci ˇc´ısel q, r . Pˇredpokl´adejme, ˇze pˇrirozen´e ˇc´ıslo m je d´ano pevnˇe a dokaˇzme u ´lohu pro libovoln´e a ∈ Z. Nejprve budeme pˇredpokl´adat, ˇze a ∈ N0 a existenci ˇc´ısel q, r dok´aˇzeme indukc´ı: Je-li 0 ≤ a < m, staˇc´ı volit q = 0, r = a a rovnost a = qm + r plat´ı.
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Dˇelen´ı se zbytkem Vˇeta (o dˇelen´ı cel´ych ˇc´ısel se zbytkem) Pro libovolnˇe zvolen´a ˇc´ısla a ∈ Z, m ∈ N existuj´ı jednoznaˇcnˇe urˇcen´a ˇc´ısla q ∈ Z, r ∈ {0, 1, . . . , m − 1} tak, ˇze a = qm + r . D˚ ukaz. Dokaˇzme nejprve existenci ˇc´ısel q, r . Pˇredpokl´adejme, ˇze pˇrirozen´e ˇc´ıslo m je d´ano pevnˇe a dokaˇzme u ´lohu pro libovoln´e a ∈ Z. Nejprve budeme pˇredpokl´adat, ˇze a ∈ N0 a existenci ˇc´ısel q, r dok´aˇzeme indukc´ı: Je-li 0 ≤ a < m, staˇc´ı volit q = 0, r = a a rovnost a = qm + r plat´ı. Pˇredpokl´adejme nyn´ı, ˇze a ≥ m a ˇze jsme existenci ˇc´ısel q, r dok´azali pro vˇsechna a0 ∈ {0, 1, 2, . . . , a − 1}. Speci´alnˇe pro a0 = a − m tedy existuj´ı q 0 , r 0 tak, ˇze a0 = q 0 m + r 0 a pˇritom r 0 ∈ {0, 1, . . . , m − 1}. Zvol´ıme-li q = q 0 + 1, r = r 0 , plat´ı a = a0 + m = (q 0 + 1)m + r 0 = qm + r , coˇz jsme chtˇeli dok´azat.
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Dokonˇcen´ı d˚ ukazu. Existenci ˇc´ısel q, r jsme tedy dok´azali pro libovoln´e a ≥ 0. Je-li naopak a < 0, pak ke kladn´emu ˇc´ıslu −a podle v´yˇse dok´azan´eho existuj´ı q 0 ∈ Z, r 0 ∈ {0, 1, . . . , m − 1} tak, ˇze −a = q 0 m + r 0 , tedy a = −q 0 m − r 0 . Je-li r 0 = 0, poloˇz´ıme r = 0, q = −q 0 ; je-li r > 0, poloˇz´ıme r = m − r 0 , q = −q 0 − 1. V obou pˇr´ıpadech a = q · m + r , a tedy ˇc´ısla q, r s poˇzadovan´ymi vlastnostmi existuj´ı pro kaˇzd´e a ∈ Z, m ∈ N.
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Dokonˇcen´ı d˚ ukazu. Existenci ˇc´ısel q, r jsme tedy dok´azali pro libovoln´e a ≥ 0. Je-li naopak a < 0, pak ke kladn´emu ˇc´ıslu −a podle v´yˇse dok´azan´eho existuj´ı q 0 ∈ Z, r 0 ∈ {0, 1, . . . , m − 1} tak, ˇze −a = q 0 m + r 0 , tedy a = −q 0 m − r 0 . Je-li r 0 = 0, poloˇz´ıme r = 0, q = −q 0 ; je-li r > 0, poloˇz´ıme r = m − r 0 , q = −q 0 − 1. V obou pˇr´ıpadech a = q · m + r , a tedy ˇc´ısla q, r s poˇzadovan´ymi vlastnostmi existuj´ı pro kaˇzd´e a ∈ Z, m ∈ N. Nyn´ı dok´aˇzeme jednoznaˇcnost. Pˇredpokl´adejme, ˇze pro nˇekter´a ˇc´ısla q1 , q2 ∈ Z; r1 , r2 ∈ {0, 1, . . . , m − 1} plat´ı ´ a = q1 m + r1 = q2 m + r2 . Upravou dostaneme r1 − r2 = (q2 − q1 )m, a tedy m | r1 − r2 . Ovˇsem z 0 ≤ r1 < m, 0 ≤ r2 < m plyne −m < r1 − r2 < m, odkud dost´av´ame r1 − r2 = 0. Pak ale i (q2 − q1 )m = 0, a proto q1 = q2 , r1 = r2 . ˇ ısla q, r jsou tedy urˇcena jednoznaˇcnˇe. C´
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
ˇ ıslo q, resp. r z vˇety se naz´yv´a (ne´ C´ upln´y) pod´ıl, resp. zbytek pˇri dˇelen´ı ˇc´ısla a ˇc´ıslem m se zbytkem. Vhodnost obou n´azv˚ u je zˇrejm´a, pˇrep´ıˇseme-li rovnost a = mq + r do tvaru a r r = q + , pˇritom 0 ≤ < 1. m m m
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
ˇ ıslo q, resp. r z vˇety se naz´yv´a (ne´ C´ upln´y) pod´ıl, resp. zbytek pˇri dˇelen´ı ˇc´ısla a ˇc´ıslem m se zbytkem. Vhodnost obou n´azv˚ u je zˇrejm´a, pˇrep´ıˇseme-li rovnost a = mq + r do tvaru a r r = q + , pˇritom 0 ≤ < 1. m m m Pˇr´ıklad Dokaˇzte, ˇze jsou-li zbytky po dˇelen´ı ˇc´ısel a, b ∈ Z ˇc´ıslem m ∈ N jedna, je jedna i zbytek po dˇelen´ı ˇc´ısla ab ˇc´ıslem m.
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
ˇ ıslo q, resp. r z vˇety se naz´yv´a (ne´ C´ upln´y) pod´ıl, resp. zbytek pˇri dˇelen´ı ˇc´ısla a ˇc´ıslem m se zbytkem. Vhodnost obou n´azv˚ u je zˇrejm´a, pˇrep´ıˇseme-li rovnost a = mq + r do tvaru a r r = q + , pˇritom 0 ≤ < 1. m m m Pˇr´ıklad Dokaˇzte, ˇze jsou-li zbytky po dˇelen´ı ˇc´ısel a, b ∈ Z ˇc´ıslem m ∈ N jedna, je jedna i zbytek po dˇelen´ı ˇc´ısla ab ˇc´ıslem m. ˇ Reaen´ ı Podle Vˇety o dˇelen´ı se zbytkem existuj´ı s, t ∈ Z tak, ˇze a = sm + 1, b = tm + 1. Vyn´asoben´ım dostaneme ab = (sm + 1)(tm + 1) = (stm + s + t)m + 1 = qm + r , kde q = stm + s + t, r = 1, kter´e je podle t´eˇze vˇety jednoznaˇcn´e, a tedy zbytek po dˇelen´ı ˇc´ısla ab ˇc´ıslem m je jedna.
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Pl´an pˇredn´aaky
1
Probl´emy teorie ˇc´ısel
2
Dˇelitelnost
3
Spoleˇcn´ı dˇelitel´e a spoleˇcn´e n´asobky Faktorizace
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Nejvˇetˇs´ı spoleˇcn´y dˇelitel (gcd) Jedn´ım z nejd˚ uleˇzitˇejˇs´ıch n´astroj˚ u v´ypoˇcetn´ı teorie ˇc´ısel je v´ypoˇcet nejvˇetˇs´ıho spoleˇcn´eho dˇelitele. Protoˇze jde, jak si uk´aˇzeme, o relativnˇe rychlou proceduru, je i v modern´ıch algoritmech velmi ˇcasto vyuˇz´ıv´ana.
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Nejvˇetˇs´ı spoleˇcn´y dˇelitel (gcd) Jedn´ım z nejd˚ uleˇzitˇejˇs´ıch n´astroj˚ u v´ypoˇcetn´ı teorie ˇc´ısel je v´ypoˇcet nejvˇetˇs´ıho spoleˇcn´eho dˇelitele. Protoˇze jde, jak si uk´aˇzeme, o relativnˇe rychlou proceduru, je i v modern´ıch algoritmech velmi ˇcasto vyuˇz´ıv´ana. Definice Mˇejme cel´a ˇc´ısla a1 , a2 . Libovoln´e cel´e ˇc´ıslo m takov´e, ˇze m | a1 , m | a2 (resp. a1 | m, a2 | m) se naz´yv´a spoleˇcn´y dˇelitel (resp. spoleˇcn´y n´asobek) ˇc´ısel a1 , a2 . Spoleˇcn´y dˇelitel (resp. n´asobek) m ≥ 0 ˇc´ısel a1 , a2 , kter´y je dˇeliteln´y libovoln´ym spoleˇcn´ym dˇelitelem (resp. dˇel´ı libovoln´y spoleˇcn´y n´asobek) ˇc´ısel a1 , a2 , se naz´yv´a nejvˇetˇs´ı spoleˇcn´y dˇelitel (resp. nejmenˇs´ı spoleˇcn´y n´asobek) ˇc´ısel a1 , a2 a znaˇc´ı se (a1 , a2 ) (resp. [a1 , a2 ]).
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Pozn´amka Pˇr´ımo z definice plyne, ˇze pro libovoln´e a, b ∈ Z plat´ı (a, b) = (b, a), [a, b] = [b, a], (a, 1) = 1, [a, 1] = |a|, (a, 0) = |a|, [a, 0] = 0.
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Pozn´amka Pˇr´ımo z definice plyne, ˇze pro libovoln´e a, b ∈ Z plat´ı (a, b) = (b, a), [a, b] = [b, a], (a, 1) = 1, [a, 1] = |a|, (a, 0) = |a|, [a, 0] = 0. Pozn´amka Analogicky se definuje i nejvˇetˇs´ı spoleˇcn´y dˇelitel a nejmenˇs´ı spoleˇcn´y n´asobek v´ıce neˇz dvou cel´ych ˇc´ısel a snadno se n´aslednˇe dok´aˇze, ˇze plat´ı (a1 , . . . , an ) = ((a1 , . . . , an−1 ), an ) [a1 , . . . , an ] = [[a1 , . . . , an−1 ], an ]
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Euklid˚ uv algoritmus Dosud jsme nijak nezd˚ uvodnili, zda pro kaˇzdou dvojici a, b ∈ Z ˇc´ısla (a, b) a [a, b] v˚ ubec existuj´ı. Pokud vˇsak existuj´ı, jsou urˇcena jednoznaˇcnˇe: Pro kaˇzd´a dvˇe ˇc´ısla m1 , m2 ∈ N0 totiˇz podle definice plat´ı, ˇze pokud m1 | m2 a z´aroveˇ n m2 | m1 , je nutnˇe m1 = m2 . D˚ ukaz existence ˇc´ısla (a, b) pod´ame (spolu s algoritmem jeho nalezen´ı) v n´asleduj´ıc´ı vˇetˇe, d˚ ukaz existence ˇc´ısla [a, b] pak dostaneme snadno ze vztahu mezi (a, b) a [a, b].
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Euklid˚ uv algoritmus Dosud jsme nijak nezd˚ uvodnili, zda pro kaˇzdou dvojici a, b ∈ Z ˇc´ısla (a, b) a [a, b] v˚ ubec existuj´ı. Pokud vˇsak existuj´ı, jsou urˇcena jednoznaˇcnˇe: Pro kaˇzd´a dvˇe ˇc´ısla m1 , m2 ∈ N0 totiˇz podle definice plat´ı, ˇze pokud m1 | m2 a z´aroveˇ n m2 | m1 , je nutnˇe m1 = m2 . D˚ ukaz existence ˇc´ısla (a, b) pod´ame (spolu s algoritmem jeho nalezen´ı) v n´asleduj´ıc´ı vˇetˇe, d˚ ukaz existence ˇc´ısla [a, b] pak dostaneme snadno ze vztahu mezi (a, b) a [a, b]. Vˇeta (Euklid˚ uv algoritmus) Necht’ a1 , a2 jsou pˇrirozen´a ˇc´ısla. Pro kaˇzd´e n ≥ 3, pro kter´e an−1 6= 0, oznaˇcme an zbytek po dˇelen´ı ˇc´ısla an−2 ˇc´ıslem an−1 . Pak po koneˇcn´em poˇctu krok˚ u dostaneme ak = 0 a plat´ı ak−1 = (a1 , a2 ).
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
D˚ ukaz. Podle Vˇety o dˇelen´ı se zbytkem plat´ı a2 > a3 > a4 > . . . . Protoˇze jde o nez´aporn´a cel´a ˇc´ısla, je kaˇzd´e n´asleduj´ıc´ı alespoˇ n o 1 menˇs´ı neˇz pˇredchoz´ı, a proto po urˇcit´em koneˇcn´em poˇctu krok˚ u dost´av´ame ak = 0, pˇriˇcemˇz ak−1 6= 0. Z definice ˇc´ısel an plyne, ˇze existuj´ı cel´a ˇc´ısla q1 , q2 , . . . , qk−2 tak, ˇze a1 = q1 · a2 + a3 , .. . ak−3 = qk−3 · ak−2 + ak−1 ak−2 = qk−2 · ak−1 . Z posledn´ı rovnosti plyne, ˇze ak−1 | ak−2 , d´ale ak−1 | ak−3 , atd., je tedy ak−1 spoleˇcn´y dˇelitel ˇc´ısel a1 , a2 . Naopak jejich libovoln´y spoleˇcn´y dˇelitel dˇel´ı i ˇc´ıslo a3 = a1 − q1 a2 , proto i a4 = a2 − q2 a3 , . . . , a proto i ak−1 = ak−3 − qk−3 ak−2 . Dok´azali jsme, ˇze ak−1 je nejvˇetˇs´ı spoleˇcn´y dˇelitel ˇc´ısel a1 , a2 .
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Vlastnosti gcd Pozn´amka Z definice, z pˇredchoz´ıho tvrzen´ı a z toho, ˇze pro libovoln´a a, b ∈ Z plat´ı (a, b) = (a, −b) = (−a, b) = (−a, −b), plyne, ˇze existuje nejvˇetˇs´ı spoleˇcn´y dˇelitel libovoln´ych dvou cel´ych ˇc´ısel.
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Vlastnosti gcd Pozn´amka Z definice, z pˇredchoz´ıho tvrzen´ı a z toho, ˇze pro libovoln´a a, b ∈ Z plat´ı (a, b) = (a, −b) = (−a, b) = (−a, −b), plyne, ˇze existuje nejvˇetˇs´ı spoleˇcn´y dˇelitel libovoln´ych dvou cel´ych ˇc´ısel. Vˇeta (Bezoutova) Pro libovoln´a cel´a ˇc´ısla a1 , a2 existuje jejich nejvˇetˇs´ı spoleˇcn´y dˇelitel (a1 , a2 ), pˇritom existuj´ı cel´a ˇc´ısla k1 , k2 tak, ˇze (a1 , a2 ) = k1 a1 + k2 a2 .
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Vlastnosti gcd Pozn´amka Z definice, z pˇredchoz´ıho tvrzen´ı a z toho, ˇze pro libovoln´a a, b ∈ Z plat´ı (a, b) = (a, −b) = (−a, b) = (−a, −b), plyne, ˇze existuje nejvˇetˇs´ı spoleˇcn´y dˇelitel libovoln´ych dvou cel´ych ˇc´ısel. Vˇeta (Bezoutova) Pro libovoln´a cel´a ˇc´ısla a1 , a2 existuje jejich nejvˇetˇs´ı spoleˇcn´y dˇelitel (a1 , a2 ), pˇritom existuj´ı cel´a ˇc´ısla k1 , k2 tak, ˇze (a1 , a2 ) = k1 a1 + k2 a2 . D˚ usledek Pro libovoln´a cel´a ˇc´ısla a1 , a2 lze jako celoˇc´ıseln´e kombinace n = k1 a1 + k2 a2 vyj´adˇrit pr´avˇe n´asobky nejvˇetˇs´ıho spoleˇcn´eho dˇelitele (a1 , a2 ).
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
D˚ ukaz. Jistˇe staˇc´ı vˇetu dok´azat pro a1 , a2 ∈ N. Vˇsimnˇeme si, ˇze jestliˇze je moˇzn´e nˇejak´a ˇc´ısla r , s ∈ Z vyj´adˇrit ve tvaru r = r1 a1 + r2 a2 , s = s1 a1 + s2 a2 , kde r1 , r2 , s1 , s2 ∈ Z, m˚ uˇzeme tak vyj´adˇrit i r + s = (r1 + s1 )a1 + (r2 + s2 )a2 a tak´e c · r = (c · r1 )a1 + (c · r2 )a2 pro libovoln´e c ∈ Z. Protoˇze a1 = 1 · a1 + 0 · a2 , a2 = 0 · a1 + 1 · a2 , plyne z (5), ˇze takto m˚ uˇzeme vyj´adˇrit i a3 = a1 − q1 a2 , a4 = a2 − q2 a3 , . . . , ak−1 = ak−3 − qk−3 ak−2 , coˇz je ovˇsem (a1 , a2 ).
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Pˇr´ıklad V´ypoˇcet nejvˇetˇs´ıho spoleˇcn´eho dˇelitele pomoc´ı Euklidova algoritmu je s vyuˇzit´ım v´ypoˇcetn´ı techniky i pro relativnˇe velk´a ˇc´ısla pomˇernˇe rychl´y. V naˇsem pˇr´ıkladu to vyzkouˇs´ıme na 2 ˇc´ıslech A,B, z nichˇz kaˇzd´e je souˇcinem dvou 101-cifern´ych prvoˇc´ısel. Vˇsimnˇeme si, ˇze v´ypoˇcet nejvˇetˇs´ıho spoleˇcn´eho dˇelitele i takto velk´ych ˇc´ısel trval zanedbateln´y ˇcas. Pˇr´ıklad v syst´emu SAGE je dostupn´y na https://sage.math.muni.cz/home/pub/6/. Pozn´amka Euklid˚ uv algoritmus a Bezoutova vˇeta jsou z´akladn´ımi v´ysledky element´arn´ı teorie ˇc´ısel a tvoˇr´ı jeden z pil´ıˇr˚ u algoritm˚ u algebry a teorie ˇc´ısel.
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Nejmenˇs´ı spoleˇcn´y n´asobek
Vˇeta Pro libovoln´a cel´a ˇc´ısla a1 , a2 existuje jejich nejmenˇs´ı spoleˇcn´y n´asobek [a1 , a2 ] a plat´ı (a1 , a2 ) · [a1 , a2 ] = |a1 · a2 |.
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Nejmenˇs´ı spoleˇcn´y n´asobek
Vˇeta Pro libovoln´a cel´a ˇc´ısla a1 , a2 existuje jejich nejmenˇs´ı spoleˇcn´y n´asobek [a1 , a2 ] a plat´ı (a1 , a2 ) · [a1 , a2 ] = |a1 · a2 |. D˚ ukaz. Vˇeta jistˇe plat´ı, je-li nˇekter´e z ˇc´ısel a1 , a2 rovno nule. M˚ uˇzeme nav´ıc pˇredpokl´adat, ˇze obˇe nenulov´a ˇc´ısla a1 , a2 jsou kladn´a, nebot’ jejich znam´enka se v dokazovan´em vzorci neprojev´ı. Budeme hotovi, uk´aˇzeme-li, ˇze q = a1 · a2 /(a1 , a2 ) je nejmenˇs´ı spoleˇcn´y n´asobek ˇc´ısel a1 , a2 .
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Dokonˇcen´ı. Protoˇze (a1 , a2 ) je spoleˇcn´y dˇelitel ˇc´ısel a1 , a2 , jsou a1 /(a1 , a2 ) i a2 /(a1 , a2 ) cel´a ˇc´ısla, a proto q=
a1 a2 a1 a2 = · a2 = · a1 (a1 , a2 ) (a1 , a2 ) (a1 , a2 )
je spoleˇcn´y n´asobek ˇc´ısel a1 , a2 . Podle vˇety 3 existuj´ı k1 , k2 ∈ Z tak, ˇze (a1 , a2 ) = k1 a1 + k2 a2 . Pˇredpokl´adejme, ˇze n ∈ Z je libovoln´y spoleˇcn´y n´asobek ˇc´ısel a1 , a2 a uk´aˇzeme, ˇze je dˇeliteln´y ˇc´ıslem q. Je tedy n/a1 , n/a2 ∈ Z, a proto je i cel´e ˇc´ıslo n n n(k1 a1 + k2 a2 ) n(a1 , a2 ) n · k1 + · k2 = = = . a2 a1 a1 a2 a1 a2 q To ovˇsem znamen´a, ˇze q | n, coˇz jsme chtˇeli dok´azat.
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Nesoudˇelnost Definice ˇ ısla a1 , a2 , . . . , an ∈ Z se naz´yvaj´ı nesoudˇeln´a, jestliˇze plat´ı C´ ˇ ısla a1 , a2 , . . . , an ∈ Z se naz´yvaj´ı po dvou (a1 , a2 , . . . , an ) = 1. C´ nesoudˇeln´a, jestliˇze pro kaˇzd´e i, j takov´e, ˇze 1 ≤ i < j ≤ n, plat´ı (ai , aj ) = 1. Pozn´amka V pˇr´ıpadˇe n = 2 oba pojmy spl´yvaj´ı, pro n > 2 plyne z nesoudˇelnosti po dvou nesoudˇelnost, ne vˇsak naopak: napˇr´ıklad ˇc´ısla 6, 10, 15 jsou nesoudˇeln´a, ale nejsou nesoudˇeln´a po dvou, nebot’ dokonce ˇz´adn´a dvojice z nich vybran´a nesoudˇeln´a nen´ı: (6, 10) = 2, (6, 15) = 3, (10, 15) = 5.
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Vˇeta Pro libovoln´a pˇrirozen´a ˇc´ısla a, b, c plat´ı 1
(ac, bc) = (a, b) · c,
2
jestliˇze a | bc, (a, b) = 1, pak a | c,
3
d = (a, b) pr´avˇe tehdy, kdyˇz existuj´ı q1 , q2 ∈ N tak, ˇze a = dq1 , b = dq2 a (q1 , q2 ) = 1.
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
D˚ ukaz. ad 1. Protoˇze (a, b) je spoleˇcn´y dˇelitel ˇc´ısel a, b, je (a, b) · c spoleˇcn´y dˇelitel ˇc´ısel ac, bc, proto (a, b) · c | (ac, bc). Podle Bezoutovy vˇety existuj´ı k, l ∈ Z tak, ˇze (a, b) = ka + lb. Protoˇze (ac, bc) je spoleˇcn´y dˇelitel ˇc´ısel ac, bc, dˇel´ı i ˇc´ıslo kac + lbc = (a, b) · c. Dok´azali jsme, ˇze (a, b) · c a (ac, bc) jsou dvˇe pˇrirozen´a ˇc´ısla, kter´a dˇel´ı jedno druh´e, proto se rovnaj´ı.
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
D˚ ukaz. ad 1. Protoˇze (a, b) je spoleˇcn´y dˇelitel ˇc´ısel a, b, je (a, b) · c spoleˇcn´y dˇelitel ˇc´ısel ac, bc, proto (a, b) · c | (ac, bc). Podle Bezoutovy vˇety existuj´ı k, l ∈ Z tak, ˇze (a, b) = ka + lb. Protoˇze (ac, bc) je spoleˇcn´y dˇelitel ˇc´ısel ac, bc, dˇel´ı i ˇc´ıslo kac + lbc = (a, b) · c. Dok´azali jsme, ˇze (a, b) · c a (ac, bc) jsou dvˇe pˇrirozen´a ˇc´ısla, kter´a dˇel´ı jedno druh´e, proto se rovnaj´ı. ad 2. Pˇredpokl´adejme, ˇze (a, b) = 1 a a | bc. Podle Bezoutovy vˇety existuj´ı k, l ∈ Z tak, ˇze ka + lb = 1, odkud plyne, ˇze c = c(ka + lb) = kca + lbc. Protoˇze a | bc, plyne odsud, ˇze i a | c.
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
D˚ ukaz. ad 1. Protoˇze (a, b) je spoleˇcn´y dˇelitel ˇc´ısel a, b, je (a, b) · c spoleˇcn´y dˇelitel ˇc´ısel ac, bc, proto (a, b) · c | (ac, bc). Podle Bezoutovy vˇety existuj´ı k, l ∈ Z tak, ˇze (a, b) = ka + lb. Protoˇze (ac, bc) je spoleˇcn´y dˇelitel ˇc´ısel ac, bc, dˇel´ı i ˇc´ıslo kac + lbc = (a, b) · c. Dok´azali jsme, ˇze (a, b) · c a (ac, bc) jsou dvˇe pˇrirozen´a ˇc´ısla, kter´a dˇel´ı jedno druh´e, proto se rovnaj´ı. ad 2. Pˇredpokl´adejme, ˇze (a, b) = 1 a a | bc. Podle Bezoutovy vˇety existuj´ı k, l ∈ Z tak, ˇze ka + lb = 1, odkud plyne, ˇze c = c(ka + lb) = kca + lbc. Protoˇze a | bc, plyne odsud, ˇze i a | c. ad 3. Necht’ d = (a, b), pak existuj´ı q1 , q2 ∈ N tak, ˇze a = dq1 , b = dq2 . Pak podle 1. ˇc´asti plat´ı d = (a, b) = (dq1 , dq2 ) = d · (q1 , q2 ), a tedy (q1 , q2 ) = 1. Naopak, je-li a = dq1 , b = dq2 a (q1 , q2 ) = 1, pak (a, b) = (dq1 , dq2 ) = d(q1 , q2 ) = d · 1 = d (opˇet uˇzit´ım 1. ˇc´asti tohoto tvrzen´ı).
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Prvoˇc´ıslo je jeden z nejd˚ uleˇzitˇejˇs´ıch pojm˚ u element´arn´ı teorie ˇc´ısel. Jeho d˚ uleˇzitost je d´ana pˇredevˇs´ım vˇetou o jednoznaˇcn´em rozkladu libovoln´eho pˇrirozen´eho ˇc´ısla na souˇcin prvoˇc´ısel, kter´a je siln´ym a u ´ˇcinn´ym n´astrojem pˇri ˇreˇsen´ı cel´e ˇrady u ´loh z teorie ˇc´ısel. Definice Kaˇzd´e pˇrirozen´e ˇc´ıslo n ≥ 2 m´a aspoˇ n dva kladn´e dˇelitele: 1 a n. Pokud kromˇe tˇechto dvou jin´e kladn´e dˇelitele nem´a, naz´yv´a se prvoˇc´ıslo. V opaˇcn´em pˇr´ıpadˇe hovoˇr´ıme o sloˇzen´em ˇc´ısle.
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Prvoˇc´ıslo je jeden z nejd˚ uleˇzitˇejˇs´ıch pojm˚ u element´arn´ı teorie ˇc´ısel. Jeho d˚ uleˇzitost je d´ana pˇredevˇs´ım vˇetou o jednoznaˇcn´em rozkladu libovoln´eho pˇrirozen´eho ˇc´ısla na souˇcin prvoˇc´ısel, kter´a je siln´ym a u ´ˇcinn´ym n´astrojem pˇri ˇreˇsen´ı cel´e ˇrady u ´loh z teorie ˇc´ısel. Definice Kaˇzd´e pˇrirozen´e ˇc´ıslo n ≥ 2 m´a aspoˇ n dva kladn´e dˇelitele: 1 a n. Pokud kromˇe tˇechto dvou jin´e kladn´e dˇelitele nem´a, naz´yv´a se prvoˇc´ıslo. V opaˇcn´em pˇr´ıpadˇe hovoˇr´ıme o sloˇzen´em ˇc´ısle. V dalˇs´ım textu budeme zpravidla prvoˇc´ıslo znaˇcit p´ısmenem p. Nejmenˇs´ı prvoˇc´ısla jsou 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, . . . (zejm´ena ˇc´ıslo 1 za prvoˇc´ıslo ani za ˇc´ıslo sloˇzen´e nepovaˇzujeme, je totiˇz invertibiln´ı, neboli tzv. jednotkou okruhu cel´ych ˇc´ısel). Prvoˇc´ısel je, jak brzy dok´aˇzeme, nekoneˇcnˇe mnoho, m´ame ovˇsem pomˇernˇe limitovan´e v´ypoˇcetn´ı prostˇredky na zjiˇstˇen´ı, zda je dan´e ˇc´ıslo prvoˇc´ıslem (nejvˇetˇs´ı zn´am´e prvoˇc´ıslo 257 885 161 − 1 m´a pouze 17 425 170 cifer).
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Uved’me nyn´ı vˇetu, kter´a ud´av´a ekvivalentn´ı podm´ınku prvoˇc´ıselnosti a je z´akladn´ı ingredienc´ı pˇri d˚ ukazu jednoznaˇcnosti rozkladu na prvoˇc´ısla. Vˇeta (Euklidova o prvoˇc´ıslech) Pˇrirozen´e ˇc´ıslo p ≥ 2 je prvoˇc´ıslo, pr´avˇe kdyˇz plat´ı: pro kaˇzd´a cel´a ˇc´ısla a, b z p | ab plyne p | a nebo p | b.
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Uved’me nyn´ı vˇetu, kter´a ud´av´a ekvivalentn´ı podm´ınku prvoˇc´ıselnosti a je z´akladn´ı ingredienc´ı pˇri d˚ ukazu jednoznaˇcnosti rozkladu na prvoˇc´ısla. Vˇeta (Euklidova o prvoˇc´ıslech) Pˇrirozen´e ˇc´ıslo p ≥ 2 je prvoˇc´ıslo, pr´avˇe kdyˇz plat´ı: pro kaˇzd´a cel´a ˇc´ısla a, b z p | ab plyne p | a nebo p | b. D˚ ukaz. ”⇒”Pˇredpokl´adejme, ˇze p je prvoˇc´ıslo a p | ab, kde a, b ∈ Z. Protoˇze (p, a) je kladn´y dˇelitel p, plat´ı (p, a) = p nebo (p, a) = 1. V prvn´ım pˇr´ıpadˇe p | a, ve druh´em p | b podle ˇc´asti 2. pˇredchoz´ı vˇety.
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Uved’me nyn´ı vˇetu, kter´a ud´av´a ekvivalentn´ı podm´ınku prvoˇc´ıselnosti a je z´akladn´ı ingredienc´ı pˇri d˚ ukazu jednoznaˇcnosti rozkladu na prvoˇc´ısla. Vˇeta (Euklidova o prvoˇc´ıslech) Pˇrirozen´e ˇc´ıslo p ≥ 2 je prvoˇc´ıslo, pr´avˇe kdyˇz plat´ı: pro kaˇzd´a cel´a ˇc´ısla a, b z p | ab plyne p | a nebo p | b. D˚ ukaz. ”⇒”Pˇredpokl´adejme, ˇze p je prvoˇc´ıslo a p | ab, kde a, b ∈ Z. Protoˇze (p, a) je kladn´y dˇelitel p, plat´ı (p, a) = p nebo (p, a) = 1. V prvn´ım pˇr´ıpadˇe p | a, ve druh´em p | b podle ˇc´asti 2. pˇredchoz´ı vˇety. ”⇐”Jestliˇze p nen´ı prvoˇc´ıslo, mus´ı existovat jeho kladn´y dˇelitel r˚ uzn´y od 1 a p. Oznaˇc´ıme jej a; pak ovˇsem b = pa ∈ N a plat´ı p = ab, odkud 1 < a < p, 1 < b < p. Naˇsli jsme tedy cel´a ˇc´ısla a, b tak, ˇze p | ab a pˇritom p nedˇel´ı ani a, ani b.
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Z´akladn´ı vˇeta aritmetiky Vˇeta Libovoln´e pˇrirozen´e ˇc´ıslo n ≥ 2 je moˇzn´e vyj´adˇrit jako souˇcin prvoˇc´ısel, pˇriˇcemˇz je toto vyj´adˇren´ı jedin´e, nebereme-li v u ´vahu poˇrad´ı ˇcinitel˚ u. (Je-li n prvoˇc´ıslo, pak jde o souˇcin“ jednoho ” prvoˇc´ısla.)
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Z´akladn´ı vˇeta aritmetiky Vˇeta Libovoln´e pˇrirozen´e ˇc´ıslo n ≥ 2 je moˇzn´e vyj´adˇrit jako souˇcin prvoˇc´ısel, pˇriˇcemˇz je toto vyj´adˇren´ı jedin´e, nebereme-li v u ´vahu poˇrad´ı ˇcinitel˚ u. (Je-li n prvoˇc´ıslo, pak jde o souˇcin“ jednoho ” prvoˇc´ısla.) Pozn´amka Dˇelitelnost je moˇzn´e obdobn´ym zp˚ usobem definovat v libovoln´em oboru integrity (zkuste si rozmyslet, proˇc se omezujeme na obory integrity). V nˇekter´ych oborech integrity pˇritom ˇz´adn´e prvky s vlastnost´ı prvoˇc´ısla (ˇr´ık´ame jim ireducibiln´ı) neexistuj´ı (napˇr. Q), v jin´ych sice ireducibiln´ı prvky existuj´ı,√ale zase tam neplat´ı vˇeta o jednoznaˇcn´em rozkladu (napˇ −5) m´ame n´asleduj´ıc´ı √ r. v Z( √ rozklady: 6 = 2 · 3 = (1 + −5) · (1 − −5);√zkuste si rozmyslet, ˇze vˇsichni uveden´ı ˇcinitel´e jsou skuteˇcnˇe v Z( −5) ireducibiln´ı).
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
D˚ ukaz. Nejprve dok´aˇzeme indukc´ı, ˇze kaˇzd´e n ≥ 2 je moˇzn´e vyj´adˇrit jako souˇcin prvoˇc´ısel. Je-li n = 2, je n souˇcin jedin´eho prvoˇc´ısla 2. Pˇredpokl´adejme nyn´ı, ˇze n > 2 a ˇze jsme jiˇz dok´azali, ˇze libovoln´e n0 , 2 ≤ n0 < n, je moˇzn´e rozloˇzit na souˇcin prvoˇc´ısel. Jestliˇze n je prvoˇc´ıslo, je souˇcinem jedin´eho prvoˇc´ısla. Jestliˇze n prvoˇc´ıslo nen´ı, pak existuje jeho dˇelitel d, 1 < d < n. Oznaˇc´ıme-li c = dn , plat´ı tak´e 1 < c < n. Z indukˇcn´ıho pˇredpokladu plyne, ˇze c i d je moˇzn´e vyj´adˇrit jako souˇcin prvoˇc´ısel, a proto je takto moˇzn´e vyj´adˇrit i jejich souˇcin c · d = n.
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
D˚ ukaz. Nejprve dok´aˇzeme indukc´ı, ˇze kaˇzd´e n ≥ 2 je moˇzn´e vyj´adˇrit jako souˇcin prvoˇc´ısel. Je-li n = 2, je n souˇcin jedin´eho prvoˇc´ısla 2. Pˇredpokl´adejme nyn´ı, ˇze n > 2 a ˇze jsme jiˇz dok´azali, ˇze libovoln´e n0 , 2 ≤ n0 < n, je moˇzn´e rozloˇzit na souˇcin prvoˇc´ısel. Jestliˇze n je prvoˇc´ıslo, je souˇcinem jedin´eho prvoˇc´ısla. Jestliˇze n prvoˇc´ıslo nen´ı, pak existuje jeho dˇelitel d, 1 < d < n. Oznaˇc´ıme-li c = dn , plat´ı tak´e 1 < c < n. Z indukˇcn´ıho pˇredpokladu plyne, ˇze c i d je moˇzn´e vyj´adˇrit jako souˇcin prvoˇc´ısel, a proto je takto moˇzn´e vyj´adˇrit i jejich souˇcin c · d = n. Nyn´ı dok´aˇzeme jednoznaˇcnost. Pˇredpokl´adejme, ˇze plat´ı rovnost souˇcin˚ u p1 · p2 · · · · · pm = q1 · q2 · · · · · qs , kde p1 , . . . , pm , q1 , . . . , qs jsou prvoˇc´ısla a nav´ıc plat´ı p1 ≤ p2 ≤ · · · ≤ pm , q1 ≤ q2 ≤ · · · ≤ qs a 1 ≤ m ≤ s. Indukc´ı vzhledem k m dok´aˇzeme, ˇze m = s, p1 = q1 , . . . , pm = qm .
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Dokonˇcen´ı. Je-li m = 1, je p1 = q1 · · · · · qs prvoˇc´ıslo. Kdyby s > 1, mˇelo by ˇc´ıslo p1 dˇelitele q1 takov´eho, ˇze 1 < q1 < p1 (nebot’ q2 q3 . . . qs > 1), coˇz nen´ı moˇzn´e. Je tedy s = 1 a plat´ı p1 = q1 .
Probl´ emy teorie ˇ c´ısel
Dˇ elitelnost
Spoleˇ cn´ı dˇ elitel´ e a spoleˇ cn´ e n´ asobky
Dokonˇcen´ı. Je-li m = 1, je p1 = q1 · · · · · qs prvoˇc´ıslo. Kdyby s > 1, mˇelo by ˇc´ıslo p1 dˇelitele q1 takov´eho, ˇze 1 < q1 < p1 (nebot’ q2 q3 . . . qs > 1), coˇz nen´ı moˇzn´e. Je tedy s = 1 a plat´ı p1 = q1 . Pˇredpokl´adejme, ˇze m ≥ 2 a ˇze tvrzen´ı plat´ı pro m − 1. Protoˇze p1 · p2 · · · · · pm = q1 · q2 · · · · · qs , dˇel´ı pm souˇcin q1 · · · · · qs , coˇz je podle Euklidovy vˇety moˇzn´e jen tehdy, jestliˇze pm dˇel´ı nˇejak´e qi pro vhodn´e i ∈ {1, 2, . . . , s}. Protoˇze qi je prvoˇc´ıslo, plyne odtud pm = qi (nebot’ pm > 1). Zcela analogicky se dok´aˇze, ˇze qs = pj pro vhodn´e j ∈ {1, 2, . . . , m}. Odtud plyne qs = pj ≤ pm = qi ≤ qs , takˇze pm = qs . Vydˇelen´ım dostaneme p1 · p2 · · · · · pm−1 = q1 · q2 · · · · · qs−1 , a tedy z indukˇcn´ıho pˇredpokladu m − 1 = s − 1, p1 = q1 , . . . , pm−1 = qm−1 . Celkem tedy m = s a p1 = q1 , . . . , pm−1 = qm−1 , pm = qm . Jednoznaˇcnost, a tedy i cel´a vˇeta, je dok´az´ana.
