École AVOSZ

Connectez-vous

364. Déterminez les nombres dont le carré vaut 1 modulo une puissance de 2

Yannis TRIANTAPHYLIDES

Soit $k$ un entier naturel non nul. Dans ce contenu, vous vous intéressez à la résolution de l’équation :

x^2\equiv 1\mod 2^k.

Traitez le cas où $k=1$

Comme $2^k = 2$ vous calculez tous les carrés modulo $2.$

\begin{array}{|c|c|c|} \hline x \mod 2 & 0 & 1\\ \hline x^2 \mod 2 & 0 & 1\\ \hline \end{array}

Vous obtenez donc :

\boxed{\forall x\in\Z, (x^2\equiv 1\mod 2) \Longleftrightarrow (x\equiv 1 \mod 2).}

Traitez le cas où $k=2$

Comme $2^2 = 4$ vous calculez tous les carrés modulo $4.$

\begin{array}{|c|c|c|c|c|} \hline x \mod 4 & 0 & 1 & 2 & -1\\ \hline x^2 \mod 4 & 0 & 1 & 0 & 1\\ \hline \end{array}

Vous obtenez donc :

\boxed{\forall x\in\Z, (x^2\equiv 1\mod 4) \Longleftrightarrow (\exists a\in\{-1,1\}, x\equiv a \mod 4).}

Traitez le cas où $k=3$

Comme $2^3 = 8$ vous calculez tous les carrés modulo $8.$

\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline x \mod 8 &-1 & 0 & 1 & 2 & 3 & 4 & 5 & 6\\ \hline x^2 \mod 8 & 1 & 0 & 1 & 4 & 1& 0 & 1 & 4\\ \hline \end{array}

Vous obtenez donc :

\boxed{\forall x\in\Z, (x^2\equiv 1\mod 8) \Longleftrightarrow (\exists a\in\{-1,1, 3, 5\}, x\equiv a \mod 8).}

Et après, que se passe-t-il modulo $16$ lorsque l’entier $k$ vaut quatre ?

Vous pourriez penser que le nombre de solutions modulo $2^4=16$ serait égal à $8$ comme le suggère cette analyse.

Analyse. Soit $x$ un nombre entier relatif tel que :

x^2\equiv 1 \mod 16.

Comme $8\mid 16$ et que $16 \mid x^2-1$ il vient $8\mid x^2-1$ et du coup :

x^2\equiv 1 \mod 8.

En appliquant le résultat précédent, vous déduisez qu’il existe $a\in\{-1, 1, 3,5\}$ tel que $x\equiv a \mod 8.$

Cas n°1. $x\equiv -1\mod 8.$ Il existe un entier relatif $t$ tel que $x=-1+8t.$ Si $t$ est pair, il existe un entier relatif $m$ tel que $t=2m$ et par suite $x=-1+16m$ et $x\equiv -1\mod 16.$ Si $t$ est impair, il existe un entier relatif $\ell$ tel que $t = 2\ell+1$ et par suite $x = -1+8(2\ell+1) = 7+16\ell$ et $x\equiv 7\mod 16.$

Cas n°2. $x\equiv 1\mod 8.$ En reprenant la démarche du cas précédent, vous déduisez que soit $x\equiv 1\mod 16$ soit $x\equiv 9\mod 16.$

Cas n°3. $x\equiv 3\mod 8.$ De même, vous déduisez que soit $x\equiv 3\mod 16$ soit $x\equiv 11\mod 16.$

Cas n°4. $x\equiv 5\mod 8.$ De même, vous avez : soit $x\equiv 5\mod 16$ soit $x\equiv 13\mod 16.$

Le résultat suivant est ainsi établi :

\boxed{\forall x\in\Z, (x^2\equiv 1\mod 16) \implies (\exists a\in\{-1,1, 3, 5, 7, 9, 11, 13\}, x\equiv a \mod 16).}

Il y a huit candidats potentiels.

Synthèse. Soit $x$ un entier relatif.

Si $x\equiv -1\mod 16\comma$ alors $x^2\equiv 1\mod 16.$

