Fiche de révision

Division euclidienne

• $a = bq + r$, avec $0 \leq r < b$.
• $a \mid b$ signifie $b = ka$.

Attention : le reste n'est jamais négatif.

Congruences

• $a \equiv b\ [n] \iff n \mid a - b$.
• On additionne, on multiplie, on élève à une puissance.

Attention : on ne divise pas dans une congruence.

Nombres premiers

• Exactement deux diviseurs positifs.
• Décomposition unique.

Attention : 1 n'est pas premier.

Fermat

• $a^{p - 1} \equiv 1\ [p]$, pour $p$ premier ne divisant pas $a$.
• $a^p \equiv a\ [p]$.

Attention : vérifie que $p$ est premier.