Posted By: Lumo (** Lumidek **) on 'CZscience'
Title: Dokonala cisla
Date: Sat Dec 13 21:00:03 1997
Podival jsem se na stranky prilehle strance, kterou citoval snake, a zjistil
jsem, ze je veda o Mersennovych cislech velmi zajimava, proto jsem se rozhodl
vas s jistymi jejimi piliri seznamit.
Definice: Mersennovo cislo je prvocislo tvaru 2^x-1, kde x je cele.
Perfektni cislo je cislo n, ktere se rovna souctu vsech svych
delitelu od jednicky do n-1. Spravny cesky nazev je "dokonale
cislo", dekuji snakeovi za opravu, ale zustanu u "perfektnich". :-)
Historicky komentar: drive si lide myslili, ze 2^x-1 je prvocislo pro kazde
prvocislo x. Ve skutecnosti prvnim protiprikladem je 2047=23.89. Navzdory
teto chybe, i nasledujici historie byla plna chyb. Dnes jiz jsme nastesti
jinde.
Priklady: Prvnich par Mersennovych cisel jsou cisla 2^n-1 pro
n=2,3,5,7,13,17,19,31,61,89,107,127 (zadna dalsi pro n<259)
Prvnim perfektnim cislem je 6=1+2+3, dalsi je 28=1+2+4+7+14, dale 496 (slavna
dimenze superstrunne kalibracni grupy v 10 dimenzich) a 8128. Vsimneme si, ze
vsechna tato cisla lze psat ve tvaru
2.3, 4.7, 16.31, 64.127,
(vsechna tato 4 perfektni cisla byla znama jiz pred Jeziskem Kristem)
obecne 2^(n-1) krat (2^n)-1. A vsimnete si take, ze vetsi z cisel, v prvnich
prikladech 3,7,31,127... jsou Mersennova prvocisla. Tohle plati zcela
univerzalne:
Teorem: Cislo k je sude perfektni cislo prave pokud ma tvar
2^(n-1) krat (2^n)-1 a (2^n)-1 je prvocislo!
Tento teorem prakticky znamena, ze hledani Mersennovych cisel je tyz ukol jako
hledani perfektnich cisel! Dodnes neni jasne, zda existuje liche perfektni
cislo, ale pokud existuje, je sakramentsky velike! ;-)
Take plati teorem, ktery jste mohli pochopit jiz z minuleho postu.
Teorem: Pokud je (2^n)-1 prvocislo, pak i n musi byt prvocislo.
Tenhle teorem je ve skutecnosti velmi jednoduche dokazat neprimo: pokud je n
slozene, tj. n=rs, potom
(2^n)-1 = (2^rs)-1 = (2^s)-1 krat 2^(s(r-1)) + 2^(s(r-2)) + ... + 2^(s.1) + 1
tj. i 2^n-1 je slozene. :-) Fakticky lze zaver snadno zobecnit i pro jine
zaklady nez 2 a rici, ze pokud je (a^n)-1 prvocislo, pak musi byt n prvocislo
a zaklad a se musi rovnat dvema! Tato novinka je jednoduchym dusledkem toho,
ze (a^n)-1 je vzdy delitelne (a-1) - a pokud a-1 neni jedna, dava nam to
rozklad.
Podivejme se na nase prvni ctyri perfektni cisla znovu. Jsou jimi
6,28,496,8128. Neunikne nam, ze vsechny konci (v nasi desitkove soustave) na
sestku nebo osmicku. Tohle je pry take lehke dokazat (ale pozor, pravidelne
stridani 6,8,6,8 plati jen na pocatku!). Zapis perfektnich cisel ve dvojkove
soustave (diky rozkladu na 2^n-1 krat 2^(n-1)) je kombinaci rady jednicek a
nul (nul je o jednu mene):
110
11100
111110000
1111111000000
Jeste rekneme dva teoremy i s dukazy:
Teorem: Mejme dve prvocisla p,q. Je-li 2^p-1 nasobkem q, pak q ma zbytek
po deleni osmi roven 1 ci 7 a take q=2kp+1 pro nejake cele k.
Dukaz je strucny a uziva male Fermatovy vety. Ta rika, ze a^(p-1) dava zbytek
1 po deleni p, pokud a,p jsou nesoudelna a p prvocislo. Dukaz male Fermatovy
vety je take na sest radek.
Teorem: Pro prvocislo p, ktere dava zbytek 3 po deleni ctyrmi,
je 2p+1 prvocislo prave kdyz 2^p-1 je nasobkem 2p+1.
(Dukaz je na 7 radek a vynecham ho.)
Tyhle veci vymysleli velci matematici minulosti jako Euler, Lagrange a dalsi.
Do dnesniho dne je znamo 36 Mersennovych cisel, posledni uvedl snake. Prvnich
petatricet je dokonce prave prvnich petatricet, ktera existuji, zatimco
sestatricate muze byt nejake mensi nez to zatim rekordni, protoze se prostor
mezi nim a predchozim, petatricatym, neprozkoumal dokonale. Petatricate ma
radove polovinu mist nez to zatim rekordni sestatricate.
Teorem (Lucasuv-Lehmeruv test): Pro liche p je 2^p-1 prvocislo prave tehdy,
je-li delitelem S(p-1), kde S(n) je posloupnost s S(1)=4
a s rekurzivnim pravidlem S(n+1)=S(n)^2-2.
Dukaz ma 13 radek a je moc dlouhy na to, abych ho cetl. ;-)
Zajemci viz http://www.utm.edu/research/primes/notes/proofs/LucasLehmer.html
Tuto mohutnou teorii zacal vytvaret Lucas uz kolem roku 1870. Vsimnete si, ze
vypocet muze byt skutecne efektivni... Cislo S(p) pro p radove milion je
samozrejme ohromne - ma 2^milion cislic rekneme :-)), nicmene nam staci
zjistit, zda je delitelne 2^p-1, ktere ma radove jen milion cislic. Tudiz
kdyz rekurzivne pocitame S(p), staci vlastne pocitat jeho zbytek po deleni
2^p-1, coz je zvlaste vyhodne pro pocitace delat ve dvojkove soustave, nebot
vystacime s rotovanim a scitanim.
V roce 1811 napsal Peter Barlow ve sve knize, ze 2^30.(2^31-1) je nejvetsi
perfektni cislo, ktere kdy bude objeveno, protoze nikdo nebude mit nikdy tolik
sil, aby pocital vetsi. Samozrejme, nemohl (nebo mohl!?) tusit, jak pokroci
nejen teorie, ale take technika. Hledani perfektnich cisel je zajimava hra,
ktera vzrusuje i mnohe lidi mimo, a tak neni divu, ze kdyz v roce 1963 v
Illinois objevili nove Mersennovo prvocislo, na postovnich razitkach se tehdy
objevila hlaska "2^11213-1 je prvocislo".
Myslim take, ze by historie Mersennovych prvocisel mela byt dalsim z varovani
pro lidi, kteri sebevedome prohlasuji, ze ani zbytek lidstva neni schopen
neceho docilit v oblasti vedy... ;-)
///// Superstring/M-theory is the language in which God wrote the world.
/// O __ Your Lumidek. mailto:motl@physics.rutgers.edu, motl@usa.net
/// ---------------------------------------------------
///_______/ http://www.kolej.mff.cuni.cz/~lumo/, http://www.motl.org/
Mazte zbytecne casti replikovanych prispevku - hmat CTRL/K maze celou radku!
-------------------------------------------------------------------------------