Pseudoprim

Pseudoprvo je přirozené číslo , které má některé vlastnosti prvočísel , ale je přesto složené . Existuje několik různých typů pseudoprimes, v závislosti na uvažovaných vlastnostech.

Existence pseudoprvočísel je překážkou testů prvočísel , které se pokoušejí využít určitých vlastností prvočísel k určení, zda je dané číslo prvočíslo.

Pseudosimple Farms

O složeném čísle n se říká , že je Fermatovým pseudoprvotním základem a, jestliže a a n jsou koprimé a . [jeden] $a^{n-1} \equiv 1\pmod{n}$

Fermatova pseudojednoduchá na bázi 2 tvoří sekvenci:

341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, … ( sekvence OEIS A001567 )

a v základu 3 sekvence:

91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, … ( sekvence OEIS A005935 )

Číslo, které je Fermatovo pseudoprvo v každém koprimém základu, se nazývá Carmichaelovo číslo .

Euler-Jacobi pseudosimples

Liché složené číslo n se nazývá Euler-Jacobiho pseudoprvočíslo v základu a , pokud vyhovuje srovnání [2]

a^{(n-1)/2} \equiv \left( \frac{a}{n} \right) \pmod{n},

kde je Jacobiho symbol . Protože z tohoto srovnání vyplývá, že každé Eulerovo-Jacobiho pseudojednoduché je také Fermatovo pseudojednoduché (ze stejného důvodu). $\left( \frac{a}{n}\right)$ $a^{n-1} \equiv 1\pmod{n},$

Euler-Jacobiho pseudojednoduchá v základu 2 tvoří sekvenci:

561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, 4681, 6601, 8321, 8481, 10585, … ( sekvence OEIS A047713 )

a v základu 3 sekvence:

121, 703, 1729, 1891, 2821, 3281, 7381, 8401, 8911, 10585, 12403, 15457, 15841, … ( sekvence OEIS A048950 )

Pseudojednoduchý Fibonacci

Hlavní článek: Pseudoprimární Fibonacciho číslo

Pseudojednoduchý Lucas

Hlavní článek: Lucas pseudoprime

Pseudojednoduchý Perrin

Složené číslo q se nazývá Perrinovo pseudoprvo , pokud dělí q-té Perrinovo číslo P ( q ) dané vztahem opakování :

P (0)=3, P (1)=0, P (2)=2,

P ( n ) = P ( n − 2) + P ( n − 3) pro n > 2.

Frobenius pseudosimples

Pseudoprvočíslo, které prošlo třístupňovým testem, že jde o možné prvočíslo , vyvinuté Jonem Granthamem v roce 1996. [3] [4]

Pseudosimple Catalana

Liché složené číslo n , které vyhovuje srovnání

(-1)^{\frac{n-1}{2}} \cdot C_{\frac{n-1}{2}} \equiv 2 \pmod n,

kde Cm je m - té katalánské číslo . Srovnání platí pro libovolné liché prvočíslo n .

Jsou známa pouze tři katalánská pseudoprima: 5907, 1194649 a 12327121 (sekvence A163209 v OEIS ), z nichž poslední dvě jsou Wieferichovy prvočísla . Obecně, jestliže p je Wieferichovo prvočíslo, pak p 2 je katalánské pseudoprvo.

Viz také

Poznámky

↑ Weisstein, Eric W. Fermat Pseudoprime na webu Wolfram MathWorld .
↑ Weisstein, Eric W. Euler-Jacobi Pseudoprime na webu Wolfram MathWorld .
↑ Weisstein, Eric W. Frobenius pseudoprime na webu Wolfram MathWorld .
↑ John Grantham. Frobenius pseudoprimes (anglicky) // Matematika počítání : deník. - 2001. - Sv. 70 , č. 234 . - S. 873-891 . - doi : 10.1090/S0025-5718-00-01197-2 .

Odkazy

Aebi, C.; Cairns, G. Katalánská čísla, prvočísla a dvojčata (nedefinováno) // Elemente der Mathematik. - 2008. - T. 63 , č. 4 . - S. 153-164 . - doi : 10.4171/EM/103 .
Katalánská pseudoprimes . Výzkum v oblasti vědeckých počítačů v pregraduálním vzdělávání.

Slovníky a encyklopedie	Britannica (online)