Section 26

Arithmétique modulaire

intermédiaireviz

a \equiv b (mod n) ⟺ n ∣ (a - b)

Définit l'égalité des résidus modulo n.

intermédiaireviz

a \equiv b, c \equiv d (mod n) \Rightarrow a + c \equiv b + d, a c \equiv b d (mod n)

Les congruences sont préservées sous somme et produit.

intermédiaireviz

a a^{- 1} \equiv 1 (mod n) ⟺ g cd (a, n) = 1

L’inverse existe exactement lorsque a et n sont premiers entre eux.

intermédiaire

a x + b y = g cd (a, b)

Connectez le plus grand facteur commun avec des combinaisons linéaires entières.

avancéviz

x \equiv a_{i} (mod n_{i}); N = i \prod n_{i}

Les systèmes avec modules coprime ont une solution unique modulo N.

avancéviz

a^{p - 1} \equiv 1 (mod p) (p ∤ a)

Résultat central pour l'arithmétique modulaire et la cryptographie.