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!
-------------------------------------------------------------------------------

Search the boards