Congruences et théorème de Fermat-Euler

Congruences et théorèmes de Fermat-Euler

1. Congruences

$a\equiv b\pmod{n}$ si $n\mid(a-b)$.

Propriétés (relation d'équivalence compatible avec les opérations) :
- $a\equiv b$ et $c\equiv d$ $\Rightarrow$ $a+c\equiv b+d$ et $ac\equiv bd\pmod n$
- $a\equiv b$ et $d\mid n$ $\Rightarrow$ $a\equiv b\pmod d$
- $\text{pgcd}(c,n)=1$ et $ac\equiv bc\pmod n$ $\Rightarrow$ $a\equiv b\pmod n$ (simplification)

2. Anneau $\mathbb{Z}/n\mathbb{Z}$

L'anneau des classes de résidus modulo $n$ est $\mathbb{Z}/n\mathbb{Z}=\{\bar0,\bar1,\ldots,\overline{n-1}\}$.

$\mathbb{Z}/n\mathbb{Z}$ est un corps ssi $n$ est premier.

Groupe des unités : $(\mathbb{Z}/n\mathbb{Z})^\times = \{\bar a : \text{pgcd}(a,n)=1\}$, d'ordre $\varphi(n)$.

3. Indicatrice d'Euler

$\varphi(n) = \text{card}\{k\in\{1,\ldots,n\} : \text{pgcd}(k,n)=1\}$.

- $\varphi(p)=p-1$ si $p$ premier
- $\varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)$
- $\varphi(mn)=\varphi(m)\varphi(n)$ si $\text{pgcd}(m,n)=1$ (multiplicativité)

4. Théorème d'Euler

Pour $\text{pgcd}(a,n)=1$ :

5. Petit théorème de Fermat

Pour $p$ premier et $p\nmid a$ :

Équivalent : $a^p \equiv a\pmod p$ pour tout $a$.

6. Théorème chinois des restes (CRT)

Si $n_1,\ldots,n_k$ sont deux à deux premiers entre eux :

Le système $x\equiv a_i\pmod{n_i}$ admet une unique solution modulo $N=n_1\cdots n_k$.