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