Nombre pseudoprimer

De Viquipèdia
Dreceres ràpides: navegació, cerca

Els nombres pseudoprimers són els que no essent primers, verifiquen el test de primalitat de base b:

Siguin un nombre enter i un altre nombre enter no primer. El nombre és pseudoprimer respecte a la base si .

Els nombres pseudoprimers respecte qualsevol base són els nombres de Carmichael.

Pseudoprimers de Fermat[modifica | modifica el codi]

El petit teorema de Fermat estableix que si és primer i és coprimer amb , llavors p−1 − 1 i és divisible per . Per a un nombre enter > 1, si un nombre enter compost divideix a -1 - 1, llavors s'anomena pseudoprimer de Fermat en base . D'això es desprèn que si és un pseudoprimer de Fermat en base , llavors es comprimeix a . Algunes fonts utilitzen variacions d'aquesta definició, per exemple, només per permetre que els nombres imparells siguin pseudoprimers.

Un enter és pseudoprimer de Fermat a tots els valors de que són primers entre si per es diu Nombre de Carmichael.

Exemples[modifica | modifica el codi]

12 1 (mod 13)

Aquí es verifica l' equació, ja que 13 és un nombre primer

2046 1 (mod 2047)

Aquí es verifica l' equació per 2047=23×89. Llavors n es un nombre pseudoprimer en base 2.

Classes de nombres pseudoprimers[modifica | modifica el codi]