Page 3 - TP-premiers-chinois

Travaux pratiques de Mathématiques Page 3 / 13
Naturels premiers Chinois
Il y a 2500 ans qu'en Chine fut émise la conjecture suivante :
Pour tout entier 1 > n :
n premier « est équivalent à » n divise 2 2 − n
n premier ⇔ n divise 2 2 − n
Nous appellerons naturel premier chinois ou encore naturel pseudo-premier, tout entier naturel 1 > n qui
vérifie :
n divise 2 2 − n
Travail demandé
1] Ecrire un programme qui détermine tous les naturels pseudo-premiers jusqu'à 300.
Fermat a montré en 1640 que pour tout naturel 1 > n :
n premier ⇒ n divise 2 2 − n
La réciproque est malheureusement fausse. Dommage car si elle était exacte nous aurions là un excellent
test pour reconnaître si un entier naturel est un nombre premier ou non.
2] Ecrire une fonction [b] = premier(n) qui détermine si un entier n donné en paramètre est un nombre
premier ou non. Suivant l'entier n , la fonction renvoie alors la variable b contenant la valeur 1 (si n est
premier) ou 0 (si n n’est pas premier).
3] Ecrire un programme qui écrit tous les entiers naturels premiers chinois non premiers, c'est-à-dire tous
les contre-exemples de la relation établie par les Chinois.
4] Ecrire un programme qui liste tous les nombres premiers jusqu’à 300.
5] Essayer de réduire le temps d’exécution de votre fonction « premier(n) » en utilisant le
théorème suivant :
Théorème : Critère de primalité
Soit n un entier naturel supérieur ou égal 2. Si n n'est pas premier, alors il existe un diviseur premier p
de n tel que n p ≤ .
On en déduit le corollaire suivant :
Soit n un entier naturel supérieur ou égal 2. Si n n'est divisible par aucun nombre premier p inférieur à
n , alors n est premier.