Pseudoprime

Ett pseudoprimtal är ett naturligt tal som har några av egenskaperna hos primtal , men som ändå är sammansatt . Det finns flera olika typer av pseudoprimer, beroende på egenskaperna som övervägs.

Förekomsten av pseudoprimtal är ett hinder för primalitetstester som försöker använda vissa egenskaper hos primtal för att avgöra om ett givet tal är primtal.

Pseudosimple Farms

Ett sammansatt tal n sägs vara Fermats pseudoprimbas a om a och n är coprime och . [ett] $a^{n-1} \equiv 1\pmod{n}$

Fermats pseudosimplar till bas 2 bildar sekvensen:

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

och i bas 3, sekvensen:

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

Ett tal som är Fermats pseudoprimtal i varje coprime -bas kallas ett Carmichael-tal .

Euler-Jacobi pseudosimples

Ett udda sammansatt tal n kallas Euler-Jacobi pseudoprimtal i bas a om det uppfyller jämförelsen [2]

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

var är Jacobi-symbolen . Eftersom det följer av denna jämförelse att alla Euler-Jacobi pseudosimple också är en Fermat pseudosimple (av samma anledning). $\left( \frac{a}{n}\right)$ $a^{n-1} \equiv 1\pmod{n},$

Euler-Jacobi pseudosimplar i bas 2 bildar sekvensen:

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

och i bas 3, sekvensen:

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

Pseudo-enkel Fibonacci

Huvudartikel: Pseudoprime Fibonacci-tal

Pseudosimple Lucas

Huvudartikel: Lucas pseudoprime

Pseudosimple Perrin

Ett sammansatt tal q kallas ett Perrin-pseudoprimtal om det dividerar det q :e Perrintalet P ( q ) som ges av återfallsrelationen :

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

och

P ( n ) = P ( n − 2) + P ( n − 3) för n > 2.

Frobenius pseudosimples

Ett pseudoprimtal som klarade trestegstestet att vara ett möjligen primtal , utvecklat av Jon Grantham 1996. [3] [4]

Pseudosimple Catalana

Ett udda sammansatt tal n som uppfyller jämförelsen

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

där Cm är det månte katalanska talet . Jämförelsen är sann för alla udda primtal n .

Endast tre katalanska pseudoprimer är kända: 5907, 1194649 och 12327121 (sekvens A163209 i OEIS ), av vilka de två sista är Wieferich -primkvadrater . I allmänhet, om p är ett Wieferich-primtal, så är p 2 ett katalanskt pseudoprimtal.

Se även

Anteckningar

↑ Weisstein, Eric W. Fermat Pseudoprime på Wolfram MathWorld- webbplatsen .
↑ Weisstein, Eric W. Euler-Jacobi Pseudoprime på Wolfram MathWorld -webbplatsen .
↑ Weisstein, Eric W. Frobenius pseudoprime på Wolfram MathWorld- webbplatsen .
↑ John Grantham. Frobenius pseudoprimes (engelska) // Mathematics of Computation : journal. - 2001. - Vol. 70 , nej. 234 . - s. 873-891 . - doi : 10.1090/S0025-5718-00-01197-2 .

Länkar

Aebi, C.; Cairns, G. Katalanska tal, primtal och tvillingprimtal (odefinierade) // Elemente der Mathematik. - 2008. - T. 63 , nr 4 . - S. 153-164 . - doi : 10.4171/EM/103 .
Katalanska pseudoprimer . Forskning i Scientific Computing inom grundutbildning.

Ordböcker och uppslagsverk	Britannica (online)