Wolstenholmeova věta

Wolstenholmeův teorém říká , že pro jakékoli prvočíslo je srovnání $p>3$

{\binom {2p}{p}}\equiv 2{\pmod {p^{3}}},

kde je průměrný binomický koeficient . Ekvivalentní srovnání $\textstyle {\binom {2p}{p}}$

{\binom {ap}{bp}}\equiv {\binom {a}{b}}{\pmod {p^{3}}}.

Složená čísla , která splňují Wolstenholmovu větu, jsou neznámá a existuje hypotéza, že neexistují. Prvočísla, která vyhovují podobnému modulovému srovnání , se nazývají Wolstenholmova prvočísla . ${\displaystyle p^{4))$

Historie

Tato věta byla poprvé prokázána Josephem Wolstenholmem v roce 1862 . V roce 1819 prokázal Charles Babbage podobnou modulovou kongruenci , což platí pro všechna prvočísla p . Druhá formulace Wolstenholmova teorému byla dána JWL Glaisherem pod vlivem Lukeova teorému . $p^{2}$

Jak sám Wolstenholm uvedl, jeho věta byla získána pomocí dvojice srovnání s (zobecněnými) harmonickými čísly :

1+{\frac {1}{2}}+{\frac {1}{3}}+\tečky +{\frac {1}{p-1}}\equiv 0{\pmod {p ^{2}}},

1+{\frac {1}{2^{2}}}+{\frac {1}{3^{2}}}+\tečky +{\frac {1}{(p-1) ^{2}}}\equiv 0{\pmod {p}}.

Jednoduchý Wolstenholm

Prvočíslo p se nazývá Wolstenholmeovo prvočíslo právě tehdy, když :

{\binom {2p}{p}}\equiv 2{\pmod {p^{4}}}.

Zatím jsou známy pouze 2 jednoduché Wolstenholmy: 16843 a 2124679 (sekvence A088164 v OEIS ); ostatní jsou tak prvotřídní, pokud existují, jsou lepší než . $10^{9}$

Pravděpodobně se chová jako pseudonáhodné číslo rovnoměrně rozložené v intervalu . Heuristicky se předpokládá, že počet Wolstenholmeových prvočísel v intervalu je odhadován jako . Z těchto heuristických úvah vyplývá, že další Wolstenholmovo prvočíslo leží mezi a . $\textstyle {\frac {{\binom {2p}{p}}-2}{p^{3}}}\mod p$ $[0,p-1]$ $(K,N)$ $\ln \ln N-\ln \ln K$ $10^{9}$ $10^{{24}}$

Podobné heuristické argumenty říkají, že neexistují žádná prvočísla, pro která by se srovnání provedlo modulo . $p^{5}$

Důkaz

Existuje několik způsobů, jak dokázat Wolstenholmovu větu.

Kombinatoricko-algebraický důkaz

Zde je Glashierův důkaz pomocí kombinatoriky a algebry .

Nechť p je prvočíslo, a , b nezáporná celá čísla. Nechť , , je množina prvků a p rozdělených na kruhy o délce p . Na každý prstenec působí skupina rotací . Skupina tak působí na celek A. Nechť B je libovolná podmnožina množiny A prvků b·p . Sada B může být zvolena různými způsoby. Každá orbita množiny B při působení grupy obsahuje prvky, kde k je počet dílčích průsečíků B s prstenci . Existují dráhy délky 1 a žádné dráhy délky p . Dostáváme tedy Babbageovu větu: $A=(a_{{ij}})$ $i=1,\tečky ,a$ $j=1,\tečky ,p$ $K_{i}=(a_{ij})$ $j=1,\tečky ,p$ ${\displaystyle C_{p}\cong \mathbb {Z} _{p))$ $\mathbb {Z} _{p}^{a}$ $\textstyle {\binom {ap}{bp))$ $\mathbb {Z} _{p}^{a}$ $p^{k}$ $K_{i}$ $\textstyle {\binom {a}{b))$

{\binom {ap}{bp}}\equiv {\binom {a}{b}}{\pmod {p^{2}}}.

Eliminujeme oběžné dráhy délky , dostáváme $p^{2}$

{\binom {ap}{bp}}\equiv {\binom {a}{b}}+{\binom {a}{2}}\left({\binom {2p}{p}}- 2\right){\binom {a-2}{b-1}}{\pmod {p^{3}}}.

Kromě jiných posloupností nám toto srovnání v případě dává obecný případ druhé formy Wolstenholmovy věty. $a=2$ $b=1$

Přecházíme z kombinatoriky na algebru a aplikujeme polynomické uvažování. Fixováním b získáme srovnání s polynomy v a na obou stranách, což platí pro jakékoli nezáporné a . Porovnání tedy platí pro jakékoli celé číslo a . Konkrétně pro , získáme srovnání: $a=-1$ $b=1$

{\binom {-p}{p}}\equiv {\binom {-1}{1}}+{\binom {-1}{2}}\left({\binom {2p}{p }}-2\right){\pmod {p^{3}}}.

Protože

{\binom {-p}{p}}={\frac {(-1)^{p}}{2}}{\binom {2p}{p}},

pak

3{\binom {2p}{p}}\equiv 6{\pmod {p^{3}}}.

Pro rušíme do 3 a důkaz je kompletní. $p\neq 3$

Podobné srovnání modulů : ${\displaystyle p^{4))$

