Matematické Fórum

BassCi · 22. 03. 2011 22:05

určuje Wilsonova věta jaké číslo je či není prvočíslo? Jaký má základ, výhody a zápory. A dokážeme pomocí ní nebo jiného principu určit výskyt prvočísel?

potřebuji odpovědi, abych mohl dnes usnout ;)

halogan · 22. 03. 2011 22:11

Wilson's theorem is useless as a primality test in practice, since computing (n − 1)! modulo n for large n is hard, and far easier primality tests are known.

Wilson's theorem

---

Ale ano, určuje (platí tam ekvivalence, viz odkaz), ale vzhledem k náročnosti výpočtu to není vhodné pro hledání prvočísel z množiny nabízených.

BassCi · 22. 03. 2011 22:16

právě jsem se dostal do bodu, kde mám sice vzorec, ale dělenec i dělitelem jsou sumačního charakteru, takže to yjde zatím nastejno, ne?

Matej1117

Cisto teoreticky sa da podla Wilsonovej vety na sto percent urcit, ci je dane cislo prvocislo alebo nie. Ale prakticky, keby si chcel overit velke cislo, tak nemas sancu pretoze musis urobit faktorial o 1 mensieho cisla a potom pripocitat este jednotku a ked to videlis danym cislom a ostane ti cele cislo, tak je toto cislo prvocislo. Lenze ak chces overit velke cislo, napriklad 2^100 + 1 tak nemas sancu ani s kalkulackou .. Rovnako mala fermatova veta - je to super sposob ale len teoreticky, prakticky sa s tou mocninou nevybabres ani za mesiac..

Preto som mal taky napad, ze keby sa vo wilsonovej vete (x - 1)! + 1 namiesto tej prvej jednotky dala napr. dvojka, potom by sa muselo pripocitat zrejme nieco ine ako ta jednicka a tym padom by to ulahcilo pocitanie.. a keby sa namiesto jednicky dosadila stovka a namiesto tej druhej jednocky nieco ine tak by to bolo uz tuti fruty.. takyto napad som mal uz davnejsie, aj som sa s tym hrajkal ale mam pocit ze nic take nie je uskutocnitelne .. to je skoda ale rozhodne to nevzdam :)

FailED · 17. 04. 2011 20:49 — Editoval FailED (17. 04. 2011 20:49)

↑ Matej1117:

Pozor, Malá Fermatova věta říká, že když je n prvočíslo, potom každé a splňuje $a^n\equiv a\pmod{n}$ a ne naopak. Fermatův test je jen pravděpodobnostní.

Odkaz

Matej1117

mala fermatova veta hovori, ze ak A je prirodzene cislo a P je prvocislo, tak A^P - A po deleni cislom P dava tento vyraz cele cislo. Mala fermatova veta je dokazana..

ruamaixanh · 17. 04. 2011 21:20

↑ Matej1117:
kolega FailED chce říct, že pokud platí $a^n\equiv a\pmod{n}$ pro všechna a, to ještě nemusí znamenat, že n je prvočíslo. Taková složená čísla se nazývají Carmichaelova čísla (http://en.wikipedia.org/wiki/Carmichael_number)

Matej1117 · 17. 04. 2011 21:23

ja neviem modulovat.. nemam vysku, takze ani neviem co chcel povedat, matematiku mam iba ako zalubu.. poznam iba tu verziu malej fermatovej vety, ktoru som napisal ja..

Matematické Fórum

#1 22. 03. 2011 22:05

Wilsonova věta

#2 22. 03. 2011 22:11

Re: Wilsonova věta

#3 22. 03. 2011 22:16

Re: Wilsonova věta

#4 17. 04. 2011 20:36 — Editoval Matej1117 (17. 04. 2011 20:38)

Re: Wilsonova věta

#5 17. 04. 2011 20:49 — Editoval FailED (17. 04. 2011 20:49)

Re: Wilsonova věta

#6 17. 04. 2011 21:12 — Editoval Matej1117 (17. 04. 2011 21:14)

Re: Wilsonova věta

#7 17. 04. 2011 21:20

Re: Wilsonova věta

#8 17. 04. 2011 21:23

Re: Wilsonova věta

Zápatí