Mathématiques Expertes Terminale
Rejoignez la communauté !
Co-construisez les ressources dont vous avez besoin et partagez votre expertise pédagogique.
Nombres complexes
Ch. 1
Nombres complexes, point de vue algébrique
Ch. 2
Nombres complexes, point de vue géométrique
Arithmétique
Ch. 3
Divisibilité dans Z
Ch. 4
PGCD et applications
Ch. 5
Nombres premiers
Graphes et matrices
Ch. 6
Calcul matriciel et applications aux graphes
Ch. 7
Suites et matrices
Annexes
Cahier d'algorithmique et de programmation
Chapitre 5
TP Info 1

Test de primalité de Fermat

Objectif
Utiliser un test probabiliste de primalité afin d'évaluer si un entier est premier ou non, à l'aide d'une des deux méthodes.

Méthode 1
Tableur

1. a. Dans un tableur, entrer la liste des 46 premiers nombres entiers strictement supérieurs à dans la colonne A.
Dans la cellule B3, entrer la formule : =MOD(2^(A3-1);A3).
Étendre ensuite la formule à toute la colonne. (Fichier téléchargeable .)

maths expertes - chapitre 5 - Nombres premiers - TP1. Test de primalité de Fermat - méthode 1
Le zoom est accessible dans la version Premium.

b. À quoi la commande MOD sert‑elle ?

2. D'après le petit théorème de Fermat, quel nombre est affiché dans la colonne B lorsque est premier ?

3. Si une cellule de la colonne B n'est pas égale à , que peut‑on dire du nombre correspondant ?

4. a. Lister l'ensemble des entiers inférieurs à dont la cellule de la colonne B est égale à .
Que remarque‑t‑on ?

b. Combien vaut modulo  ? En déduire . Le nombre est‑il premier ?

c. Finalement, que peut‑on dire lorsque la cellule de la colonne B est égale à  ?

Méthode 2
Python

1. Dans la fonction ci‑dessous on considère un entier .

maths expertes - chapitre 5 - Nombres premiers - TP1. Test de primalité de Fermat - méthode 2
Le zoom est accessible dans la version Premium.

À quoi sert la commande % ?

2. a. D'après le petit théorème de Fermat, que renvoie l'algorithme lorsque est un nombre premier ?

b. Que peut‑on dire lorsque la valeur de F affichée en sortie d'algorithme n'est pas égale à  ?

c. Tester cet algorithme pour une dizaine de valeurs afin de vérifier les observations. Que remarque‑t‑on pour  ? Cet entier est‑il premier ?



3. Les observations ci‑dessus servent à élaborer un test permettant de déterminer si le nombre a des chances d'être premier.

def testfermat2(n):
	F = 2**(n-1) % n
	if ... :
		return("Peut-être premier")
	else :
		return ("Pas premier")

a. Compléter la condition à tester ligne 3.

b. Tester l'algorithme avec quelques valeurs puis tester l'algorithme pour .

c. Quel est l'avantage et l'inconvénient de cet algorithme par rapport à celui consistant à tester l'ensemble des diviseurs possibles entre et  ?

Histoire des maths

Les entiers qui ne sont pas premiers mais qui vérifient , dès lors que et sont premiers entre eux, sont appelés les nombres de Carmichael, du nom du mathématicien américain Robert Daniel Carmichael (1879‑1967), qui s'est tout particulièrement intéressé aux propriétés de ces nombres. Il a été démontré en 1994 qu'il existe en fait une infinité de nombres de Carmichael.

Une erreur sur la page ? Une idée à proposer ?

Nos manuels sont collaboratifs, n'hésitez pas à nous en faire part.

Oups, une coquille

j'ai une idée !

Nous préparons votre pageNous vous offrons 5 essais
collaborateur

collaborateurYolène
collaborateurÉmilie
collaborateurJean-Paul
collaborateurFatima
collaborateurSarah

Premium activé


5
essais restants
Utilisation des cookies
Lors de votre navigation sur ce site, des cookies nécessaires au bon fonctionnement et exemptés de consentement sont déposés.