Si $x\equiv 1\mod 16\comma$ alors $x^2\equiv 1\mod 16.$

Si $x\equiv 3\mod 16\comma$ alors $x^2\equiv 9\mod 16.$

Si $x\equiv 5\mod 16\comma$ alors $x^2\equiv 25\mod 16$ et $x^2\equiv 9\mod 16.$

Si $x\equiv 7\mod 16\comma$ alors $x^2\equiv 49 \mod 16$ et $x^2\equiv 1 \mod 16.$

Si $x\equiv 9\mod 16\comma$ alors $x\equiv -7\mod 16$ donc $x^2\equiv 49 \mod 16$ et $x^2\equiv 1 \mod 16.$

Si $x\equiv 11\mod 16\comma$ alors $x\equiv -5\mod 16$ donc $x^2\equiv 25 \mod 16$ et $x^2\equiv 9 \mod 16.$

Si $x\equiv 13\mod 16\comma$ alors $x\equiv -3\mod 16$ donc $x^2 \equiv 9 \mod 16.$

Parmi les $8$ candidats, il n’y en a que quatre qui conviennent.

Conclusion. Par analyse-synthèse, il vient d’être démontré que :

\boxed{\forall x\in\Z, (x^2\equiv 1\mod 16) \Longleftrightarrow (\exists a\in\{-1,1, 7, 9\}, x\equiv a \mod 16).}

Le nombre de solutions modulo $16$ reste finalement égal à $4.$ Vous allez montrer que cela se généralise.

Passez au cas général en étudiant la situation pour $k\geq 3$

Dans cette section, vous supposez que $k$ est un entier supérieur ou égal à $3.$

Pour tout entier $n\geq 3$ vous notez $\mathscr{P}(n)$ la propriété suivante :

\boxed{\forall x\in\Z, (x^2\equiv 1\mod 2^n) \Longleftrightarrow (\exists a\in\left\{-1,1, -1+2^{n-1}, 1+2^{n-1}\right\}, x\equiv a \mod 2^n).}

Initialisation. Il a été démontré ci-dessus que :

\forall x\in\Z, (x^2\equiv 1\mod 8) \Longleftrightarrow (\exists a\in\{-1,1, 3, 5\}, x\equiv a \mod 8).

Comme $3 = -1+2^{3-1}$ et $5 = 1+2^{3-1}$ vous en déduisez que $\mathscr{P}(3)$ est vérifiée.

Hérédité. Soit $n$ un entier supérieur ou égal à $3.$ Supposez que $\mathscr{P}(n)$ soit vraie.

Soit $x$ un entier relatif tel que $x^2\equiv 1 \mod 2^{n+1}.$

Comme $2^n \mid 2^{n+1}$ vous déduisez $x^2\equiv 1 \mod 2^n.$ D’après l’hypothèse de récurrence, il existe un entier $a\in \left\{-1,1, -1+2^{n-1}, 1+2^{n-1}\right\}$ tel que $x\equiv a\mod 2^n.$

Cas n°1. $a\in\{-1,1\}.$ De $x\equiv a \mod 2^n$ vous déduisez l’existence d’un entier relatif $t_1$ tel que $x = a+2^n t_1.$ Si $t_1$ est pair, il existe un entier relatif $k_1$ tel que $t_1 = 2k_1$ et par suite $x=a+2^{n+1}k_1$ et $x\equiv a\mod 2^{n+1}.$

Si $t_1$ est impair il existe un entier relatif $\ell_1$ tel que $t_1 = 1+2\ell_1$ et par suite $x = a+2^n(1+2\ell_1)$ d’où $x=a+2^n+2^{n+1}\ell_1$ et $x\equiv a+2^n \mod 2^{n+1}.$

Cas n°2. $a\in\{-1+2^{n-1}, 1+2^{n-1}\}.$ Il existe $b\in\{-1,1\}$ tel que $a = b+2^{n-1}.$ Comme $x\equiv a \mod 2^n$ vous déduisez qu’il existe un entier relatif $t$ tel que $x = a+2^n t$ ce qui donne $x = b+2^{n-1}+2^n t.$ En élevant au carré, il vient :

