1

Test de primalité de Fermat

1. a. Dans un tableur, entrer la liste des 46 premiers nombres entiers strictement supérieurs à $2$ 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 ici.)

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 $n$ est premier ?


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


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


b. Combien vaut $2^{40}$ modulo $561$ ? En déduire $2^{560} [561]$. Le nombre $561$ est‑il premier ?


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

1. Dans la fonction ci‑dessous on considère un entier $n \geqslant 3$.

À quoi sert la commande % ?


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


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


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

3. Les observations ci‑dessus servent à élaborer un test permettant de déterminer si le nombre $n$ 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 $n=154 515 677$.

c. Quel est l’avantage et l’inconvénient de cet algorithme par rapport à celui consistant à tester l’ensemble des diviseurs possibles entre $1$ et $\sqrt{n}$ ?