Pseudoprim

Un pseudoprim este un număr natural care are unele dintre proprietățile primelor , dar este totuși compus . Există mai multe tipuri diferite de pseudoprime, în funcție de proprietățile luate în considerare.

Existența pseudoprimelor este un obstacol în calea testelor de primalitate care încearcă să folosească anumite proprietăți ale primelor pentru a determina dacă un anumit număr este prim.

Ferme pseudosimple

Se spune că un număr compus n este baza pseudoprimă a lui Fermat dacă a și n sunt coprime și . [unu] $a^{n-1} \equiv 1\pmod{n}$

Pseudosimplele Fermat la baza 2 formează secvența:

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

iar în baza 3, secvența:

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

Un număr care este pseudoprimul lui Fermat în fiecare bază coprime se numește număr Carmichael .

Euler-Jacobi pseudosimple

Un număr compus impar n se numește pseudoprim Euler-Jacobi în baza a dacă satisface comparația [2]

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

unde este simbolul Jacobi . Deoarece din această comparație rezultă că orice pseudosimplu Euler-Jacobi este și un pseudosimplu Fermat (din același motiv). $\left(\frac{a}{n}\dreapta)$ $a^{n-1} \equiv 1\pmod{n},$

Pseudosimplele Euler-Jacobi în baza 2 formează secvența:

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

iar în baza 3, secvența:

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

Fibonacci pseudo-simplu

Articolul principal: Numărul Fibonacci pseudoprim

Pseudosimple Lucas

Articolul principal: Lucas pseudoprime

Pseudosimple Perrin

Un număr compus q se numește pseudoprim Perrin dacă împarte al- lea număr Perrin P ( q ) dat de relația de recurență :

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

și

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

Frobenius pseudosimples

Un număr pseudoprim care a trecut testul în trei pași de a fi un număr posibil prim , dezvoltat de Jon Grantham în 1996. [3] [4]

Pseudosimple Catalana

Un număr compus impar n care satisface comparația

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

unde Cm este al- lea număr catalan . Comparația este adevărată pentru orice număr prim impar n .

Sunt cunoscute doar trei pseudoprime catalane: 5907, 1194649 și 12327121 (secvența A163209 în OEIS ), ultimele două dintre acestea fiind pătrate prime Wieferich . În general, dacă p este un prim Wieferich, atunci p 2 este un pseudoprim catalan.

Vezi și

Note

^ Weisstein, Eric W. Fermat Pseudoprime pe site- ul Wolfram MathWorld .
^ Weisstein , Eric W. Euler-Jacobi Pseudoprime pe site- ul Wolfram MathWorld .
^ Weisstein , Eric W. Frobenius pseudoprime pe site- ul Wolfram MathWorld .
↑ John Grantham. Frobenius pseudoprimes (engleză) // Matematica calculului : jurnal. - 2001. - Vol. 70 , nr. 234 . - P. 873-891 . - doi : 10.1090/S0025-5718-00-01197-2 .

Link -uri

Aebi, C.; Cairns, G. Numere catalane, numere prime și numere prime gemene (nedefinite) // Elemente der Mathematik. - 2008. - T. 63 , nr. 4 . - S. 153-164 . - doi : 10.4171/EM/103 .
pseudoprime catalane . Cercetare în calcul științific în învățământul universitar.

Dicționare și enciclopedii	Britannica (online)