Terminale

Nombres premiers et petit théorème de Fermat — Exercices d'application

1. Nombres premiers

↩ Revoir le cours

Exercice 1 — ⭐

Les nombres $221$ , $223$ et $1\,001$ sont-ils premiers ? Justifie.
Quels nombres premiers suffit-il de tester pour savoir si un entier inférieur à $1\,000$ est premier ?
Modifie la fonction crible du cours pour qu’elle renvoie le nombre de nombres premiers inférieurs ou égaux à $N$ . Combien y en a-t-il jusqu’à $1\,000$ ?

Voir le corrigé

$221 = 13 \times 17$ : non. $223$ : $\sqrt{223} \approx 14{,}9$ ; ni $2$ , $3$ , $5$ , $7$ , $11$ , $13$ ne le divisent : premier. $1\,001 = 7 \times 11 \times 13$ : non.
Les nombres premiers inférieurs à $\sqrt{1\,000} \approx 31{,}6$ : $2$ , $3$ , $5$ , $7$ , $11$ , $13$ , $17$ , $19$ , $23$ , $29$ , $31$ .
return len([n for n in range(N + 1) if est_premier[n]]) ; on obtient $168$ nombres premiers jusqu’à $1\,000$ .

2. Une infinité de nombres premiers

↩ Revoir le cours

Exercice 2 — ⭐⭐

Calcule $2 \times 3 \times 5 + 1$ et $2 \times 3 \times 5 \times 7 + 1$ . Ces nombres sont-ils premiers ?
Soit $n \geqslant 2$ . Montre que $n! + 1$ n’a aucun diviseur premier inférieur ou égal à $n$ . En déduire une autre démonstration du fait qu’il existe des nombres premiers aussi grands qu’on veut.
Montre que les $9$ entiers consécutifs $10! + 2$ , $10! + 3$ , …, $10! + 10$ ne sont pas premiers. Que peut-on en déduire sur les « trous » entre nombres premiers ?

Voir le corrigé

$31$ et $211$ : tous deux premiers (on vérifie qu’aucun premier $\leqslant \sqrt{211} \approx 14{,}5$ ne divise $211$ ).
Si $p \leqslant n$ est premier, $p$ divise $n!$ ; s’il divisait $n! + 1$ , il diviserait $1$ . Donc tout diviseur premier de $n! + 1$ (il en existe, car $n! + 1 \geqslant 2$ ) est strictement supérieur à $n$ . Pour tout $n$ , il existe donc un nombre premier $> n$ .
Pour $2 \leqslant k \leqslant 10$ , $k$ divise $10!$ donc divise $10! + k$ , et $10! + k > k$ : ces entiers ne sont pas premiers. On peut ainsi construire des suites aussi longues qu’on veut d’entiers consécutifs non premiers : les écarts entre nombres premiers consécutifs peuvent être arbitrairement grands.

3. Décomposition en produit de facteurs premiers

↩ Revoir le cours

Exercice 3 — ⭐⭐

Décompose $1\,540$ et $2\,002$ en produits de facteurs premiers.
En déduire leur PGCD et le nombre de diviseurs positifs de $1\,540$ .
Quel est le plus petit entier naturel par lequel il faut multiplier $1\,540$ pour obtenir un carré parfait ?

Voir le corrigé

$1\,540 = 2^2 \times 5 \times 7 \times 11$ ; $2\,002 = 2 \times 7 \times 11 \times 13$ .
$\text{PGCD} = 2 \times 7 \times 11 = 154$ . Nombre de diviseurs de $1\,540$ : $(2 + 1)(1 + 1)(1 + 1)(1 + 1) = 24$ .
Dans un carré, tous les exposants sont pairs : il faut multiplier par $5 \times 7 \times 11 = 385$ ( $1\,540 \times 385 = 592\,900 = 770^2$ ).

Exercice 4 — ⭐⭐⭐

Montre, à l’aide du lemme d’Euclide, que si un nombre premier $p$ divise $a^2$ , alors $p$ divise $a$ .
En déduire que $\sqrt 2$ est irrationnel : on suppose $\sqrt 2 = \dfrac ab$ avec $a$ et $b$ premiers entre eux, et on montre que $2$ divise $a$ puis $b$ .
Détermine les entiers naturels $n$ ayant exactement $3$ diviseurs positifs.

Voir le corrigé

