Dans ce contenu, 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\comma$ vous vous intéressez à la résolution de l’équation suivante où l’inconnue $x$ est un nombre entier relatif :

Pour tout entier naturel $n\comma$ 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\comma$ 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 \gt 1$ contradiction. Donc $\pgcd(n,p)=1.$

Réciproquement, supposez que $\pgcd(n,p)=1.$ Si $\pgcd(n,p^e)\gt 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 positifs, $1$ et $p.$ Comme $q$ est premier vous avez $q\neq 1\comma$ vous obtenez donc $q=p.$ Il en résulte que $p$ divise $n.$ Comme $p$ divise $p\comma$ 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 :

Une première équation équivalente

Vous notez $a’$ le résidu modulo $p^e$ du nombre $a$ pour obtenir :

Comme $a\equiv a’\mod p^e\comma$ pour tout entier relatif $x$ vous avez $ax\equiv a’x\mod p^e.$

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 $ax\equiv b\mod p^e$ est équivalente à une équation de la forme $a’x \equiv b’\mod p^e$ avec les conditions suivantes :

Le cas $a’=0$ est exclu puisque $\pgcd(0,p)=p$ et que $p\neq 1.$ Le cas $a’=1$ est directement résolu. Il sera supposé dans la suite que :

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 » \lt 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$ tels que $r\lt 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.$ Comme $q$ est non nul puisque $p^e = a’q \gt 0\comma$ vous avez $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)\gt 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 »,p)=1.$ Vous obtenez $1\leq a »\lt 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\comma$ 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) \gt 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 \lt a’$ vous avez $1\leq r \leq a’-1$ donc $1\leq a’-r\lt 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\comma$ comme $p$ divise $q\comma$ 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\comma$ 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’\comma$ 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 » \lt 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. Les coefficients successifs formant une suite d’entiers naturels non nuls strictement décroissante, le procédé s’arrête au bout d’un nombre fini d’étapes avec un coefficient égal à $1.$

Un exemple d’application

Soit à résoudre $39x\equiv 13\mod 32$ où $x$ est un entier relatif.

Le nombre $32= 2^5$ est 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 :

Le quotient de la division euclidienne de $32$ par $7$ est égal à $4.$ Comme $4$ est un multiple de $2\comma$ vous allez multiplier l’équation obtenue par $5$ ce qui fournit :

Le quotient de la division euclidienne de $32$ par $3$ est $10.$ Comme $10$ est un multiple de $2\comma$ vous multipliez la dernière équation obtenue par $11.$

L’équation de départ est ainsi résolue.