Soient $p$ et $q$ deux nombres premiers distincts, $n = pq$ et $m = (p-1)(q-1)$. On fixe $e \in \mathbb{N}^*$ tel que $e \wedge m = 1$.
- Justifier que $m \geqslant 2$, puis qu'il existe $d \in \{1, \dots, m-1\}$ tel que $ed \equiv 1 \;[m]$.
- Soit $x \in \mathbb{Z}$. Montrer que $x^{ed} \equiv x \;[p]$. On distinguera les cas $p \mid x$ et $p \nmid x$.
- En déduire que $x^{ed} \equiv x \;[n]$ pour tout $x \in \mathbb{Z}$.
- Application numérique : $p = 11$, $q = 13$, $e = 7$. a) Calculer $n$, $m$ et l'entier $d$ de la question 1. b) Calculer le reste $y$ de la division euclidienne de $5^7$ par $n$. c) Sans utiliser la question 3, calculer les restes de $47^{103}$ modulo $11$ et modulo $13$, puis en déduire le reste de $47^{103}$ modulo $143$. Interpréter à l'aide de la question 3.
L'un des deux premiers distincts vaut au moins $3$.
Un entier est inversible modulo $m$ si et seulement s'il est premier avec $m$ ; prendre ensuite le reste de l'inverse modulo $m$.
Écrire $ed = 1 + km$ avec $k \in \mathbb{N}$, puis $x^{ed} = x \cdot (x^{p-1})^{k(q-1)}$.
Pour la question 3, $p$ et $q$ sont premiers entre eux et divisent tous deux $x^{ed} - x$.
Pour 4a, une seule division euclidienne de $120$ par $7$ suffit.
Pour 4c, réduire $47$ modulo $11$ et $13$, puis chercher une petite puissance congrue à $\pm 1$.
1. Comme $p \neq q$ sont premiers, l'un d'eux vaut au moins $3$ et l'autre au moins $2$, donc $m = (p-1)(q-1) \geqslant 2 \times 1 = 2$.
Comme $e \wedge m = 1$, le théorème de Bézout fournit $u, v \in \mathbb{Z}$ avec $eu + mv = 1$, donc $eu \equiv 1 \;[m]$. Soit $d$ le reste de la division euclidienne de $u$ par $m$ : $d \equiv u \;[m]$, donc $ed \equiv 1 \;[m]$, et $d \in \{0, \dots, m-1\}$. Si $d = 0$, on aurait $0 \equiv 1 \;[m]$, soit $m \mid 1$, impossible car $m \geqslant 2$. Donc $d \in \{1, \dots, m-1\}$.
2. Comme $ed \equiv 1 \;[m]$ et $ed \geqslant 1$, il existe $k \in \mathbb{N}$ tel que $ed = 1 + km$.
- Si $p \mid x$ : $x \equiv 0 \;[p]$ et $x^{ed} \equiv 0 \;[p]$ car $ed \geqslant 1$. Donc $x^{ed} \equiv x \;[p]$.
- Si $p \nmid x$ : par le petit théorème de Fermat, $x^{p-1} \equiv 1 \;[p]$. Alors $$x^{ed} = x \cdot x^{k(p-1)(q-1)} = x \cdot \left(x^{p-1}\right)^{k(q-1)} \equiv x \;[p].$$
3. Le raisonnement de la question 2, en échangeant les rôles de $p$ et $q$, donne $x^{ed} \equiv x \;[q]$. Ainsi $p$ et $q$ divisent $x^{ed} - x$. Comme $p$ et $q$ sont des premiers distincts, $p \wedge q = 1$, et une conséquence du lemme de Gauss donne $pq \mid x^{ed} - x$, c'est-à-dire $x^{ed} \equiv x \;[n]$.
4. a) $n = 11 \times 13 = 143$ et $m = 10 \times 12 = 120$. On a $120 = 17 \times 7 + 1$, donc $7 \times (-17) \equiv 1 \;[120]$. Le reste de $-17$ modulo $120$ est $103$, donc $d = 103$. Vérification : $7 \times 103 = 721 = 6 \times 120 + 1$.
b) $5^3 = 125$ et $5^4 = 625 = 4 \times 143 + 53$, donc $5^4 \equiv 53 \;[143]$. Puis $5^7 = 5^4 \times 5^3 \equiv 53 \times 125 = 6625 \;[143]$. Or $143 \times 46 = 5720 + 858 = 6578$ et $6625 - 6578 = 47$. Donc $y = 47$.
c) Modulo $11$. $47 = 4 \times 11 + 3$, donc $47 \equiv 3 \;[11]$. Or $3^5 = 243 = 22 \times 11 + 1 \equiv 1 \;[11]$ et $103 = 5 \times 20 + 3$, donc $47^{103} \equiv 3^{103} \equiv 3^3 = 27 \equiv 5 \;[11]$.
Modulo $13$. $47 = 3 \times 13 + 8$, donc $47 \equiv 8 \;[13]$. Or $8^2 = 64 = 5 \times 13 - 1 \equiv -1 \;[13]$ et $103 = 2 \times 51 + 1$, donc $47^{103} \equiv (8^2)^{51} \times 8 \equiv (-1)^{51} \times 8 = -8 \equiv 5 \;[13]$.
Conclusion. $11$ et $13$ divisent $47^{103} - 5$ et $11 \wedge 13 = 1$, donc $143 \mid 47^{103} - 5$. Comme $0 \leqslant 5 < 143$, le reste de $47^{103}$ modulo $143$ est $5$.
Interprétation. $47^{103} \equiv (5^7)^{103} = 5^{ed} \;[143]$, et la question 3 donne $5^{ed} \equiv 5 \;[143]$. Le message $5$, chiffré en $y = 47$ par $x \mapsto x^e$, est retrouvé par $y \mapsto y^d$.
$n=143$, $m=120$, $d=103$, $y=47$, $47^{103}\equiv 5\;[143]$