Arithmétique : PGCD, Bézout, Gauss

À retenir. Algorithme d'Euclide : $\operatorname{PGCD}(a,b)=\operatorname{PGCD}(b,r)$ où $r$ est le reste de la division de $a$ par $b$ ; le PGCD est le dernier reste non nul. $\operatorname{PGCD}(a,b)\times\operatorname{PPCM}(a,b)=ab$.

À retenir. $a$ et $b$ sont premiers entre eux si et seulement s'il existe des entiers $u$ et $v$ tels que $au+bv=1$. L'équation $ax+by=c$ admet des solutions entières si et seulement si $\operatorname{PGCD}(a,b)$ divise $c$.

À retenir. Gauss : si $a\mid bc$ et $\operatorname{PGCD}(a,b)=1$ alors $a\mid c$. Si $(x_0\,;y_0)$ est solution de $ax+by=c$ avec $a,b$ premiers entre eux, les solutions sont $x=x_0+bt$ et $y=y_0-at$ ($t$ entier).