NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 27/07/2016

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique                               

     

Nombres PREMIERS

 

Débutants

Nombres

Premiers

Recherche de PRIMALITÉ

 

Glossaire

Nombres

Premiers

 

 

INDEX

 

Nombres premiers

 

Types de premiers

 

Crible d'Ératosthène

Divisibilité

Pseudo-premiers

Carmichaël

Primalité

Liste pseudo-P.

Carmichaël - texte

Presque-premiers

 

Sommaire de cette page

>>> Approche

>>> Théorème chinois

>>> Nombres pseudo-premiers

>>> Remarques

>>> Pseudo-premiers d'Euler

>>> Plus petit pseudo-premier

 

 

 

 

 

  

NOMBRES PSEUDO PREMIERS

ou de POULET

 

S'ils n'existaient pas, il serait beaucoup plus facile de déterminer si un nombre est premier ou pas. Leur existence infime la réciproque du Petit  Théorème de Fermat.

Anglais: Pseudo prime

 

  

 

APPROCHE

 

Approche

 

*       On s'intéresse a puissance p de 2, et on retranche 2. Divisibilité?

 

*       Cette puissance est souvent divisible par la puissance p elle-même.

Examinons les conditions sur p pour que ça marche.

 

*       Il faut que p soit premier.
Alors cela marche à coup sûr.
Mais il existe aussi des cas bons, sans que p soit premier.

 

Exemples

 

p = 5

Premier

25 – 2 

= 30 = 5 k

Bon

p = 4 = 2 x 2

Composé

24 – 2 

= 14  4 k

Non

p = 341 = 11 x 31

Composé

2341 – 2 

= 341 k

Bon

 

Il semblerait donc que 2p – 2

 

*       Est divisible par p         si p est premier; et         

*       On ne peut rien dire     si p est composé.    

 

 

 

  

Théorème chinois

 

*      Les Chinois formulent une hypothèse:

 

Pour tout premier p,

2p - 2 est divisible par p.

 

 

C'est vrai !

MAIS, la réciproque est fausse

 

*      C'est une conséquence du petit théorème de Fermat

 

Si p est premier, le reste des divisions par p

- d'un nombre quelconque et

- de ce nombre à la puissance p

sont égaux :

ap - a est divisible par p

 

ou, plus mathématique moderne :

ap = a mod p

 

Autre formulation

*      En divisant les deux membres par p, à condition que a et p soient étrangers:

 

2p-1 – 1 est divisible par p

 

 

 

*      Contrairement à la croyance chinoise. C'est ce que pensait également Leibniz. C'est Pierre Sarrus qui prouva le contraire.

 

 

Exemple

2341 – 2 est divisible par 341

et, pourtant 341 n'est pas premier: 341 = 31 x 11

 

 

*      341 est le plus petit entier composé ayant cette propriété.

 

*      Ce contre-exemple montre que la réciproque du petit théorème est fausse.

 

 

 

Nombres PSEUDO-PREMIERS ou

Nombres de POULET ou

Nombres CHINOIS

 

*      Nombres curieux qui se comportent comme des nombres premiers selon le test basé sur le petit théorème de Fermat.

 

*      Ils sont de la famille des probablement premiers.

 

*      Le test de Fermat fonctionne comme un tamis qui laisse passer tous les nombres premiers. Mais, qui, hélas, en laisse passer quelques autres, les pseudo-premiers.

 

En effet, avec le test de Fermat:

 

*      Un nombre premier donne toujours le résultat attendu.

 

*      Le résultat 1 est obtenu pour tous les nombres premiers et, aussi,  quelques autres, les pseudo-premiers.

 

 

 

 

Remarques

 

*      341 est le plus petit pseudo-premier de base 2.

Ce qui signifie que 2340 – 1 est divisible par 341, bien que 341 soit composé et non pas premier.

 

 

Les pseudo-premiers sont relativement rares

 

Jusqu'à

Pseudo-premiers

PP de base 2

PP Absolu

20 000 000 000

882 206 716

19 865

Voir 561

  

Voici la liste de tels nombres jusqu'à 10 000 pour a = 2:

 

341,  561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911.

 

Pour a = 3, on trouverait: 91  121  286   671  703

Pour a = 4, on trouverait: 15    85    91   341  435

Etc.

 

 

Pseudo-premier d'Euler

 

*      Un pseudo-premier d'Euler n de base a est un nombre impair composé, n et a étant premiers entre eux, tel que:

 

 

*      En effet, tous calculs faits en mod p

 

*       Petit théorème de Fermat avec p premier et premier avec a.

*       Avec p premier autre que 2;
p est alors impair.

 

 

*       En factorisant

 

*       En considérant chaque facteur

*       Or p = 2q + 1 et q = (p-1)/2

 

Plus petit pseudo-premiers

 

Le plus petit pseudo-premier dans sa catégorie:

Source Pomerance indiquée in fine

 

 

 

Suite

*   Liste  des pseudo-premiers.

*   Nombres de Carmichaël

*   Pseudo-premiers de Perrin

*    Nombres premiersIndex

Voir

*    Décomposition

*    Nombre en 161 038

*    Petit théorème de Fermat

*    Théorie des nombres

DicoNombre

*    Nombre 341

*    Nombre 161 038

Sites

*    La page des nombres premiers
       de Chris Caldwell

*    The Pseudoprimes to 25 109 by Carl Pomerance et al.

Cette page

http://villemin.gerard.free.fr/Wwwgvmm/Premier/pseudo.htm