Pseudoprime

Az álprím egy természetes szám , amely rendelkezik a prímek bizonyos tulajdonságaival , de ennek ellenére összetett . A vizsgált tulajdonságoktól függően többféle pszeudoprím létezik.

A pszeudoprímek megléte akadályt jelent a prímszámok bizonyos tulajdonságainak felhasználásával annak meghatározására , hogy egy adott szám prím-e.

Pseudosimple Farms

Egy n összetett számról azt mondjuk , hogy Fermat a pszeudoprím bázisa , ha a és n koprím és . [egy] $a^{n-1} \equiv 1\pmod{n}$

A 2-es bázishoz tartozó Fermat-pszeudo-egyszerűségek a következő sorrendet alkotják:

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

a 3. bázisban pedig a következő sorrend:

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

Azt a számot, amely Fermat pszeudoprímje minden másodprím -alapban, Carmichael-számnak nevezzük .

Euler-Jacobi pszeudosimples

Egy n páratlan összetett számot Euler-Jacobi pszeudoprímnek nevezünk az a bázisban , ha kielégíti az összehasonlítást [2]

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

hol van a Jacobi szimbólum . Mivel ebből az összehasonlításból az következik, hogy bármely Euler-Jacobi álegyszerűség egyben Fermat-álegyszerűség is (ugyanebből az okból). $\left( \frac{a}{n}\right)$ $a^{n-1} \equiv 1\pmod{n},$

A 2. bázis Euler-Jacobi álegyszerűségei a következő sorrendet alkotják:

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

a 3. bázisban pedig a következő sorrend:

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

Ál-egyszerű Fibonacci

Főcikk : Pseudoprime Fibonacci-szám

Pszeudosimple Lucas

Főcikk : Lucas pszeudoprime

Pszeudosimple Perrin

Egy q összetett számot Perrin-pszeudoprímnek nevezünk , ha elosztja a q- edik P ( q ) Perrin - számot , amelyet az ismétlődési reláció adja :

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

és

P ( n ) = P ( n − 2) + P ( n − 3), n > 2 esetén.

Frobenius pseudosimples

Egy pszeudoprímszám, amely megfelelt a lehetséges prímszám háromlépéses tesztjén , amelyet Jon Grantham fejlesztett ki 1996-ban. [3] [4]

Pseudosimple Catalana

Páratlan összetett n szám , amely kielégíti az összehasonlítást

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

ahol Cm az m - edik katalán szám . Az összehasonlítás igaz bármely n páratlan prímszámra .

Csak három katalán pszeudoprím ismert: 5907, 1194649 és 12327121 (A163209 szekvencia az OEIS- ben ), amelyek közül az utolsó kettő Wieferich -prímnégyzet . Általában, ha p Wieferich prím, akkor p 2 katalán pszeudoprím.

Lásd még

Jegyzetek

↑ Weisstein, Eric W. Fermat Pseudoprime a Wolfram MathWorld webhelyén .
↑ Weisstein, Eric W. Euler-Jacobi Pseudoprime a Wolfram MathWorld webhelyén .
↑ Weisstein, Eric W. Frobenius pszeudoprím a Wolfram MathWorld webhelyén .
↑ John Grantham. Frobenius pseudoprimes (angol) // Számítási matematika : folyóirat. - 2001. - Vol. 70 , sz. 234 . - P. 873-891 . - doi : 10.1090/S0025-5718-00-01197-2 .

Linkek

Aebi, C.; Cairns, G. Katalán számok, prímek és ikerprímek (undefined) // Elemente der Mathematik. - 2008. - T. 63 , 4. sz . - S. 153-164 . - doi : 10.4171/EM/103 .
Katalán pszeudoprímek . Kutatás a tudományos számítástechnikában az alapképzésben.

Szótárak és enciklopédiák	Britannica (online)