Divisibilité, division euclidienne, nombres premiers

$a$ divise $b$ ($a\mid b$) s'il existe $k\in\mathbb{Z}$ tel que $b=ka$. Division euclidienne : pour $a\in\mathbb{Z}, b\in\mathbb{N}^*$, il existe un unique couple $(q,r)$ tel que $a=bq+r$, $0\le r

Algorithme d'Euclide et théorème de Bézout

L'algorithme d'Euclide calcule $a\wedge b$ par divisions euclidiennes successives jusqu'au reste nul. Théorème de Bézout : $a\wedge b=d \Leftrightarrow \exists u,v\in\mathbb{Z},\ au+bv=d$ ; en particulier $a$ et $b$ sont premiers entre eux ($a\wedge b=1$) si et seulement si $\exists u,v,\ au+bv=1$. L'algorithme d'Euclide étendu (remontée des divisions) calcule explicitement $u$ et $v$. Théorème de Gauss : si $a\mid bc$ et $a\wedge b=1$, alors $a\mid c$. Petit théorème de Fermat : si $p$ premier et $p\nmid a$, alors $a^{p-1}\equiv1\pmod p$.

Équation diophantienne ax + by = c

L'équation $ax+by=c$ ($a,b,c\in\mathbb{Z}$) a des solutions dans $\mathbb{Z}^2$ si et seulement si $(a\wedge b)\mid c$. Méthode : (1) trouver une solution particulière $(x_0,y_0)$ via Bézout (ou par essais) ; (2) la solution générale est $x=x_0+\dfrac{b}{a\wedge b}k$, $y=y_0-\dfrac{a}{a\wedge b}k$, $k\in\mathbb{Z}$, obtenue en soustrayant l'équation particulière de l'équation générale et en utilisant le théorème de Gauss.

Congruences et structure de ℤ/nℤ

$a\equiv b\pmod n$ si $n\mid(a-b)$. Les congruences sont compatibles avec $+$ et $\times$ : $a\equiv b$ et $c\equiv d \Rightarrow a+c\equiv b+d$ et $ac\equiv bd \pmod n$. $\mathbb{Z}/n\mathbb{Z}=\{\overline0,\overline1,\dots,\overline{n-1}\}$ muni de $+$ et $\times$ induites. $\overline{a}$ est inversible dans $(\mathbb{Z}/n\mathbb{Z},\times)$ si et seulement si $a\wedge n=1$ ; en particulier $(\mathbb{Z}/n\mathbb{Z},+,\times)$ est un corps si et seulement si $n$ est premier.