Pseudoprimo

Un pseudoprimo es un número natural que tiene algunas de las propiedades de los primos , pero no obstante es compuesto . Hay varios tipos diferentes de pseudoprimes, dependiendo de las propiedades bajo consideración.

La existencia de pseudoprimos es un obstáculo para las pruebas de primalidad que intentan usar ciertas propiedades de los primos para determinar si un número dado es primo.

Granjas pseudosimples

Se dice que un número compuesto n es la base pseudoprima a de Fermat si ayn son coprimos y . [una] $a^{n-1} \equiv 1\pmod{n}$

Los pseudosimples de Fermat en base 2 forman la sucesión:

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

y en base 3, la secuencia:

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

Un número que es el pseudoprimo de Fermat en cada base coprima se llama número de Carmichael .

Pseudosimples de Euler-Jacobi

Un número compuesto impar n se llama pseudoprimo de Euler-Jacobi en base a si satisface la comparación [2]

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

¿ Dónde está el símbolo de Jacobi ? Ya que de esta comparación se sigue que cualquier pseudosimple de Euler-Jacobi es también un pseudosimple de Fermat (por la misma razón). $\left(\frac{a}{n}\right)$ $a^{n-1} \equiv 1\pmod{n},$

Los pseudosimples de Euler-Jacobi en base 2 forman la secuencia:

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

y en base 3, la secuencia:

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

Pseudo-simple Fibonacci

Artículo principal: número de Fibonacci pseudoprimo

Pseudosimple Lucas

Artículo principal: Lucas pseudoprime

Perrin pseudosimple

Un número compuesto q se llama pseudoprimo de Perrin si divide el q-ésimo número de Perrin P ( q ) dado por la relación de recurrencia :

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

PAGS ( norte ) = PAGS ( norte - 2) + PAGS ( norte - 3) para norte > 2.

Pseudosimples de Frobenius

Un número pseudoprimo que pasó la prueba de los tres pasos de ser un número posiblemente primo , desarrollada por Jon Grantham en 1996. [3] [4]

Catalana pseudosimple

Un número compuesto impar n que satisface la comparación

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

donde Cm es el m-ésimo número catalán . La comparación es cierta para cualquier número primo impar n .

Solo se conocen tres pseudoprimos catalanes: 5907, 1194649 y 12327121 (secuencia A163209 en OEIS ), los dos últimos de los cuales son cuadrados primos de Wieferich . En general, si p es un primo de Wieferich, entonces p 2 es un pseudoprimo catalán.

Véase también

Notas

↑ Weisstein, Eric W. Fermat Pseudoprime en el sitio web de Wolfram MathWorld .
↑ Weisstein, Eric W. Euler-Jacobi Pseudoprime en el sitio web de Wolfram MathWorld .
↑ Weisstein, Eric W. Frobenius pseudoprime en el sitio web Wolfram MathWorld .
↑ John Grantham. Frobenius pseudoprimes (inglés) // Matemáticas de la computación : diario. - 2001. - vol. 70 , núm. 234 . - Pág. 873-891 . -doi : 10.1090/ S0025-5718-00-01197-2 .

Enlaces

Aebi, C.; Cairns, G. Números catalanes, primos y primos gemelos (indefinido) // Elemente der Mathematik. - 2008. - T. 63 , N º 4 . - S. 153-164 . -doi : 10.4171 / EM/103 .
Pseudoprimos catalanes . Investigación en Computación Científica en la Educación de Pregrado.

diccionarios y enciclopedias	Britannica (en línea)