Prots sætning

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 28. februar 2017; checks kræver 6 redigeringer .

I talteorien er Proths sætning en primalitetstest for Proths tal .

Ordlyd

Proths sætning siger:

Hvis p er et Prota-tal af formen , hvor k er ulige og , så er p primtal (kaldet en Prota-primtal ), hvis og kun hvis sammenligningen foretages for en anden kvadratisk ikke-rest a : $k\cdot 2^{n}+1$ ${\displaystyle k<2^{n))$

a^{(p-1)/2}\equiv -1{\pmod {p))

Bevis

(a) Lad p være primtal. Derefter for enhver kvadratisk ikke-rest a : ved Eulers kriterium . $a^{(p-1)/2}\equiv -1{\pmod {p))$

(b) Lad for nogle kvadratiske ikke-rest a . Vi bruger Pocklington-kriteriet , hvor . Så er den eneste prime divisor . Lad os kontrollere opfyldelsen af betingelserne for kriteriet: $a^{(p-1)/2}\equiv -1{\pmod {p))$ $n=2^{k}+1$ $q=2$ $n-1$

$a^{n-1}=(a^{(n-1)/2})^{2}\equiv 1{\pmod {n))$ - udført.
tal n og coprime — færdig. $a^{(n-1)/q}-1$

Da betingelsen er opfyldt, er n primtal. [en] $2^{k}>{\sqrt {n}}-1$

Test af Proth-numre for primalitet

Proths teorem kan bruges til at teste for primaliteten af Proth-tal. Den probabilistiske testalgoritme baseret på sætningen er som følger: Et heltal vælges tilfældigt , således at og beregner . Følgende resultater er mulige: $-en$ $a\not \equiv 1{\pmod {p}}\$ $b\equiv a^{(p-1)/2}{\pmod {p}}\$

$b\equiv -1{\pmod {p}}\$ , så er primtal ved Proth-sætningen. $s$
$b\not \equiv \pm 1{\pmod {p}}\$ og , så er sammensat, da er ikke-trivielle divisors af . $b^{2}\equiv 1{\pmod {p}}\$ $s$ $gcd(b\pm 1,p)$ $s$
$b^{2}\not \equiv 1{\pmod {p}}\$ , så er p sammensat af Fermats lille sætning .
$b\equiv 1{\pmod {p}}\$ , så er testresultatet ukendt.

Udfald (4) er årsagen til, at testen er sandsynlig. I tilfælde (1) er det en kvadratisk ikke-restmodulo . Proceduren gentages, indtil enkelheden er etableret. Hvis er prime, så vil testen bekræfte dette med en sandsynlighed i én iteration, da antallet af kvadratiske ikke-rester modulo er nøjagtigt . [2] $-en$ $s$ $s$ $s$ $1/2$ $s$ $(p-1)/2$

Eksempler

for p = 3 er 2 1 + 1 = 3 et multiplum af 3, så 3 er primtal.
for p = 5 er 3 2 + 1 = 10 et multiplum af 5, så 5 er primtal.
p = 13, 5 6 + 1 = 15626 er deleligt med 13, 13 er primtal.
for p = 9, som ikke er primtal, er der ingen b , således at a 4 + 1 er deleligt med 9.

Prota primtal

Prot-primtallene danner en sekvens:

3 , 5 , 13 , 17 , 41 , 97 , 113 , 193 , 241 , 257 , 353 , 449, 577, 641, 673, 769, 929, 1153 A0) ( 8 OEIS sekvens 6 )

Fra maj 2017 er Proths største kendte prime, 10223 2 31172165 + 1, blevet fundet af Primegrid- projektet . Den har 9383761 decimalcifre og er den største kendte ikke- Mersenne primtal . [3]

Generaliseret Proths teorem

Lemma. Lad for nogle prime l og . Lad være magten af et primtal, hvor . Hvis og , så er n primtal . ${\displaystyle n=l^{k))$ $k\geqslant 1$ $r^{e}$ $r\neq l$ $r^{e}{\mathcal {j}}\phi (n)$ $r^{e}>{\sqrt {n))$

Bevis. er en divisor , så . Hvis , så er det en selvmodsigelse. Derfor , og er enkel.

r^{e}

{\displaystyle \phi (n)=(l-1)l^{k-1))

r^{e}{\mathcal {j}}l-1

k>1

\phi (n)\geqslant (l-1)l>r^{2}e>n

k=1

n

Sætning (generaliseret Proths sætning). Lad os for nogle primtal og heltal . Lad . Hvis og for et eller andet heltal , så er primtal. $N=r^{e}t+1$ $r$ $e,t\geqslant 1$ $r^{e}>t$ $a^{N-1}\equiv 1(modN)$ $a^{(N-1)/r}\ikke \equiv 1(modN)$ $-en$ $N$