Notions d’arithmétique modulaire

a mod m est le reste de la division entière de a par m (0 ≤ a mod m ≤ m − 1). a ≡ b(mod m) si m divise (b − a). lem.: a ≡ b(mod m) ssi a mod m = b mod m. Exemple : 143 mod 5? −18 mod 7? pgcd est le plus grand commun diviseur.

\begin{matrix}ℤ_{m} = \{0, …, m − 1\} \\ x op_{m} y : x op y mod m avec op ∈ \{+, −, ∗\} \end{matrix}

La fonction indicatrice d’Euler ϕ(m) est définie par le nombre d’entiers de ℤ_{m} qui sont premiers avec m.

Soit a ∈ ℤ_{m}, a^{−1} ∈ ℤ_{m} est l’inverse de a si a∗_{m}a^{−1} ≡ a^{−1} ∗_{m} a ≡ 1(mod m).

Th.: Un nombre a admet un inverse dans ℤ_{m} si et seulement si pgcd(a, m) = 1 (i.e. a et m sont premiers entre-eux).

Algo. d’Euclide : Le plus grand commun diviseur de deux nombres b et a (b > a) est donné par la définition récursive suivante :

pgcd(a, b) = \{ \begin{matrix}a si b mod a = 0 \\ pgcd(b mod a, a) sinon \end{matrix}

Algo. d’Euclide étendu : L’inverse de x dans ℤ_{m} si il existe est x_{m}^{−1} = inverse(x, m, 0, 1, m) avec :

inverse(u, v, t, t′, m) t′ si v mod u = 0 et u = 1 ⊥ si v mod u = 0 et u ≠ 1 inverse(v mod u, u, t′, (t − (v div u) ∗ t′) mod m, m)