Congruences

Le théorème qui est derrière tout ça est le théorème de Bézout, que tu dois connaître.

Plus généralement, soient $a,b,n \in \mathbb{N}^*$ et l'on suppose $\textrm{pgcd}(a,n) = 1$. Alors l'équation $ax \equiv b \pmod n$ a une solution, unique si l'on se restreint à $\{0,\dotsc,n-1\}$, donnée par $x \equiv ub \pmod n$, où $u$ est un coefficient de Bézout de $a$ dans l'égalité $\textrm{pgcd}(a,n) = 1$.

Exemple. $a=5$, $b=1$ et $n=336$. On peut prendre par exemple $u=-67$ et l'on obtient $x=269$.

Démonstration. Puisque $\textrm{pgcd}(a,n) = 1$, il existe $u,v \in \mathbb{Z}$ tels que $au+nv = 1$, et donc $aub + nvb=b$. Soit $x$ une solution. Puisque $ax \equiv b \pmod n$, il existe $k \in \mathbb{Z}$ tel que $ax=b+nk$. Ainsi
$$aub + nvb = ax - nk \Longleftrightarrow a \left( x-ub \right) = n \left( k + bv \right)$$
d'où l'on déduit que $n$ divise $a \left( x-ub \right)$ et comme $\textrm{pgcd}(a,n) = 1$, le théorème de Gauss implique que $n \mid x-ub$, ou encore $x \equiv ub \pmod n$. Réciproquement, on vérifie que les nombres $x \equiv ub \pmod n$ sont solutions, ce qui est facile car, de l'égalité $au+nv = 1$, il vient $au \equiv 1 \pmod n$, et donc $ax \equiv aub \equiv b \pmod n$.

Si $a>0$ est premier avec $p>0$ et si on veut résoudre l'équation $ax\equiv 1\mod{p}$.

Cela revient à trouver un couple de nombres entiers solution de l'équation:

$ax+py=1$

Et l'algorithme d'Euclide étendu permet de trouver un couple de solution $(x,y)$.

(algorithme au programme de la classe de terminale S sauf erreur de ma part)

En suivant ce que je t'ai dit plus haut, il n'est pas difficile d'élaborer un petit algorithme, sur TI-82 ou Casio 35 +, qui lit trois entiers $a,b,n$ avec $a$ et $n$ premiers entre eux et qui affiche une solution $x$ de la congruence $ax \equiv b \pmod n$.