$p \mid a \times a$ : par le lemme d’Euclide, $p \mid a$ ou $p \mid a$ , donc $p \mid a$ .
$\sqrt 2 = \dfrac ab$ donne $a^2 = 2b^2$ : $2 \mid a^2$ donc $2 \mid a$ (question 1). Écrivons $a = 2a'$ : $4a'^2 = 2b^2$ , $b^2 = 2a'^2$ , donc $2 \mid b$ . $2$ divise $a$ et $b$ , qui sont premiers entre eux : contradiction. $\sqrt 2$ est irrationnel.
Si $n = p_1^{\alpha_1} \dots p_k^{\alpha_k}$ , le nombre de diviseurs est $(\alpha_1 + 1) \dots (\alpha_k + 1) = 3$ . $3$ est premier, donc $k = 1$ et $\alpha_1 = 2$ : $n = p^2$ avec $p$ premier ( $4$ , $9$ , $25$ , $49$ …).

4. Petit théorème de Fermat

↩ Revoir le cours

Exercice 5 — ⭐⭐

En utilisant le petit théorème de Fermat, détermine le reste de $3^{100}$ dans la division par $7$ , puis par $11$ .
Montre que pour tout entier $n$ , $n^{13} - n$ est divisible par $13$ .
Démontre que pour tout entier $n$ , $n^5 - n$ est divisible par $30$ (on appliquera Fermat avec $p = 5$ , puis on montrera la divisibilité par $2$ et $3$ ).

Voir le corrigé

Modulo $7$ : $3^6 \equiv 1$ ; $100 = 6 \times 16 + 4$ ; $3^{100} \equiv 3^4 = 81 \equiv 4\ [7]$ . Modulo $11$ : $3^{10} \equiv 1$ ; $100 = 10 \times 10$ ; $3^{100} \equiv 1\ [11]$ .
$13$ est premier : $n^{13} \equiv n\ [13]$ , donc $13 \mid n^{13} - n$ .
Fermat avec $p = 5$ : $5 \mid n^5 - n$ . $n^5 - n = n(n - 1)(n + 1)(n^2 + 1)$ contient le produit de trois entiers consécutifs $(n - 1)n(n + 1)$ , divisible par $2$ et par $3$ . $2$ , $3$ , $5$ sont premiers entre eux deux à deux : $30 \mid n^5 - n$ .

Exercice 6 — ⭐⭐⭐

Test de Fermat.

Calcule $2^{90}$ modulo $91$ avec Python (pow(2, 90, 91)). Que peut-on en conclure sur $91$ ?
Vérifie que $3^{90} \equiv 1\ [91]$ . Ce résultat prouve-t-il que $91$ est premier ?
Écris une fonction temoin_fermat(n) qui renvoie le plus petit entier $a \geqslant 2$ tel que $a^{n-1} \not\equiv 1\ [n]$ , ou None s’il n’y en a pas parmi les $a$ premiers avec $n$ .

Voir le corrigé

pow(2, 90, 91) vaut $64 \neq 1$ : si $91$ était premier, on aurait $2^{90} \equiv 1\ [91]$ . Donc $91$ n’est pas premier ( $91 = 7 \times 13$ ).
pow(3, 90, 91) vaut bien $1$ , mais cela ne prouve rien : le test de Fermat peut seulement démontrer qu’un nombre n’est pas premier.

from math import gcd

def temoin_fermat(n):
    for a in range(2, n):
        if gcd(a, n) == 1 and pow(a, n - 1, n) != 1:
            return a
    return None

print(temoin_fermat(91), temoin_fermat(561))   # 2 None

Exercice 7 — ⭐⭐⭐⭐

Un RSA miniature. On choisit $p = 5$ , $q = 11$ , $n = pq = 55$ et $e = 3$ (clé publique). Un message est un entier $M$ de $0$ à $54$ ; son chiffré est le reste $C$ de $M^e$ modulo $55$ .

Chiffre le message $M = 7$ .
On pose $\varphi = (p - 1)(q - 1) = 40$ . Trouve $d$ tel que $3d \equiv 1\ [40]$ (clé privée).
On admet que $C^d \equiv M\ [55]$ . Déchiffre $C$ obtenu à la question 1 avec Python.
Pourquoi la sécurité repose-t-elle sur la difficulté à décomposer $n$ en facteurs premiers ?

Voir le corrigé

$7^3 = 343 = 55 \times 6 + 13$ : $C = 13$ .
$3 \times 27 = 81 = 2 \times 40 + 1$ : $d = 27$ .
pow(13, 27, 55) renvoie $7$ : on retrouve le message.
Connaître $p$ et $q$ permet de calculer $\varphi$ , puis $d$ . Pour de très grands $n$ (plusieurs centaines de chiffres), on ne sait pas retrouver $p$ et $q$ en un temps raisonnable : $d$ reste secret même si $n$ et $e$ sont publics.