Soit $k$ un entier naturel non nul. Dans cette section, 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$ dans le cas où $k=4$ ?
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^2\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 $k$ tel que $t=2k$ et par suite $x=-1+16k$ 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$ en 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$, alors $x^2\equiv 1\mod 16.$
Si $x\equiv 1\mod 16$, alors $x^2\equiv 1\mod 16.$
Si $x\equiv 3\mod 16$, alors $x^2\equiv 9\mod 16.$
Si $x\equiv 5\mod 16$, alors $x^2\equiv 25\mod 16$ et $x^2\equiv 9\mod 16.$
Si $x\equiv 7\mod 16$, alors $x^2\equiv 49 \mod 16$ et $x^2\equiv 1 \mod 16.$
Si $x\equiv 9\mod 16$, 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$, alors $x\equiv -5\mod 16$ alors $x^2\equiv 25 \mod 16$ et $x^2\equiv 9 \mod 16.$
Si $x\equiv 13\mod 16$, alors $x\equiv -3\mod 16$ alors $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 $\mathscr{P}(n).$
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 $k$ tel que $b\times 2^n = k\times 2^{n+1}.$ En divisant par $2^n$ vous obtenez $b = 2k$ 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}).De ces deux implications, il en résulte que $\mathscr{P}(n+1)$ est vraie.
Conclusion. Par récurrence vous avez montré que pour tout entier $n$ supérieur ou égal à $3$, 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$, 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 :
\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}).Partagez !
Diffusez cet article auprès de vos connaissances susceptibles d'être concernées.
Aidez-moi sur Facebook !
Vous appréciez cet article et souhaitez témoigner du temps que j'y ai passé pour le mettre en œuvre. C'est rapide à faire pour vous et c'est important pour moi, déposez un j'aime sur ma page Facebook. Je vous en remercie par avance.
Lisez d'autres articles !
Parcourez tous les articles qui ont été rédigés. Vous en trouverez sûrement un qui vous plaira !