Arithmétique

PGCD et PGCM

$a / b \text{ et } a / c \Longrightarrow a / b \land c \qquad \qquad a/c \text{ et } b / c \Longrightarrow a \lor b / c \qquad \qquad a = bq + r \Longrightarrow a \land b = b \land r$

$\dfrac{a}{a \land b} \land \dfrac{b}{a \land b} = 1 \qquad \qquad ka \land kb = k(a \land b) \qquad \qquad ka \lor kb = k(a \lor b)$

Coefficients de Bezout : $(a,b) \in \mathbb{N}^2 \qquad \exists (u,v) \in \mathbb{Z}^2 \qquad au + bv = a \land b$

Théorème de Gauss : $a / bc \text{ et } a \land b = 1 \Longrightarrow a / c$

Équations diophantiennes : Soient $(a,b,c) \in \mathbb{Z}^3$ , l’équation $ax + by = c$ possède des solutions dans $\mathbb{Z}^2$ si et seulement si $a \land b / c$ .

Méthode de résolution : Soit $a'=\dfrac{a}{a \land b}$ , $b'=\dfrac{b}{a \land b}$ et $c'=\dfrac{c}{a \land b}$ . L’équation devient : $a'x + b'y = c'$ , avec $a' \land b' = 1$ .
On résout l’équation $a'x + b'y = 1$ . Les solutions sont de la forme $(x_0 + b'k , y_0 - a'k)$ , où $(x_0;y_0)$ est une solution particulière. Il suffit ensuite de multiplier les solutions par $c'$ .