{\binom {ap}{bp}}\equiv {\binom {a}{b}}{\pmod {p^{4}}}

pro všechna přirozená čísla a , b platí právě tehdy, když , , tedy právě tehdy, když p je Wolstenholmovo prvočíslo. $a=2$ $b=1$

Číselný teoretický důkaz

Představme si binomický koeficient jako poměr faktoriálů , zrušme p ! a zrušte p v binomickém koeficientu a posuňte čitatel na pravou stranu, dostaneme:

{\displaystyle \prod \limits _{k=1}^{p-1}\equiv (p-1)!{\pmod {p^{3))))

Levá strana je polynom v p , vynásobte závorky a ve výsledném polynomu zahoďte mocniny p větší než 3, dostaneme:

{\displaystyle a_{2}p^{2}+a_{1}p+(p-1)!\equiv (p-1)!{\pmod {p^{3))))

Také zrušíme mocninu p spolu s modulem a pak na : $(p-1)!$ $(p-1)!$

{\displaystyle a_{2}p+a_{1}\equiv 0{\pmod {p^{2))))

všimněte si, že

a_{1}=\sum \limits _{k=1}^{p-1}{\frac {1}{k)),

a_{2}=\sum \limits _{1\leq i<j\leq p-1}{\frac {1}{ij)).

Nechť je bijekce a automorfismus . Pak $T:x\mapsto gx$ ${\displaystyle \mathbb {Z} _{p}^{+))$ ${\mathbb {Z}}_{p}^{{\times }}$

a_{2}=\sum \limits _{1\leq i<j\leq p-1}{\frac {1}{ij))\equiv \sum \limits _{1\leq i<j \leq p-1}{\frac {1}{T(i)T(j)}}={\frac {1}{g^{2}}}={\frac {a_{2}}{g ^{2))}{\pmod {p)),

což znamená . $a_{2}\equiv 0{\pmod {p))$

Konečně,

a_{1}\equiv 0{\pmod {p^{2}}}\Leftrightarrow 2a_{1}\equiv 0{\pmod {p^{2}}}

2a_{1}=\sum \limits _{k=1}^{p-1}\left({\frac {1}{k))+{\frac {1}{pk))\right )=-p\sum \limits _{k=1}^{p-1}{\frac {1}{k^{2}}}\equiv 0{\pmod {p^{2}}},

protože

\sum \limits _{k=1}^{p-1}{\frac {1}{k^{2}}}\equiv \left(\sum \limits _{k=1}^{ p-1}{\frac {1}{k}}\right)^{2}-a_{2}\equiv 0{\pmod {p}}

Tím je věta dokázána.

Zobecnění

Platí i obecnější tvrzení:

{\binom {ap^{n}}{bp^{n}}}\equiv {\binom {ap^{n-1}}{bp^{n-1}}}{\pmod {p ^{3n}}}

Převrácení věty jako domněnka

Tvrzení obrácené k Wolstenholmeově větě je hypotéza, a to, pokud:

{\binom {2n}{n}}\equiv 2{\pmod {n^{k}}},

pro k = 3, pak n je prvočíslo. Tato hodnota k je minimum, pro které neexistují žádná známá složená srovnávací řešení:

pro k = 1 vyhovují srovnání kromě prvočísel i čísla tvořící posloupnost A082180 v OEIS ; mezi nimi jsou druhé mocniny prvočísel a několik složených čísel (první netriviální lichý příklad: n = 27173 = 29 937).
pro k = 2, druhé mocniny Wolstenholmových prvočísel vyhovují srovnání (avšak složená čísla, která nejsou mocninami prvočísel, která vyhovují takovému srovnání, nejsou známa).

Pokud složené číslo vyhovuje srovnání, pak z toho nevyplývá, že

{\binom {an}{bn}}\equiv {\binom {a}{b}}{\pmod {n^{k}}}.

I když je obrácení Wolstenholmovy věty pravdivé, je obtížné jej použít jako test primality , protože neexistuje žádný známý způsob, jak vypočítat modulo binomický koeficient v polynomiálním čase . Na druhou stranu, je-li pravda, obrácení Wolstenholmovy věty může být užitečné pro konstrukci diofantinské reprezentace prvočísel (viz Hilbertův desátý problém ), stejně jako například Wilsonova věta . ${\tbinom {2n}{n))$ $\textstyle n^{3}$

Viz také

Poznámky

Odkazy

Babbage, C. (1819), Demonstration of a teorem related to prvočísla , The Edinburgh philosophical journal vol . 1: 46–49 , < https://books.google.com/books?id=KrA-AAAAYAAJ&pg=PA46 >
Wolstenholme, J. (1862), O určitých vlastnostech prvočísel , The Quarterly Journal of Pure and Applied Mathematics vol . 5: 35–39 , < https://books.google.com/books?id=vL0KAAAAIAAJ&pg=PA35 >
McIntosh, RJ (1995), On the converse of Wolstenholme's teorem , Acta Arithmetica vol . 71(4): 381–389 , < http://matwbn.icm.edu.pl/ksiazki/aa/aa71/aa7144.pdf >
E. B. Vinberg, „Překvapivé aritmetické vlastnosti binomických koeficientů“, Mat. osvícení, ser. 3, 12, Nakladatelství MCNMO, M., 2008, 33-42
The Prime Glossary: Wolstenholme Prime
Stav hledání prvočísel Wolstenholme