´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Chv´ ala d˚ ukaz˚ u Jindˇ rich Beˇ cv´ aˇ r Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
Bansk´a Bystrica, 11. ˇr´ıjna 2016
[email protected] www.karlin.mff.cuni.cz/∼becvar www.karlin.mff.cuni.cz/katedry/kdm J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Osnova
´ 1 Uvod 2 Prvoˇ c´ısla 3 Dokonal´ a ˇc´ısla 4 Mersennova prvoˇ c´ısla 5 D˚ ukazy beze slov
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
´ Uvod Marnˇe by n´am Eukleides pˇredkl´adal nejkr´asnˇejˇs´ı geometrick´e pravdy, kdyby nebyl dodal d˚ ukazy potˇrebn´e k tomu, aby n´as pˇresvˇedˇcil. Na jeho pouh´e slovo bychom mu ony pravdy nikdy neuvˇeˇrili. Leonhard Euler (1707–1783)
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
´ Uvod Marnˇe by n´am Eukleides pˇredkl´adal nejkr´asnˇejˇs´ı geometrick´e pravdy, kdyby nebyl dodal d˚ ukazy potˇrebn´e k tomu, aby n´as pˇresvˇedˇcil. Na jeho pouh´e slovo bychom mu ony pravdy nikdy neuvˇeˇrili. Leonhard Euler (1707–1783) Vˇedeck´e pozn´an´ı je soubor tvrzen´ı s r˚ uzn´ym stupnˇem jistoty; nˇekter´a z tˇechto tvrzen´ı jsou velmi nejist´a, nˇekter´a jsou t´emˇeˇr jist´a, ale ˇz´adn´e z nich nen´ı zcela jist´e. Richard Feynman (1918–1988) pˇredn´aˇska v Americk´e N´arodn´ı Akademii Vˇed, 1955 J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Poˇ c´ atky d˚ ukazov´ e techniky • Egypt, Mezopot´amie, ...
Existoval d˚ ukaz (v naˇsem slova smyslu)?
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Poˇ c´ atky d˚ ukazov´ e techniky • Egypt, Mezopot´amie, ...
Existoval d˚ ukaz (v naˇsem slova smyslu)? Byla pociˇtov´ana potˇreba d˚ ukazu?
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Poˇ c´ atky d˚ ukazov´ e techniky • Egypt, Mezopot´amie, ...
Existoval d˚ ukaz (v naˇsem slova smyslu)? Byla pociˇtov´ana potˇreba d˚ ukazu?
ˇ • Star´e Recko Vn´ım´an´ı pˇr´ıˇcinnosti, implikace: jestliˇze ..., potom ...
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Poˇ c´ atky d˚ ukazov´ e techniky • Egypt, Mezopot´amie, ...
Existoval d˚ ukaz (v naˇsem slova smyslu)? Byla pociˇtov´ana potˇreba d˚ ukazu?
ˇ • Star´e Recko Vn´ım´an´ı pˇr´ıˇcinnosti, implikace: jestliˇze ..., potom ... Prvn´ı d˚ ukazy: poloˇzit pˇred oˇci, udˇelat zˇrejm´ym, viditeln´ym
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Poˇ c´ atky d˚ ukazov´ e techniky • Egypt, Mezopot´amie, ...
Existoval d˚ ukaz (v naˇsem slova smyslu)? Byla pociˇtov´ana potˇreba d˚ ukazu?
ˇ • Star´e Recko Vn´ım´an´ı pˇr´ıˇcinnosti, implikace: jestliˇze ..., potom ... Prvn´ı d˚ ukazy: poloˇzit pˇred oˇci, udˇelat zˇrejm´ym, viditeln´ym – Figur´aln´ı ˇc´ısla – Pr´ace se sud´ymi a lich´ymi ˇc´ısly • • • • • • •
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
+
• • • • •
=
• • • • • • • • • • • •
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Poˇ c´ atky d˚ ukazov´ e techniky • Egypt, Mezopot´amie, ...
Existoval d˚ ukaz (v naˇsem slova smyslu)? Byla pociˇtov´ana potˇreba d˚ ukazu?
ˇ • Star´e Recko Vn´ım´an´ı pˇr´ıˇcinnosti, implikace: jestliˇze ..., potom ... Prvn´ı d˚ ukazy: poloˇzit pˇred oˇci, udˇelat zˇrejm´ym, viditeln´ym – Figur´aln´ı ˇc´ısla – Pr´ace se sud´ymi a lich´ymi ˇc´ısly • • • • • • •
+
• • • • •
=
• • • • • • • • • • • •
– P´ythagorova vˇeta, Eukleidova vˇeta o odvˇesnˇe, ... J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
N´ ar˚ ust abstrakce, d˚ ukazy sporem (5. a 4. stolet´ı pˇr. Kr.) √ – objev nesoumˇeˇriteln´ych u ´seˇcek (iracionalita ˇc´ısla 2) – iracionalit je nekoneˇcnˇe mnoho
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
N´ ar˚ ust abstrakce, d˚ ukazy sporem (5. a 4. stolet´ı pˇr. Kr.) √ – objev nesoumˇeˇriteln´ych u ´seˇcek (iracionalita ˇc´ısla 2) – iracionalit je nekoneˇcnˇe mnoho – Eukleid´es: Stoicheia (Z´aklady ) (kolem r. 300 pˇr. Kr.) Vzor pro budov´an´ı vˇedeck´e teorie pro cel´a dvˇe tis´ıcilet´ı
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
N´ ar˚ ust abstrakce, d˚ ukazy sporem (5. a 4. stolet´ı pˇr. Kr.) √ – objev nesoumˇeˇriteln´ych u ´seˇcek (iracionalita ˇc´ısla 2) – iracionalit je nekoneˇcnˇe mnoho – Eukleid´es: Stoicheia (Z´aklady ) (kolem r. 300 pˇr. Kr.) Vzor pro budov´an´ı vˇedeck´e teorie pro cel´a dvˇe tis´ıcilet´ı
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
N´ ar˚ ust abstrakce, d˚ ukazy sporem (5. a 4. stolet´ı pˇr. Kr.) √ – objev nesoumˇeˇriteln´ych u ´seˇcek (iracionalita ˇc´ısla 2) – iracionalit je nekoneˇcnˇe mnoho – Eukleid´es: Stoicheia (Z´aklady ) (kolem r. 300 pˇr. Kr.) Vzor pro budov´an´ı vˇedeck´e teorie pro cel´a dvˇe tis´ıcilet´ı Metodick´ a pozn´ amka
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
N´ ar˚ ust abstrakce, d˚ ukazy sporem (5. a 4. stolet´ı pˇr. Kr.) √ – objev nesoumˇeˇriteln´ych u ´seˇcek (iracionalita ˇc´ısla 2) – iracionalit je nekoneˇcnˇe mnoho – Eukleid´es: Stoicheia (Z´aklady ) (kolem r. 300 pˇr. Kr.) Vzor pro budov´an´ı vˇedeck´e teorie pro cel´a dvˇe tis´ıcilet´ı Metodick´ a pozn´ amka
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
N´ ar˚ ust abstrakce, d˚ ukazy sporem (5. a 4. stolet´ı pˇr. Kr.) √ – objev nesoumˇeˇriteln´ych u ´seˇcek (iracionalita ˇc´ısla 2) – iracionalit je nekoneˇcnˇe mnoho – Eukleid´es: Stoicheia (Z´aklady ) (kolem r. 300 pˇr. Kr.) Vzor pro budov´an´ı vˇedeck´e teorie pro cel´a dvˇe tis´ıcilet´ı Metodick´ a pozn´ amka (m´a tvar implikace):
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
N´ ar˚ ust abstrakce, d˚ ukazy sporem (5. a 4. stolet´ı pˇr. Kr.) √ – objev nesoumˇeˇriteln´ych u ´seˇcek (iracionalita ˇc´ısla 2) – iracionalit je nekoneˇcnˇe mnoho – Eukleid´es: Stoicheia (Z´aklady ) (kolem r. 300 pˇr. Kr.) Vzor pro budov´an´ı vˇedeck´e teorie pro cel´a dvˇe tis´ıcilet´ı Metodick´ a pozn´ amka (m´a tvar implikace): Likvidujeme-li d˚ ukazy ve ˇskolsk´e matematice, likvidujeme matematiku. Pˇrestane b´yt ch´ap´ana pˇr´ıˇcinnost, neotˇresitelnost matematick´ych pravd. Ztr´ac´ıme mnoho moˇznost´ı pro vzbuzen´ı z´ajmu o matematiku. J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Prvoˇc´ısla Def. Prvoˇc´ıslem rozum´ıme pˇrirozen´e ˇc´ıslo p, kter´e m´a pr´avˇe dva dˇelitele, tj. 1 a p. Ostatn´ı pˇrirozen´a ˇc´ısla (kromˇe ˇc´ısla 1) se naz´yvaj´ı sloˇzen´a. Pˇr. 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, ...
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Prvoˇc´ısla Def. Prvoˇc´ıslem rozum´ıme pˇrirozen´e ˇc´ıslo p, kter´e m´a pr´avˇe dva dˇelitele, tj. 1 a p. Ostatn´ı pˇrirozen´a ˇc´ısla (kromˇe ˇc´ısla 1) se naz´yvaj´ı sloˇzen´a. Pˇr. 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, ... – Z hrom´adky kam´enk˚ u prvoˇc´ıseln´eho poˇctu nelze sestavit (netrivi´aln´ı) obd´eln´ıkov´e ˇc´ıslo. • • • • J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
• • • •
• • • •
• • • • • • • •
• • • • •
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Vˇ eta. Prvoˇc´ısel je nekoneˇcnˇe mnoho. (Eukleid´es: Stoicheia), IX.20
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Vˇ eta. Prvoˇc´ısel je nekoneˇcnˇe mnoho. (Eukleid´es: Stoicheia), IX.20 D˚ ukaz sporem. Pˇredpokl´adejme, ˇze 2 < 3 < · · · < p jsou vˇsechna prvoˇc´ısla. Utvoˇrme ˇc´ıslo n = 2 · 3 · 5 · · · · · p + 1, kter´e je vˇetˇs´ı neˇz p, a proto je sloˇzen´e. Pˇritom nen´ı dˇeliteln´e ˇz´adn´ym z prvoˇc´ısel 2, 3, . . . , p. Mus´ı b´yt tedy dˇeliteln´e jin´ym prvoˇc´ıslem. Spor.
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Vˇ eta. Prvoˇc´ısel je nekoneˇcnˇe mnoho. (Eukleid´es: Stoicheia), IX.20 D˚ ukaz sporem. Pˇredpokl´adejme, ˇze 2 < 3 < · · · < p jsou vˇsechna prvoˇc´ısla. Utvoˇrme ˇc´ıslo n = 2 · 3 · 5 · · · · · p + 1, kter´e je vˇetˇs´ı neˇz p, a proto je sloˇzen´e. Pˇritom nen´ı dˇeliteln´e ˇz´adn´ym z prvoˇc´ısel 2, 3, . . . , p. Mus´ı b´yt tedy dˇeliteln´e jin´ym prvoˇc´ıslem. Spor. D˚ ukaz nen´ı zcela korektn´ı!
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Vˇ eta. Prvoˇc´ısel je nekoneˇcnˇe mnoho. (Eukleid´es: Stoicheia), IX.20 D˚ ukaz sporem. Pˇredpokl´adejme, ˇze 2 < 3 < · · · < p jsou vˇsechna prvoˇc´ısla. Utvoˇrme ˇc´ıslo n = 2 · 3 · 5 · · · · · p + 1, kter´e je vˇetˇs´ı neˇz p, a proto je sloˇzen´e. Pˇritom nen´ı dˇeliteln´e ˇz´adn´ym z prvoˇc´ısel 2, 3, . . . , p. Mus´ı b´yt tedy dˇeliteln´e jin´ym prvoˇc´ıslem. Spor. D˚ ukaz nen´ı zcela korektn´ı! Mlˇcky pˇredpokl´ad´ame existenci rozkladu na prvoˇc´ısla (jedna ˇc´ast tzv. Z´akladn´ı vˇety aritmetiky ). J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Dokonal´a ˇc´ısla Def. Dokonal´ym ˇc´ıslem rozum´ıme pˇrirozen´e ˇc´ıslo, kter´e je souˇctem vˇsech sv´ych vlastn´ıch dˇelitel˚ u. ˇ Pˇr. Staˇr´ı Rekov´ e znali tato dokonal´a ˇc´ısla: 6=1+2+3 28 = 1 + 2 + 4 + 7 + 14 496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248 8128 = 1 + 2 + 4 + 8 + 16 + 32 + 64 + +127 + 254 + 508 + 1016 + 2032 + 4064
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Dokonal´a ˇc´ısla Def. Dokonal´ym ˇc´ıslem rozum´ıme pˇrirozen´e ˇc´ıslo, kter´e je souˇctem vˇsech sv´ych vlastn´ıch dˇelitel˚ u. ˇ Pˇr. Staˇr´ı Rekov´ e znali tato dokonal´a ˇc´ısla: 6=1+2+3 28 = 1 + 2 + 4 + 7 + 14 496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248 8128 = 1 + 2 + 4 + 8 + 16 + 32 + 64 + +127 + 254 + 508 + 1016 + 2032 + 4064 6=1+2+3·1
28 = 1 + 2 + 4 + 7 · (1 + 2)
496 = 1 + 2 + 4 + 8 + 16 + 31 · (1 + 2 + 4 + 8) 8128 = 1 + 2 + 4 + 8 + 16 + 32 + 64 + 127 · (1 + 2 + 4 + 8 + 16 + 32) J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Vˇ eta. Jestliˇze je 2p − 1 prvoˇc´ıslo, pak je 2p−1 (2p − 1) ˇc´ıslo dokonal´e. (Eukleid´es: Stoicheia), IX.36
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Vˇ eta. Jestliˇze je 2p − 1 prvoˇc´ıslo, pak je 2p−1 (2p − 1) ˇc´ıslo dokonal´e. (Eukleid´es: Stoicheia), IX.36 D˚ ukaz. Seˇctˇeme vˇsechny vlastn´ı dˇelitele ˇc´ısla 2p−1 (2p − 1): (1 + 2 + · · · + 2p−1 ) + (1 + 2 + · · · + 2p−2 ) · (2p − 1) = =1·
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
2p − 1 2p−1 − 1 + (2p − 1) · = (2p − 1)2p−1 2−1 2−1
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Vˇ eta. Jestliˇze je 2p − 1 prvoˇc´ıslo, pak je 2p−1 (2p − 1) ˇc´ıslo dokonal´e. (Eukleid´es: Stoicheia), IX.36 D˚ ukaz. Seˇctˇeme vˇsechny vlastn´ı dˇelitele ˇc´ısla 2p−1 (2p − 1): (1 + 2 + · · · + 2p−1 ) + (1 + 2 + · · · + 2p−2 ) · (2p − 1) = =1·
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
2p − 1 2p−1 − 1 + (2p − 1) · = (2p − 1)2p−1 2−1 2−1
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Vˇ eta. Jestliˇze je 2p − 1 prvoˇc´ıslo, pak je 2p−1 (2p − 1) ˇc´ıslo dokonal´e. (Eukleid´es: Stoicheia), IX.36 D˚ ukaz. Seˇctˇeme vˇsechny vlastn´ı dˇelitele ˇc´ısla 2p−1 (2p − 1): (1 + 2 + · · · + 2p−1 ) + (1 + 2 + · · · + 2p−2 ) · (2p − 1) = =1·
2p − 1 2p−1 − 1 + (2p − 1) · = (2p − 1)2p−1 2−1 2−1
Pozn. D˚ ukaz vyuˇz´ıv´a jednoznaˇcnosti rozkladu.
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Vˇ eta. Jestliˇze je 2p − 1 prvoˇc´ıslo, pak je 2p−1 (2p − 1) ˇc´ıslo dokonal´e. (Eukleid´es: Stoicheia), IX.36 D˚ ukaz. Seˇctˇeme vˇsechny vlastn´ı dˇelitele ˇc´ısla 2p−1 (2p − 1): (1 + 2 + · · · + 2p−1 ) + (1 + 2 + · · · + 2p−2 ) · (2p − 1) = =1·
2p − 1 2p−1 − 1 + (2p − 1) · = (2p − 1)2p−1 2−1 2−1
Pozn. D˚ ukaz vyuˇz´ıv´a jednoznaˇcnosti rozkladu.
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Vˇ eta. Jestliˇze je 2p − 1 prvoˇc´ıslo, pak je 2p−1 (2p − 1) ˇc´ıslo dokonal´e. (Eukleid´es: Stoicheia), IX.36 D˚ ukaz. Seˇctˇeme vˇsechny vlastn´ı dˇelitele ˇc´ısla 2p−1 (2p − 1): (1 + 2 + · · · + 2p−1 ) + (1 + 2 + · · · + 2p−2 ) · (2p − 1) = =1·
2p − 1 2p−1 − 1 + (2p − 1) · = (2p − 1)2p−1 2−1 2−1
Pozn. D˚ ukaz vyuˇz´ıv´a jednoznaˇcnosti rozkladu. L. Euler: Vˇsechna sud´a dokonal´a ˇc´ısla maj´ı v´yˇse uveden´y tvar.
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Vˇ eta. Kaˇzd´e sud´e dokonal´e ˇc´ıslo m´a tvar 2p−1 (2p − 1), kde 2p − 1 je prvoˇc´ıslo.
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Vˇ eta. Kaˇzd´e sud´e dokonal´e ˇc´ıslo m´a tvar 2p−1 (2p − 1), kde 2p − 1 je prvoˇc´ıslo. D˚ ukaz. Uvaˇzujme sud´e dokonal´e ˇc´ıslo n = 2m−1 · q, kde m > 1 a q je lich´e. Souˇcet vˇsech dˇelitel˚ u ˇc´ısla n je 2m · q = (1 + 2 + · · · + 2m−1 ) · S, kde S je souˇcet vˇsech dˇelitel˚ u ˇc´ısla q. Odtud 2m · q = (2m − 1) · S, proto S = 2m · x. D´ale je tedy q = (2m − 1) · x. Pokud by bylo x 6= 1, byl by souˇcet S vˇsech dˇelitel˚ u ˇc´ısla q (2m − 1) · x + (2m − 1) + x + · · · > S = 2m · x. Proto je x = 1 a q = 2m − 1 je prvoˇc´ıslo.
J. Beˇ cv´ aˇr
Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
D˚ usledek. Existuje vz´ajemnˇe jednoznaˇcn´a korespondence mezi sud´ymi dokonal´ymi ˇc´ısly a prvoˇc´ısly tvaru 2p − 1.
Podstatnou roli tedy hraj´ı prvoˇc´ısla tvaru 2p − 1.
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
D˚ usledek. Existuje vz´ajemnˇe jednoznaˇcn´a korespondence mezi sud´ymi dokonal´ymi ˇc´ısly a prvoˇc´ısly tvaru 2p − 1.
Podstatnou roli tedy hraj´ı prvoˇc´ısla tvaru 2p − 1. Otevˇren´ y probl´ em: Nev´ıme, zda existuje nˇejak´e lich´e dokonal´e ˇc´ıslo.
Muselo by b´yt vˇetˇs´ı neˇz 10300 a m´ıt v´ıce neˇz 8 prvoˇcinitel˚ u. Nyn´ı jsou jiˇz jistˇe nalezeny tvrdˇs´ı podm´ınky.
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Mersennova prvoˇc´ısla Def. Mersennov´ym ˇc´ıslem, resp. prvoˇc´ıslem rozum´ıme pˇrirozen´e ˇc´ıslo, resp. prvoˇc´ıslo tvaru 2m − 1.
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Mersennova prvoˇc´ısla Def. Mersennov´ym ˇc´ıslem, resp. prvoˇc´ıslem rozum´ıme pˇrirozen´e ˇc´ıslo, resp. prvoˇc´ıslo tvaru 2m − 1. Vˇ eta. Je-li 2m − 1 prvoˇc´ıslo, je m prvoˇc´ıslo.
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Mersennova prvoˇc´ısla Def. Mersennov´ym ˇc´ıslem, resp. prvoˇc´ıslem rozum´ıme pˇrirozen´e ˇc´ıslo, resp. prvoˇc´ıslo tvaru 2m − 1. Vˇ eta. Je-li 2m − 1 prvoˇc´ıslo, je m prvoˇc´ıslo.
D˚ ukaz. Pokud je ˇc´ıslo m sloˇzen´e, je m = ab, kde 1 < a, b < m. Potom je 2m − 1 = 2ab − 1 = (2a − 1)(2a(b−1) + 2a(b−2) + · · · + 2a + 1). Protoˇze je 1 < 2a − 1 < 2m − 1, je ˇc´ıslo 2m − 1 sloˇzen´e.
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Mersennova prvoˇc´ısla Def. Mersennov´ym ˇc´ıslem, resp. prvoˇc´ıslem rozum´ıme pˇrirozen´e ˇc´ıslo, resp. prvoˇc´ıslo tvaru 2m − 1. Vˇ eta. Je-li 2m − 1 prvoˇc´ıslo, je m prvoˇc´ıslo.
D˚ ukaz. Pokud je ˇc´ıslo m sloˇzen´e, je m = ab, kde 1 < a, b < m. Potom je 2m − 1 = 2ab − 1 = (2a − 1)(2a(b−1) + 2a(b−2) + · · · + 2a + 1). Protoˇze je 1 < 2a − 1 < 2m − 1, je ˇc´ıslo 2m − 1 sloˇzen´e.
Pozn. Opaˇcn´a implikace neplat´ı, neboˇt 211 − 1 = 2047 = 23 · 89. P´ıˇseme Mm = 2m − 1.
J. Beˇ cv´ aˇr
Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Marin Mersenne (1588–1648), francouzsk´y mnich (minorita), poˇstovn´ı schr´anka, ... Historik Henri Bosmans (1852–1928): Informer Mersenne d’une d´ecouverte, c’´etait la publier par l’Europe enti`ere.
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Marin Mersenne (1588–1648), francouzsk´y mnich (minorita), poˇstovn´ı schr´anka, ... Historik Henri Bosmans (1852–1928): Informer Mersenne d’une d´ecouverte, c’´etait la publier par l’Europe enti`ere. Vu ´vodu spisu Cogitata physico-mathematica (Paris, 1644) Mersenne uvedl, ˇze v intervalu od 1 do 257 jsou prvoˇc´ısly M2 , M3 , M5 , M7 , M13 , M17 , M19 , M31 , M67 , M127 , M257 .
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Marin Mersenne (1588–1648), francouzsk´y mnich (minorita), poˇstovn´ı schr´anka, ... Historik Henri Bosmans (1852–1928): Informer Mersenne d’une d´ecouverte, c’´etait la publier par l’Europe enti`ere. Vu ´vodu spisu Cogitata physico-mathematica (Paris, 1644) Mersenne uvedl, ˇze v intervalu od 1 do 257 jsou prvoˇc´ısly M2 , M3 , M5 , M7 , M13 , M17 , M19 , M31 , M67 , M127 , M257 . Chyby: M67 , M257 – nejsou prvoˇc´ısla, M61 , M89 , M107 – jsou prvoˇc´ısla. 1903 – F. Nelson Cole: ˇc´ıslo M67 je sloˇzen´e – dramatick´e vystoupen´ı na zased´an´ı AMS J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Otevˇren´y probl´em: je Mersennov´ych prvoˇc´ısel koneˇcnˇe nebo nekoneˇcnˇe mnoho? • Do roku 1950 bylo zn´amo 12 Mersennov´ych prvoˇc´ısel • Roku 1951 bylo nejvˇetˇs´ı zn´am´e prvoˇc´ıslo (39 cifer) M127 = 170 141 183 460 469 231 731 687 303 715 884 105 727
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Otevˇren´y probl´em: je Mersennov´ych prvoˇc´ısel koneˇcnˇe nebo nekoneˇcnˇe mnoho? • Do roku 1950 bylo zn´amo 12 Mersennov´ych prvoˇc´ısel • Roku 1951 bylo nejvˇetˇs´ı zn´am´e prvoˇc´ıslo (39 cifer) M127 = 170 141 183 460 469 231 731 687 303 715 884 105 727 • Do roku 2000 bylo zn´amo 38 Mersennov´ych prvoˇc´ısel • Nyn´ı je zn´amo 48 Mersennov´ych prvoˇc´ısel
ˇ ıslo M1 257 787 m´a 378 632 cifer (1996). C´ – Vyuˇzit´ı pˇri zkouˇsk´ach!
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Otevˇren´y probl´em: je Mersennov´ych prvoˇc´ısel koneˇcnˇe nebo nekoneˇcnˇe mnoho? • Do roku 1950 bylo zn´amo 12 Mersennov´ych prvoˇc´ısel • Roku 1951 bylo nejvˇetˇs´ı zn´am´e prvoˇc´ıslo (39 cifer) M127 = 170 141 183 460 469 231 731 687 303 715 884 105 727 • Do roku 2000 bylo zn´amo 38 Mersennov´ych prvoˇc´ısel • Nyn´ı je zn´amo 48 Mersennov´ych prvoˇc´ısel
ˇ ıslo M1 257 787 m´a 378 632 cifer (1996). C´ – Vyuˇzit´ı pˇri zkouˇsk´ach! ˇ ıslo M74 207 281 m´a 22 338 618 cifer (2016). C´
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Otevˇren´y probl´em: je Mersennov´ych prvoˇc´ısel koneˇcnˇe nebo nekoneˇcnˇe mnoho? • Do roku 1950 bylo zn´amo 12 Mersennov´ych prvoˇc´ısel • Roku 1951 bylo nejvˇetˇs´ı zn´am´e prvoˇc´ıslo (39 cifer) M127 = 170 141 183 460 469 231 731 687 303 715 884 105 727 • Do roku 2000 bylo zn´amo 38 Mersennov´ych prvoˇc´ısel • Nyn´ı je zn´amo 48 Mersennov´ych prvoˇc´ısel
ˇ ıslo M1 257 787 m´a 378 632 cifer (1996). C´ – Vyuˇzit´ı pˇri zkouˇsk´ach! ˇ ıslo M74 207 281 m´a 22 338 618 cifer (2016). C´
Neuvˇ eˇriteln´ y pokrok! J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
´ Francois Edouard Anatole Lucas (1842–1891), francouzsk´y dˇelostˇreleck´y d˚ ustojn´ık, gymnazi´aln´ı profesor. Nalezl test pro zjiˇstˇen´ı prvoˇc´ıselnosti Mersennov´ych ˇc´ısel.
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
´ Francois Edouard Anatole Lucas (1842–1891), francouzsk´y dˇelostˇreleck´y d˚ ustojn´ık, gymnazi´aln´ı profesor. Nalezl test pro zjiˇstˇen´ı prvoˇc´ıselnosti Mersennov´ych ˇc´ısel. Derrick Henry Lehmer (1905–1991) test zaˇc´atkem 30. let vytˇr´ıbil. Definujme rekurentnˇe posloupnost {Sn }: S1 = 4, Sn+1 = Sn2 − 2 pro kaˇzd´e n ≥ 1. Je tedy: S1 = 4, S2 = 14, S3 = 194, S4 = 37 634, S5 = 1 416 317 954, S6 = 2 005 956 546 822 746 114, ...
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
´ Francois Edouard Anatole Lucas (1842–1891), francouzsk´y dˇelostˇreleck´y d˚ ustojn´ık, gymnazi´aln´ı profesor. Nalezl test pro zjiˇstˇen´ı prvoˇc´ıselnosti Mersennov´ych ˇc´ısel. Derrick Henry Lehmer (1905–1991) test zaˇc´atkem 30. let vytˇr´ıbil. Definujme rekurentnˇe posloupnost {Sn }: S1 = 4, Sn+1 = Sn2 − 2 pro kaˇzd´e n ≥ 1. Je tedy: S1 = 4, S2 = 14, S3 = 194, S4 = 37 634, S5 = 1 416 317 954, S6 = 2 005 956 546 822 746 114, ... Lucas˚ uv-Lehmer˚ uv test. Pro lich´e prvoˇc´ıslo p plat´ı: Mp je prvoˇc´ıslo pr´avˇe tehdy, kdyˇz Mp dˇel´ı Sp−1 .
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
´ Francois Edouard Anatole Lucas (1842–1891), francouzsk´y dˇelostˇreleck´y d˚ ustojn´ık, gymnazi´aln´ı profesor. Nalezl test pro zjiˇstˇen´ı prvoˇc´ıselnosti Mersennov´ych ˇc´ısel. Derrick Henry Lehmer (1905–1991) test zaˇc´atkem 30. let vytˇr´ıbil. Definujme rekurentnˇe posloupnost {Sn }: S1 = 4, Sn+1 = Sn2 − 2 pro kaˇzd´e n ≥ 1. Je tedy: S1 = 4, S2 = 14, S3 = 194, S4 = 37 634, S5 = 1 416 317 954, S6 = 2 005 956 546 822 746 114, ... Lucas˚ uv-Lehmer˚ uv test. Pro lich´e prvoˇc´ıslo p plat´ı: Mp je prvoˇc´ıslo pr´avˇe tehdy, kdyˇz Mp dˇel´ı Sp−1 . Pˇr´ıklady. M5 = 31 je prvoˇc´ıslo pr´avˇe tehdy, kdyˇz 31 dˇel´ı S4 = 37 634. M7 = 127 je prvoˇc´ıslo pr´avˇe tehdy, kdyˇz 127 dˇel´ı S6 = 2 005 956 546 822 746 114. J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Mersennova prvoˇ c´ısla
Dokonal´ aˇ c´ısla
D˚ ukazy beze slov
√ √ Lemma. Poloˇzme w = 2 + 3, w = 2 − 3. Potom je w + w = 4, w · w = 1.
Pro kaˇzd´e n je
n−1
Sn = w 2
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
n−1
+ w2
.
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Mersennova prvoˇ c´ısla
Dokonal´ aˇ c´ısla
D˚ ukazy beze slov
√ √ Lemma. Poloˇzme w = 2 + 3, w = 2 − 3. Potom je w + w = 4, w · w = 1.
Pro kaˇzd´e n je
n−1
n−1
Sn = w 2
+ w2
.
D˚ ukaz indukc´ı. 1. Pro n = 1 je S1 = w + w = 4. 2. Pˇredpokl´adejme, ˇze tvrzen´ı plat´ı pro n, dokaˇzme jeho platnost pro n + 1. n−1
n−1
+ w2
Sn+1 = Sn2 − 2 = (w 2 n
n
n−1
= w 2 + w 2 + 2w 2 J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
)2 − 2 =
n−1
w2
n
n
− 2 = w 2 + w 2 . Q.e.d.
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Mersennova prvoˇ c´ısla
Dokonal´ aˇ c´ısla
D˚ ukazy beze slov
D˚ ukaz jedn´ e implikace L-L testu. Pˇredpokl´adejme ˇze Mp = 2p − 1 dˇel´ı Sp−1 . Podle lemmatu je p−2
Sp−1 = w 2 p−2
Po vyn´asoben´ı w 2 p−1
w2
p−2
+ w2
= R · Mp .
dostaneme p−2
= w2
· R · Mp − 1 = A · Mp − 1
a po umocnˇen´ı p
w 2 = (A · Mp − 1)2 = B · Mp + 1. Pˇredpokl´adejme, ˇze je Mp sloˇzen´e a q je nejmenˇs´ı prvoˇc´ıslo, kter´e Mp dˇel´ı, potom q 2 ≤ Mp . J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Mersennova prvoˇ c´ısla
Dokonal´ aˇ c´ısla
D˚ ukazy beze slov
Uvaˇzujme mnoˇzinu √ {a + b 3 ; a, b ∈ Zq }, kter´a m´a q 2 prvk˚ u. Jej´ı prvky sˇc´ıt´ame a n´asob´ıme (podobnˇe jako komplexn´ı ˇc´ısla). Uvaˇzujme vˇsechny invertibiln´ı prvky t´eto mnoˇziny. Je jich nejv´yˇse q 2 − 1 a tvoˇr´ı grupu. √ V t´eto grupˇe je prvek w = 2 + 3 prvkem ˇr´adu 2p , neboˇt p
w 2 = 1,
p−1
w2
6= 1
ˇ ad prvku je nejv´yˇse roven ˇr´adu grupy, proto (viz v´yˇse). R´ 2p ≤ q 2 − 1 < Mp = 2p − 1
– spor.
Dok´azali jsme tedy, ˇze kdyˇz Mp = 2p − 1 dˇel´ı Sp−1 , pak je Mp prvoˇc´ıslo. J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
V´ yhodn´ a modifikace L-L testu. Pro lich´e prvoˇc´ıslo p definujme posloupnost {Rn }: R1 = 4,
Rn+1 je zbytek pˇri dˇelen´ı ˇc´ısla Rn2 − 2 ˇc´ıslem Mp . Potom je Mp prvoˇc´ıslem pr´avˇe tehdy, kdyˇz Mp dˇel´ı Rp−1 .
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
V´ yhodn´ a modifikace L-L testu. Pro lich´e prvoˇc´ıslo p definujme posloupnost {Rn }: R1 = 4,
Rn+1 je zbytek pˇri dˇelen´ı ˇc´ısla Rn2 − 2 ˇc´ıslem Mp . Potom je Mp prvoˇc´ıslem pr´avˇe tehdy, kdyˇz Mp dˇel´ı Rp−1 . D˚ ukaz. Zvaˇzme dˇelitelnost ˇc´ısel Sn a Sn+1 ˇc´ıslem X . Je-li Sn = aX + q, je Sn+1 = Sn2 − 2 = (a2 X 2 + 2aXq) + q 2 − 2
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Q. e. d.
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
V´ yhodn´ a modifikace L-L testu. Pro lich´e prvoˇc´ıslo p definujme posloupnost {Rn }: R1 = 4,
Rn+1 je zbytek pˇri dˇelen´ı ˇc´ısla Rn2 − 2 ˇc´ıslem Mp . Potom je Mp prvoˇc´ıslem pr´avˇe tehdy, kdyˇz Mp dˇel´ı Rp−1 . D˚ ukaz. Zvaˇzme dˇelitelnost ˇc´ısel Sn a Sn+1 ˇc´ıslem X . Je-li Sn = aX + q, je Sn+1 = Sn2 − 2 = (a2 X 2 + 2aXq) + q 2 − 2
Q. e. d.
Posloupnost {Sn } prudce roste:
S1 = 4, S2 = 14, S3 = 194, S4 = 37 634, S5 = 1 416 317 954, S6 = 2 005 956 546 822 746 114, ... Posloupnost {Rn } neroste; pro kaˇzd´e p je vˇsak jin´a. J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Pˇr´ıklady. p = 5: M5 = 31 – prvoˇc´ıslo: R1 = 4, R2 = 14, R3 = 8, R4 = 0.
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Pˇr´ıklady. p = 5: M5 = 31 – prvoˇc´ıslo: R1 = 4, R2 = 14, R3 = 8, R4 = 0. p = 7: M7 = 127 – prvoˇc´ıslo: R1 = 4, R2 = 14, R3 = 67, R4 = 42, R5 = 111, R6 = 0.
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Pˇr´ıklady. p = 5: M5 = 31 – prvoˇc´ıslo: R1 = 4, R2 = 14, R3 = 8, R4 = 0. p = 7: M7 = 127 – prvoˇc´ıslo: R1 = 4, R2 = 14, R3 = 67, R4 = 42, R5 = 111, R6 = 0. p = 11: M11 = 2047 – nen´ı prvoˇc´ıslo: R1 = 4, R2 = 14, R3 = 194, R4 = 788, R5 = 701, R6 = 119, R7 = 1 877, R8 = 240, R9 = 282, R10 = 1 736.
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Pˇr´ıklady. p = 5: M5 = 31 – prvoˇc´ıslo: R1 = 4, R2 = 14, R3 = 8, R4 = 0. p = 7: M7 = 127 – prvoˇc´ıslo: R1 = 4, R2 = 14, R3 = 67, R4 = 42, R5 = 111, R6 = 0. p = 11: M11 = 2047 – nen´ı prvoˇc´ıslo: R1 = 4, R2 = 14, R3 = 194, R4 = 788, R5 = 701, R6 = 119, R7 = 1 877, R8 = 240, R9 = 282, R10 = 1 736. L-L test se vyuˇz´ıv´a k hled´an´ı dalˇs´ıch Mp pomoc´ı poˇc´ıtaˇc˚ u.
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
D˚ ukazy beze slov Vhodn´ e t´ ema pro ˇskolskou matematiku Ukazuj´ı kr´asu matematiky, zejm´ena geometrie. Propojuj´ı jednotliv´e discipl´ıny. Mohou okouzlit a inspirovat. Mohou z´ıskat sympatie k matematice. D´ıvej se (a pˇrem´ yˇslej)! Knihy i webov´e str´anky na t´ema d˚ ukazy beze slov. Mathematics Magazine: ok´enko Proof without Words
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Hippokratovy mˇ es´ıˇ cky Hippokrat´es z Chiu (asi 450 aˇz 400), ˇreck´y matematik
Obsah modr´ych mˇes´ıˇck˚ u je roven obsahu ˇzlut´eho troj´ uheln´ıka. J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Archim´ ed˚ uv arbelos Archim´ed´es ze Syr´ak´ us (287–212)
Obsah modr´eho u ´tvaru ohraniˇcen´eho tˇremi polokruˇznicemi ... J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
... je roven obsahu ˇzlut´eho kruhu.
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Archim´ ed˚ uv s´ alos, sal´ınon
Obsah modr´eho u ´tvaru ohraniˇcen´eho ˇctyˇrmi polokruˇznicemi ...
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
... je roven obsahu ˇzlut´eho kruhu.
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
V´ yˇsky v troj´ uheln´ıku se prot´ınaj´ı v jednom bodˇ e
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
V´ yˇsky v troj´ uheln´ıku se prot´ınaj´ı v jednom bodˇ e
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Souˇ cet geometrick´ e ˇrady
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Souˇ cet geometrick´ e ˇrady
Troj´ uheln´ıky PQR a TSP jsou podobn´e. 1 + r + r2 + · · · = J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
1 1−r
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Souˇ cet obsah˚ uˇ ctverc˚ u nad u ´seky libovolnˇ e zvolen´ ych kolm´ ych tˇ etiv je konstantn´ı.
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Reciprok´ a Pythagorova vˇ eta: 1 2 a
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
+
1 2 b
=
1 2 h
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Reciprok´ a Pythagorova vˇ eta: 1 2 a
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
+
1 2 b
=
1 2 h
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Pˇrejdeme k podobn´emu troj´ uheln´ıku:
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Mersennova prvoˇ c´ısla
1:
D˚ ukazy beze slov
1 ab
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Pˇrejdeme k podobn´emu troj´ uheln´ıku:
1:
1 ab
Obsah: J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
D˚ ukazy beze slov
Mersennova prvoˇ c´ısla
1 2 ab
= 21 ch
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Obsah pravo´ uhl´ eho troj´ uheln´ıka: K = xy
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
Obsah pravo´ uhl´ eho troj´ uheln´ıka: K = xy
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
ˇ Ctverec vepsan´ y do polokruˇ znice a kruˇ znice
2:5
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
´ Uvod
Prvoˇ c´ısla
Dokonal´ aˇ c´ısla
Mersennova prvoˇ c´ısla
D˚ ukazy beze slov
ˇ Ctverec vepsan´ y do polokruˇ znice a kruˇ znice
2:5
J. Beˇ cv´ aˇr Chv´ ala d˚ ukaz˚ u
Katedra didaktiky matematiky, Matematicko-fyzik´ aln´ı fakulta UK, Praha
