Fiche de révision

PGCD

• $\mathrm{PGCD}(a ; b) = \mathrm{PGCD}(b ; r)$.
• Dernier reste non nul.

Attention : ne confonds pas avec le dernier quotient.

Bézout

• $au + bv = 1 \iff \mathrm{PGCD}(a ; b) = 1$.
• On remonte l'algorithme d'Euclide.

Attention : le couple $(u ; v)$ n'est pas unique.

Gauss

• Si $a \mid bc$ et $\mathrm{PGCD}(a ; b) = 1$, alors $a \mid c$.
• Base des équations diophantiennes.

Attention : vérifie toujours « premiers entre eux ».

Inverse modulo $n$

• Il existe si $\mathrm{PGCD}(a ; n) = 1$.
• $ax \equiv b \iff x \equiv a'b\ [n]$.

Attention : on multiplie, on ne divise pas.

Équations diophantiennes

• Existence : $\mathrm{PGCD}(a ; b) \mid c$.
• Solution particulière, puis Gauss.

Attention : il y a une infinité de solutions.