Exercice 1 1222 Correction

Soit $p$ un nombre premier.

(a)

Montrer

$\forall k \in {1,2, \dots, p - 1}, p ∣ (\binom{p}{k}) .$
(b)

En déduire que

$\forall n \in ℤ, n^{p} \equiv n [p] .$

Solution

(a)

On a

$(\binom{p}{k}) = \frac{p}{k} (\binom{p - 1}{k - 1})$

donc

$k (\binom{p}{k}) = p (\binom{p - 1}{k - 1}) .$

Par suite, $p ∣ k (\binom{p}{k})$ .
Or $p$ est premier et $k < p$ donc $k \land p = 1$ puis $p ∣ (\binom{p}{k})$ en vertu du théorème de Gauss.
(b)

Par récurrence finie sur $n \in {0,1, \dots, p - 1}$
Pour $n = 0$ : ok
Supposons la propriété établie au rang $n \in {0,1, \dots, p - 2}$
Par la formule du binôme

${(n + 1)}^{p} = n^{p} + \sum_{k = 1}^{p - 1} (\binom{p}{k}) n^{k} + 1 \equiv n + 1 [p]$

car pour $1 \leq k \leq p - 1$ .

$(\binom{p}{k}) \equiv 0 [p] .$

Récurrence établie.
Pour tout $n \in ℤ$ , il existe $r \in {0,1, \dots, p - 1}$ tel que $n \equiv r [p]$ et

$n^{p} \equiv r^{p} \equiv r \equiv n [p] .$

Exercice 2 3636 Correction

Soit $n \geq 2$ un entier. On suppose

\forall a \in {1, \dots, n - 1}, a^{n - 1} \equiv 1 [n] .

Montrer que $n$ est un nombre premier

Solution

Pour tout $a \in {1, \dots, n - 1}$ , $a$ est premier avec $n$ . En effet, un diviseur commun à $a$ et $n$ est diviseur de $a^{n - 1} - 1$ et donc de 1.
On en déduit que $n$ est premier puisque premier avec chaque naturel strictement inférieur à lui-même.

Exercice 3 204 Correction

(Nombres de Carmichael)

Soit $n$ un entier supérieur à 2.
On suppose que $n$ pour tout facteur premier $p$ de $n$ , $p^{2}$ ne divise pas $n$ mais $p - 1$ divise $n - 1$ .
Établir

\forall a \in ℤ, a^{n} \equiv a [n] .

Solution

Par hypothèse, on peut écrire $n = p_{1} p_{2} \dots p_{r}$ avec $p_{1}, \dots, p_{r}$ nombres premiers deux à deux distincts.
Soit $a \in ℤ$ . Considérons $i \in {1, \dots, r}$ .
Si $p_{i}$ ne divise pas $a$ , le petit théorème de Fermat assure $a^{p_{i} - 1} \equiv 1 [p_{i}]$ .
Puisque $p_{i} - 1$ divise $n - 1$ , on a encore $a^{n - 1} \equiv 1 [p_{i}]$ et donc $a^{n} \equiv a [p_{i}]$
Si $p_{i}$ divise $a$ alors $p_{i}$ divise aussi $a^{n}$ et donc $a^{n} \equiv 0 \equiv a [p_{i}]$ .
Enfin, chaque $p_{i}$ divisant $a^{n} - a$ et les $p_{i}$ étant deux à deux premiers entre eux, $n = p_{1} \dots p_{r}$ divise $a^{n} - a$ et finalement $a^{n} \equiv a [n]$ .
La réciproque de ce résultat est vraie.
Ce résultat montre que le petit théorème de Fermat ne caractérise pas les nombres premiers. Les nombres non premiers satisfaisant le petit théorème de Fermat, sont les nombres de Carmichael. Le plus petit d’entre eux est 561, le suivant 1105.

Exercice 4 3686

On désire établir qu’il existe une infinité de nombres premiers de la forme $4 n + 1$ . Pour cela on raisonne par l’absurde et l’on suppose que ceux-ci sont en nombre fini. On pose $N$ le produit de ceux-ci et l’on introduit

M = {(2 N)}^{2} + 1 .

(a)

On suppose qu’il existe un facteur premier $q$ de $M$ de la forme $4 n + 3$ . Établir

${(2 N)}^{q - 1} \equiv - 1 [q] .$
(b)

Conclure en exploitant le petit théorème de Fermat.

Petit théorème de Fermat