\begin{align*} x^2 &= b^2+2^{2n-2}+t^2\times 2^{2n}+b2^{n}+bt\times2^{n+1}+t\times 2^{2n}\\ &= b^2+2^{n+1}2^{n-3}+t^2\times 2^{n+1}2^{n-1}+b\times 2^n+bt\times 2^{n+1}+t\times 2^{n+1}2^{n-1}. \end{align*}

Comme $n\geq 3$ tous les exposants qui apparaissent dans les puissances de $2$ sont positifs ou nuls. Modulo $2^{n+1}$ vous obtenez :

x^2\equiv b^2+b\times 2^n\mod 2^{n+1}.

Or, $b^2=1$ donc :

x^2\equiv 1+b\times 2^n\mod 2^{n+1}.

Comme $x^2\equiv 1 \mod 2^{n+1}$ vous déduisez :

\begin{align*} 1 \equiv 1+b\times 2^n \mod 2^{n+1}\\ b\times 2^n \equiv 0 \mod 2^{n+1}. \end{align*}

Il existe un entier relatif $m$ tel que $b\times 2^n = m\times 2^{n+1}.$ En divisant par $2^n$ vous obtenez $b = 2m$ donc $b$ est pair. Or, $b\in\{-1,1\}$ d’où une contradiction. Ainsi le cas n°2 ne peut se produire.

Vous déduisez l’implication suivante :

\forall x\in\Z, (x^2\equiv 1\mod 2^{n+1}) \implies (\exists u\in\left\{-1,1, -1+2^{n}, 1+2^{n}\right\}, x\equiv u \mod 2^{n+1}).

Il reste à montrer la réciproque.

Soit $x$ un entier relatif.

S’il existe $a\in\{-1,1\}$ tel que $x\equiv a \mod 2^{n+1}$ alors $x^2\equiv a^2\mod 2^{n+1}.$ Or $a^2=1$ donc $x^2\equiv 1 \mod 2^{n+1}.$

S’il existe $a\in\{-1,1\}$ tel que $x\equiv a+2^n \mod 2^{n+1}$ alors :

\begin{align*} x^2\equiv a^2+2^{2n}+a\times 2^{n+1} \mod 2^{n+1}\\ x^2\equiv a^2+2^{n+1}2^{n-1}+a\times 2^{n+1} \mod 2^{n+1}\\ x^2 \equiv a^2 \mod 2^{n+1}. \end{align*}

Comme $a^2=1$ vous obtenez encore $x^2\equiv 1 \mod 2^{n+1}.$

Vous avez démontré ce qui suit :

\forall x\in\Z, (x^2\equiv 1\mod 2^{n+1}) \impliedby (\exists u\in\left\{-1,1, -1+2^{n}, 1+2^{n}\right\}, x\equiv u \mod 2^{n+1}).

Il résulte de ces deux implications que $\mathscr{P}(n+1)$ est vraie.

Conclusion. Par récurrence vous avez montré que pour tout entier $n$ supérieur ou égal à $3\comma$ vous avez :

\forall x\in\Z, (x^2\equiv 1\mod 2^{n}) \Longleftrightarrow (\exists u\in\left\{-1,1, -1+2^{n-1}, 1+2^{n-1}\right\}, x\equiv u \mod 2^{n}).

Comme l’entier $k$ est supérieur ou égal à $3\comma$ le résultat final est ainsi établi :

\boxed{\forall x\in\Z, (x^2\equiv 1\mod 2^{k}) \Longleftrightarrow (\exists a\in\left\{-1,1, -1+2^{k-1}, 1+2^{k-1}\right\}, x\equiv a \mod 2^{k}).}

Prolongement

Vous pouvez aussi regrouper les solutions en visant une approche qui conserve les opposés.

Adaptez alors la démonstration précédemment effectuée pour justifier que, pour tout entier $k\geq 3\comma$ vous avez :

\forall x\in\Z, (x^2\equiv 1\mod 2^{k}) \Longleftrightarrow (\exists a\in\left\{1, 1+2^{k-1}\right\}, x\equiv \pm a \mod 2^{k}).