Dans cet exposé, vous désignez par $e$ un nombre entier naturel non nul et par $p$ un nombre premier.
Lorsque $a$ et $b$ sont deux entiers relatifs avec $PGCD(a,p)=1$, vous vous intéressez à la résolution de l’équation suivante où l’inconnue $x$ est un nombre entier relatif :
\boxed{ax\equiv b\mod p^e.}Pour tout entier naturel $n$, les propositions $PGCD(n,p^e)=1$ et $PGCD(n,p)=1$ sont équivalentes
Soit $n$ un entier naturel.
Supposez que $PGCD(n,p^e)=1.$ Comme $p$ est un nombre premier, $PGCD(n,p)\in\{1,p\}.$ Si $PGCD(n,p)=p$, alors $p$ divise $n.$ Or $p$ divise $p^e.$ Donc $p$ est un diviseur commun à $n$ et à $p^e$ donc $PGCD(n,p^e)\geq p > 1$ contradiction. Donc $PGCD(n,p)=1.$
Réciproquement, supposez que $PGCD(n,p)=1.$ Si $PGCD(n,p^e)> 1$ alors $PGCD(n,p^e)$ est un entier supérieur ou égal à $2$. Il est donc divisible par un nombre premier $q.$ D’une part $q$ divise $n.$ D’autre part, $q$ divise $p^e.$ D’après le lemme d’Euclide, $q$ divise $p.$ Comme $p$ est un nombre premier, il n’admet que deux diviseurs $1$ et $p.$ Comme $q$ est premier vous avez $q\neq 1$ vous obtenez donc $q=p.$ Il en résulte que $p$ divise $n.$ Comme $p$ divise $p$, vous déduisez que $PGCD(n,p)\geq p$ donc $1\geq p$ ce qui est impossible. Donc $PGCD(n,p^e)=1.$
Est ainsi prouvé le lemme suivant :
\boxed{\forall n\in\N, PGCD(n,p^e)=1 \Longleftrightarrow PGCD(n,p)=1.}Une première équation équivalente
Vous notez $a’$ le résidu modulo $p^e$ du nombre $a$ pour obtenir :
\left\{\begin{align*}
&0\leq a'< p^e\\
&a\equiv a'\mod p^e.
\end{align*}\right.Examinez $PGCD(a’,p).$ Si $PGCD(a’,p)=p$ vous déduisez que $p$ divise $a’.$ Comme $p^e$ divise $a-a’$ et que $p$ divise $p^e$ vous en tirez que $p$ divise $a-a’.$ Par somme, il en résulte que $p$ divise $a’+(a-a’)$ donc $p$ divise $a$ et donc $PGCD(a,p)\geq p$ ce qui implique $PGCD(a,p)\neq 1$ contradiction. Comme $PGCD(a’,p)\in\{1,p\}$ vous obtenez $PGCD(a’,p)=1.$
En posant $b’=b$ par souci de cohérence des notations, l’équation de départ a été ramenée à une équation de la forme $a’x\equiv b’ \mod p^e$ avec :
L’équation $ax\equiv b\mod p^e$ est équivalente à une équation de la forme $a’x \equiv b’\mod p^e$ avec les conditions suivantes :
\left\{\begin{align*}
&0\leq a' < p^e\\
&PGCD(a',p)=1
\end{align*}\right.Le cas où $a’=0$ fait disparaître la variable $x$ et l’équation est résolue : soit il n’y a pas de solution, soit tous les entiers sont solutions. Le cas $a’=1$ est directement résolu. Il sera supposé dans la suite que :
2\leq a' < p^e.
Déterminez une autre équation équivalente
Vous cherchez à montrer que l’équation $a’x\equiv b’ \mod p^e$ va se ramener à une équation équivalente de la forme $a »x\equiv b » \mod p^e$ où $1\leq a » < a’$ et $PGCD(a »,p)=1.$
Effectuez la division euclidienne de $p^e$ par $a’$
Comme $p^e$ et $a’$ sont positifs, il existe un entier naturel $q$ et un entier positif ou nul $r$ tel que $r<a’$ avec $p^e = a’q+r.$
Si $r=0$ alors $p^e = a’q.$ Donc $p^e$ divise $a’ q.$ Or, $PGCD(a’,p)=1$ donc $PGCD(a’,p^e)=1.$ Par le théorème de Gauss, $p^e$ divise $q.$ Donc $p^e \leq q.$ Or $a’\geq 2$ donc $a’q \geq 2q$ et $p^e \geq 2q.$ donc $q\geq p^e \geq 2q$ et $q\geq 2q$ d’où $0\geq q$ donc $q=0$ et par suite $p^e = 0$ et $p=0$ contradiction. Donc $r\geq 1.$
Premier cas : $q$ n’est pas un multiple de $p$
Supposez $PGCD(r,p)> 1$ alors $PGCD(r,p)=p$ car $p$ est un nombre premier. Donc $p$ divise $r.$ Comme $a’q = p^e-r$ vous déduisez que $p$ divise $a’q.$ Or $PGCD(a’,p)=1$ donc par le théorème de Gauss $p$ divise $q$ ce qui est absurde. Donc $PGCD(r,p)=1.$
Vous posez $a » = r$ et vous avez bien $PGCD(a »,r)=1.$ Vous obtenez $1\leq a »< a’.$ Comme $p^e = a’q+r$ vous avez $r\equiv -a’q \mod p^e.$
Soit maintenant $x$ un entier relatif tel que $a’x\equiv b’ \mod p^e.$ En multipliant cette relation par $q$, vous obtenez $a’qx\equiv b’q \mod p^e.$ Vous remplacez $a’q$ par $-r$ étant entendu que $a’q\equiv -r \mod p^e.$ D’où $-rx\equiv b’q \mod p^e.$ Du coup, $rx\equiv -b’q \mod p^e.$ En posant $b » = -b’q$ vous avez obtenu $a »x\equiv b » \mod p^e.$
Réciproquement, soit $x$ un entier relatif tel que $a »x\equiv b » \mod p^e.$ Alors $rx\equiv -b’q \mod p^e.$ Du coup, $-a’qx \equiv -b’q \mod p^e$ et $a’qx\equiv b’q \mod p^e$ si bien que $p^e$ divise $q(a’x-b’).$ Supposez en raisonnant par l’absurde que $PGCD(p,q) > 1.$ Comme $p$ est un nombre premier vous obtenez $PGCD(p,q) = p$ donc $p$ divise $q$ ce qui est absurde. Donc $PGCD(p,q)=1.$ Du coup, $PGCD(p^e,q)=1.$ Via le théorème de Gauss vous déduisez que $p^e$ divise $a’x-b’$ et finalement $a’x\equiv b’\mod p^e.$
Second cas : $q$ est un multiple de $p$
L’égalité $p^e = a’q+r$ s’écrit $p^e = a'(q+1) + r-a’.$ Comme $1\leq r < a’$ vous avez $1\leq r \leq a’-1$ donc $1\leq a’-r< a’.$ Vous posez $a » = a’-r$ et vous avez $p^e = a'(q+1)-a ».$ Modulo $p^e$ cela fournit $a'(q+1)\equiv a » \mod p^e.$
Si $p$ divisait $q+1$ par différence $p$ diviserait $1$ ce qui est absurde. Donc $p$ ne divise pas $q+1.$ Par suite $PGCD(p,q+1)$ ne peut être égal à $p.$ Comme $p$ est premier vous déduisez que $PGCD(p,q+1)=1.$
Soit maintenant $x$ un entier relatif tel que $a’x\equiv b’ \mod p^e.$ En multipliant cette relation par $q+1$, vous obtenez $a'(q+1)x\equiv b'(q+1) \mod p^e.$ Vous remplacez $a'(q+1)$ par $a »$ compte tenu de la congruence $a'(q+1)\equiv a » \mod p^e.$ D’où $a »x\equiv b'(q+1) \mod p^e.$ En posant $b » = b'(q+1)$ vous avez obtenu $a »x\equiv b » \mod p^e.$
Réciproquement, soit $x$ un entier relatif tel que $a »x\equiv b » \mod p^e.$ Alors $a'(q+1)x\equiv b'(q+1) \mod p^e$ si bien que $p^e$ divise $(q+1)(a’x-b’).$ Comme $PGCD(p,q+1) =1$ vous déduisez $PGCD(p^e, q+1)=1.$ Via le théorème de Gauss vous déduisez que $p^e$ divise $a’x-b’$ et finalement $a’x\equiv b’\mod p^e.$
Il reste à examiner $PGCD(a »,p) = PGCD(a’-r,p).$ Si ce nombre est strictement supérieur à $1$ comme $p$ est premier vous avez $PGCD(a’-r,p)=p$ et $p$ divise $a’-r.$ Comme $a'(q+1)=p^e+(a’-r)$ vous déduisez que $p$ divise $a'(q+1).$ Comme $PGCD(a’,p)=1$ via le théorème de Gauss vous obtenez $p \mid q+1.$ Donc $PGCD(q+1,p) \geq p$ ce qui contredit $PGCD(q+1,p)=1.$ Ainsi, $PGCD(a »,p)=1.$
Conclusion
En notant $q$ le quotient de la division euclidienne de $p^e$ par $a’$, il suffit de multiplier l’équation $a’x\equiv b’\mod p^e$ par $q$ ou par $q+1$ pour obtenir une nouvelle équation $a »x\equiv b »\mod p^e$ équivalente à la précédente, avec le fait que $1\leq a » < a’.$ Si $q$ est un multiple de $p$ vous multipliez par $q+1$ et si $q$ n’est pas multiple de $p$ vous multipliez par $q.$
Si $a »=1$ l’équation est alors résolue. Sinon, il suffit de recommencer.
Un exemple d’application
Soit à résoudre $39x\equiv 13\mod 32$ où $x$ est un entier relatif.
$32= 2^5$ donc $32$ est bien une puissance d’un nombre premier ce qui va permettre d’appliquer successivement la méthode développée ci-dessus.
Vous remarquez que $39\equiv 7 \mod 32$ donc vous avez l’équivalence :
\forall x\in\Z, (39x\equiv 13\mod 32) \Longleftrightarrow (7x\equiv 13 \mod 32).
Vous déterminez le quotient de $32$ par $7$ il est égal à $4.$ Comme $4$ est un multiple de $2$, vous allez multiplier l’équation obtenue par $5$ ce qui fournit :
\begin{align*}
\forall x\in\Z, (7x\equiv 13 \mod 32) &\Longleftrightarrow (35x\equiv 65 \mod 32)\\
&\Longleftrightarrow (3x\equiv 1 \mod 32).
\end{align*}Le quotient de la division euclidienne de $32$ par $3$ est $10.$ Comme $10$ est un multiplie de $2$, vous multipliez la dernière équation obtenue par $11.$
\begin{align*}
\forall x\in\Z, (3x\equiv 1 \mod 32) &\Longleftrightarrow (33x\equiv 11 \mod 32)\\
&\Longleftrightarrow (x\equiv 11 \mod 32).
\end{align*}L’équation de départ est ainsi résolue.
\boxed{\forall x\in\Z, (39x\equiv 13\mod 32) \Longleftrightarrow (x\equiv 11 \mod 32).}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 !