Posted By: Lumo (** Lumidek **) on 'CZscience'
Title: Re: Mersennova prvocisla
Date: Sat Dec 13 01:36:15 1997
> Nazdarek all,
>
> prave jsem koukal po http://www.mersenne.org/prime.htm a nejvetsi zname
> prvocislo je 2^2976221-1, coz je cislo majici milion!!! cislic. Mne pripada,
> ze slozitost je linearni, coz by znamenalo IMHO 2^100.000 (pocita se do
> odmocniny a nektera cisla - suda apod. - muzeme rovnou vyloucit) operaci.
> Neco mi nehraje... Neporadite mi co to je?
Tentokrat ti neporadime uplne presne a exaktne, protoze prece jen nejsme
teoretik cisel :-)). Nicmene Ti lze jiste poradit v obecnem ramci. Vysvetleni
Tveho podivu se zcela zjevne opira o nazor, ze jediny zpusob poznani je hruba
sila. ;-)) Proc si myslis, ze na zjisteni, zda je cislo tvaru 2^x-1
prvocislo, musis prozkoumat jeho delitelnost opravdu cimkoliv? ;-)
Prirovnani udelam drasticke, ale zato snad pusobive. Predstav si, ze chces
zjistit, zda cislo se sto tisici cislicemi je delitelne sedmi - a nekdo
proste zacne pocitat zbytek tak, ze si bude odpocitavat
1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3,4,5,6... a zaroven bude dane ohromne cislo
zmensovat o jednicku. Zjevne mu to bude trvat radove 10^100000 operaci.
Znamena to, ze rychleji to nejde? ;-) (Ja to umim radove po 100000 operacich.)
Obecne cisla tvaru 2^x-1 jsou prvocisla velmi casto. Rekneme si par prvnich:
x = 1,2,3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 ...
1,3,7,15,31,63,127,255,511,1023,2047,4095,8191 ...
Zadne z nich zajiste neni sude, protoze jsou tvaru 2^x-1. Muzeme se podivat na
zbytek po deleni tremi. Zjevne je stridave 1,0,1,0,1,0, ... Staci tedy vzit
2^x-1 s cislem x lichym - a cislo 2^x-1 nebude delitelne tremi. Dukaz, ze
zbytky se fakt stridaji, je celkem jednoduchy: kriterium delitelnosti tremi
podle zapisu ve dvojkove soustave lze formulovat pomoci souctu dvojcisli,
protoze "11" (3), "1111" (15), "111111" (63) apod. jsou zajiste delitelne
tremi, podily jsou "1" (1), "101" (5), "10101" (21), "1010101" ...
Pojdme dal. Ctyrmi samozrejme nejsou delitelna (jsouc licha). Zbytek po deleni
peti je 1,3,2,0,1,3,2,0,1,3,2,0, ... Pokud tedy x neni delitelne ctyrmi,
2^x-1 jiste nebude delitelne peti. Dukaz analogicky: "1111" (15) je delitelne
peti, a tudiz take vsechny jeho nasobky jako "11111111", "111111111111", ...
Sestku, stejne jako vsechna dalsi slozena cisla, preskocime.
Zbytek po deleni sedmi je 1,3,0,1,3,0,1,3,0... tedy pokud neni x delitelne
tremi, 2^x-1 nemuze byt delitelne sedmi. Vsimnete si, jak rozlozitelnost x
typicky implikuje nejakou rozlozitelnost 2^x-1.
Tohle take vedlo lidi k opacne domnence, ze totiz pokud je x prvocislo, tak
take 2^x-1 je prvocislo. Tahle hypoteza sice plati velmi dlouho (ted nevim
zpameti, jaky je prvni protipriklad, ale je jim 2^11-1=2047=23.89), ovsem ne
obecne. :-) Kdyby platila obecne, slo by vzit nejvetsi zname prvocislo x a
rici, ze 2^x-1 je jeste vetsi prvocislo, ze ano... :-) Nicmene za urcitych
dodatecnych predpokladu pro cislo x, ktere se daji overit v realnem case, i
pokud x ma statisice cifer, lze tvrdit, ze 2^x-1 je prvocislo. Ale o detaily
bychom museli pozadat matematika. ;-)
///// 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!
-------------------------------------------------------------------------------