Arithmétique : congruences, Bézout, Gauss (méthode)

Congruences modulo $n$

$a\equiv b[n]$ signifie : $n$ divise $a-b$.

Propriétés :

• Si $a\equiv b[n]$ et $c\equiv d[n]$, alors $a+c\equiv b+d[n]$ et $a\cdot c\equiv b\cdot d[n]$.
• Conséquence : on peut élever au carré, au cube, etc. : $a^k\equiv b^k[n]$.

Exemple : montrer que $n^2+n$ est pair

Cas $n\equiv 0[2]$ : $n^2+n\equiv 0+0=0[2]$. Pair.

Cas $n\equiv 1[2]$ : $n^2+n\equiv 1+1=2\equiv 0[2]$. Pair.

Donc $n^2+n$ est toujours pair.

PGCD et algorithme d'Euclide

$\text{pgcd}(a,b)=\text{pgcd}(b,r)$ où $r$ = reste de $a$ par $b$. On itère jusqu'à $r=0$.

Exemple : $\text{pgcd}(252,105)$ :

$252=2\times 105+42$ → $\text{pgcd}(105,42)$.

$105=2\times 42+21$ → $\text{pgcd}(42,21)$.

$42=2\times 21+0$ → $\text{pgcd}(21,0)=21$.

Théorème de Bézout

$a$ et $b$ sont premiers entre eux ⇔ il existe $u,v\in \mathbb{Z}$ tels que $au+bv=1$.

Plus généralement : $\text{pgcd}(a,b)=d$ ⇔ ∃ $u,v$ : $au+bv=d$.

Comment trouver $u,v$ ? En remontant l'algorithme d'Euclide (algorithme d'Euclide étendu).

Théorème de Gauss

Si $a$ divise $bc$ et $\text{pgcd}(a,b)=1$, alors $a$ divise $c$.

Application : pour résoudre $7x\equiv 3[10]$, on cherche l'inverse de 7 modulo 10. Comme $7\times 3=21\equiv 1[10]$, l'inverse est 3. Donc $x\equiv 3\times 3=9[10]$.

Équations diophantiennes : $ax+by=c$

Existe une solution ⇔ $\text{pgcd}(a,b)|c$.

Si oui : trouve une solution particulière $(x_0,y_0)$ via Bézout, puis la solution générale est :

$\{\begin{array}{l}x=x_0+k\frac{b}{d}\\ y=y_0-k\frac{a}{d}\end{array}$ avec $k\in \mathbb{Z}$, $d=\text{pgcd}(a,b)$.

Erreurs à éviter

• Confondre congruence et égalité. $a\equiv b[n]$ ne veut PAS dire $a=b$.
• Appliquer Gauss sans vérifier que $\text{pgcd}(a,b)=1$.
• Oublier l'unicité modulo $n$ : il y a une infinité de solutions à une congruence, mais une seule modulo $n$.

Plus d'exercices : arithmétique 2BAC SM.