Prothsova věta - Proths theorem - Wikipedia

v teorie čísel, Prothova věta je test primality pro Proth čísla.

Uvádí^[1][2] to když p je Proth číslo, formuláře k2ⁿ + 1 s k liché a k < 2ⁿ, a pokud existuje celé číslo A pro který

${ displaystyle a ^ { frac {p-1} {2}} equiv -1 { pmod {p}},}$

pak p je primární. V tomto případě p se nazývá a Proth prime. Toto je praktický test, protože pokud p je hlavní, jakýkoli vyvolený A má asi 50 procentní šanci pracovat.

Li A je kvadratická rezidua modulo p pak platí i konverzace a test je nezvratný. Takový A lze najít iterací A přes malé prvočísla a výpočet Jacobi symbol dokud:

${ displaystyle left ({ frac {a} {p}} right) = - 1.}$

Na rozdíl od mnoha Monte Carlo testy primality (randomizované algoritmy, které mohou vrátit a falešně pozitivní ), algoritmus testování primality založený na Prothově teorému je a Algoritmus Las Vegas, vždy vrací správnou odpověď, ale s dobou chodu, která se mění náhodně.

Numerické příklady

Příklady věty zahrnují:

• pro p = 3 = 1(2¹) + 1, máme tu 2^(3-1)/2 + 1 = 3 je dělitelné 3, takže 3 je prvočíslo.
• pro p = 5 = 1(2²) + 1, máme tu 3^(5-1)/2 + 1 = 10 je dělitelné 5, takže 5 je prvočíslo.
• pro p = 13 = 3(2²) + 1, máme 5^(13-1)/2 + 1 = 15626 je dělitelné 13, takže 13 je prvočíslo.
• pro p = 9, což není prime, není A takhle A^(9-1)/2 + 1 je dělitelné 9.

První Prothova prvočísla jsou (sekvence A080076 v OEIS ):

3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153 ….

Největší známý Proth prime od roku 2016^{[Aktualizace]} je ${ displaystyle 10223 cdot 2 ^ {31172165} +1}$a je dlouhý 9 383 761 číslic.^[3] Zjistil to Peter Szabolcs v PrimeGrid projekt distribuovaných výpočtů která to oznámila dne 6. listopadu 2016.^[4] Je to také největší známáMersenne prime a největší číslo Colberta.^[5] Druhý největší známý Proth prime je ${ displaystyle 19249 cdot 2 ^ {13018586} +1}$, nalezeno Sedmnáct nebo Busta.^[6]

Důkaz

Důkaz pro tuto větu používá Pocklington-Lehmerův test primality, a velmi se podobá důkazu Pépinův test. Důkaz najdete na stranách 52 knihy Ribenboima v referencích.

Dějiny

François Proth (1852–1879) publikoval teorém v roce 1878.^[7][8]

Viz také

• Pépinův test (zvláštní případ k = 1, kde si jeden vybere A = 3)
• Sierpinského číslo

Reference

externí odkazy

• Weisstein, Eric W. „Prothova věta“. MathWorld.