Skip to content

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'.

Autres propriétés

Tout entier supérieur ou égal à 2 possède au moins un diviseur premier.

Soit n \in \mathbb{N}, non premier, alors n possède un diviseur premier p tel que p^2 \le n.

Soit p un nombre premier. \forall n \in \mathbb{N}^* tel que n < p alors p / \binom{p}{n}.

CONGRUENCES

    \[ a \equiv b \pod n \implies  \begin{cases} a + c \equiv b + c \pod n \\ ac \equiv bc \pod n \\ a^p \equiv b^p \pod n \end{cases}$ \]

Petit théorème de Fermat : p premier ne divisant pas a, alors a^{p-1} \equiv 1 \pod p.
Si p divise a alors a^p \equiv a \pod p