Examen National 2022 (Session de Rattrapage)
-
Montrons que $137$ est un nombre premier.
On a $\lfloor\sqrt{137}\rfloor = 11$. Il suffit donc de vérifier que $137$ n'est divisible par aucun des nombres premiers inférieurs ou égaux à $11$, c'est-à-dire $\{2, 3, 5, 7, 11\}$.
C'est bien le cas ici (aucun reste nul). On en déduit que $137$ est un nombre premier. - Cherchons un couple $(u,v) \in \mathbb{Z}^2$ tel que : \[ 38u + 136v = 2 \qquad (1) \] En divisant par $2$, cela équivaut à résoudre : \[ 19u + 68v = 1 \qquad (2) \] Pour chercher une solution particulière de $(2)$, utilisons l'algorithme d'Euclide : \begin{align*} \mathbf{68} &= 3 \times \mathbf{19} + \mathbf{11} \\ \mathbf{19} &= 1 \times \mathbf{11} + \mathbf{8} \\ \mathbf{11} &= 1 \times \mathbf{8} + \mathbf{3} \\ \mathbf{8} &= 2 \times \mathbf{3} + \mathbf{2} \\ \mathbf{3} &= 1 \times \mathbf{2} + \mathbf{1} \end{align*} En posant $a=68$ et $b=19$, et en remontant l'algorithme, il vient : \begin{align*} 11 &= a - 3b \\ 8 &= b - (a - 3b) = 4b - a \\ 3 &= (a - 3b) - (4b - a) = 2a - 7b \\ 2 &= (4b - a) - 2(2a - 7b) = 18b - 5a \\ 1 &= (2a - 7b) - (18b - 5a) = 7a - 25b \end{align*} On trouve donc la relation de Bézout suivante : \[ 7 \times 68 - 25 \times 19 = 1 \] En multipliant cette égalité par $2$ pour retrouver l'équation $(1)$ : \begin{align*} 14 \times 68 - 50 \times 19 &= 2 \\ 136(7) + 38(-25) &= 2 \end{align*} Une solution particulière est donc le couple $(u,v) = (-25, 7)$.
-
Soit $x \in \mathbb{Z}$ tel que $x^{38} \equiv 1 \pmod{137}$.
-
Puisque $x^{38} \equiv 1 \pmod{137}$, il existe un entier $k \in \mathbb{Z}$ tel que $x^{38} = 1 + 137k$.
On peut réécrire cette égalité sous la forme : \[ x \times x^{37} - 137 \times k = 1 \] D'après le théorème de Bachet-Bézout, cette identité prouve que $x$ et $137$ sont premiers entre eux ($x \land 137 = 1$). -
Nous venons de prouver que $x \land 137 = 1$. En outre, $137$ est un nombre premier.
D'après le petit théorème de Fermat, on a directement : \[ x^{136} \equiv 1 \pmod{137} \] -
D'après la question 2, nous avons la relation : $136(7) + 38(-25) = 2$.
On en tire l'égalité : \[ 136 \times 7 = 38 \times 25 + 2 \] Évaluons $x^{136 \times 7}$ en utilisant cette égalité : \begin{align*} x^{136 \times 7} &= x^{38 \times 25 + 2} \\ (x^{136})^7 &= (x^{38})^{25} \times x^2 \pmod{137} \end{align*} Or, d'après les questions précédentes, $x^{38} \equiv 1 \pmod{137}$ et $x^{136} \equiv 1 \pmod{137}$.
En substituant : \begin{align*} 1^7 &\equiv 1^{25} \times x^2 \pmod{137} \\ 1 &\equiv x^2 \pmod{137} \end{align*} On en déduit bien que $x^2 \equiv 1 \pmod{137}$.
-
Puisque $x^{38} \equiv 1 \pmod{137}$, il existe un entier $k \in \mathbb{Z}$ tel que $x^{38} = 1 + 137k$.
-
Résolution de l'équation $x^{38} \equiv 1 \pmod{137}$ :
D'après la question précédente, si $x^{38} \equiv 1 \pmod{137}$, alors on a nécessairement $x^2 \equiv 1 \pmod{137}$. \begin{align*} x^2 - 1 &\equiv 0 \pmod{137} \\ (x-1)(x+1) &\equiv 0 \pmod{137} \end{align*} Puisque $137$ est un nombre premier, il divise ce produit si et seulement s'il divise l'un des facteurs (lemme d'Euclide). On en déduit : \[ x \equiv 1 \pmod{137} \quad \text{ou} \quad x \equiv -1 \pmod{137} \] Sachant que $-1 \equiv 136 \pmod{137}$, les solutions de l'équation sont les entiers $x$ tels que : \[ x \equiv 1 \pmod{137} \quad \text{ou} \quad x \equiv 136 \pmod{137} \]
💡 Remarque:
L'énoncé de l'examen guide l'élève vers l'utilisation des coefficients de Bézout trouvés à la question 2. Cependant, il existe une méthode beaucoup plus rapide et élégante en exploitant les propriétés des puissances et l'ordre d'un élément.
Remarquons que $38 = 2 \times 19$. L'équation $x^{38} \equiv 1 \pmod{137}$ peut s'écrire :
\[ (x^2)^{19} \equiv 1 \pmod{137} \]D'autre part, d'après le petit théorème de Fermat, pour tout entier $x$ non divisible par $137$, on a $x^{136} \equiv 1 \pmod{137}$. On en déduit pour $x^2$ :
\[ (x^2)^{136} \equiv 1 \pmod{137} \]L'ordre multiplicatif de l'élément $(x^2)$ modulo $137$ doit donc diviser simultanément l'exposant $19$ et l'exposant $136$.
Or, $19$ est un nombre premier qui ne divise pas $136$ (en effet, $136 = 8 \times 17$). Par conséquent, ces deux exposants sont premiers entre eux :
Le seul diviseur commun positif étant $1$, l'ordre de $(x^2)$ est exactement $1$. Cela signifie par définition que :
\[ (x^2)^1 \equiv 1 \pmod{137} \]Soit $x^2 \equiv 1 \pmod{137}$. On retrouve instantanément l'équation de la question 4, dont les solutions évidentes sont $x \equiv 1 \pmod{137}$ et $x \equiv -1 \pmod{137}$ (c'est-à-dire $136$).