Arithmétique des entiers

Division euclidienne

Soit $a$ et $b$ deux entiers relatifs. On dit que $a$ divise $b$, ou que a est un diviseur de $b$ s'il existe $k\in\mathbb Z$ tel que $b=ka$. On dit encore que $b$ est un multiple de $a$.

Théorème (division euclidienne) : Soient $(a,b)\in\mathbb Z^2$ avec $b\neq 0$. Il existe un unique couple $(q,r)\in\mathbb Z^2$ tels que $$\left\{ \begin{array}{l} a=bq+r\\ 0\leq r< |b|. \end{array} \right. $$ $q$ s'appelle le quotient et $r$ s'appelle le reste.

pgcd,ppcm

Si $a$ et $b$ sont deux entiers relatifs dont l'un au moins est non-nul, alors le pgcd de $a$ et $b$, noté $a\wedge b,$ est le plus grand élément, pour $\leq$, de l'ensemble des diviseurs communs de $a$ et $b$. Par convention, on pose $0\wedge 0=0$.

Théorème (algorithme d'Euclide) : Soit $a$ et $b$ deux entiers relatifs avec $b\neq 0$. Soit $r$ le reste dans la division euclidienne de $a$ par $b$. Alors $a\wedge b=b\wedge r$.

On en déduit l'algorithme suivant pour calculer $a\wedge b$ lorsque $a\geq b\geq 0$. On pose $r_0=a$ et $r_1=b$. Pour $i\in\mathbb N^*$, si $r_i\neq 0$, on note $r_{i+1}$ le reste de la division euclidienne de $r_{i-1}$ par $r_i$. Tant qu'elle ne devient pas nulle, la suite $(r_i)$ est une suite strictement décroissante d'entiers naturels. Elle finit donc par s'annuler. Le dernier reste non nul est $a\wedge b$.

Proposition : Soit $a,b,d\in\mathbb Z$. On a $(d|a\textrm{ et }d|b)\iff d|a\wedge b$.

Autrement dit, l'ensemble des diviseurs communs de $a$ et de $b$ est égal à l'ensemble des diviseurs de leur pgcd $a\wedge b$.

Proposition (relation de Bézout) : Soit $a,b\in\mathbb Z$. Alors il existe $(u,v)\in\mathbb Z^2$ tel que $au+bv=a\wedge b$.

Proposition : Si $a,b,k\in (\mathbb Z\backslash\{0\})^3$, alors $(ka)\wedge (kb)=|k|(a\wedge b)$.

Si $a$ et $b$ sont deux entiers relatifs, le ppcm de $a$ et $b$, noté $a\vee b$, est le plus petit multiple commun positif de $a$ et $b$, au sens de $\leq$.

Proposition : Pour tout couple d'entiers relatifs $(a,b)$, on a $$|ab|=(a\wedge b)(a\vee b).$$

Comme un diviseur de $a$ et de $b$ est un diviseur de $a\wedge b$, un multiple de $a$ et $b$ est un multiple de $a\vee b$.

Théorème : Soit $a,b,m\in\mathbb Z$. Alors $m$ est un multiple commun de $a$ et de $b$ si et seulement si $m$ est un multiple de $a\vee b$.

Nombres premiers entre eux

On dit que deux entiers relatifs sont premiers entre eux si leur pgcd vaut 1.

Théorème de Bézout : Soit $(a,b)\in\mathbb Z^2$. On a $$a\wedge b=1\iff \exists (u,v)\in\mathbb Z^2,\ au+bv=1.$$

Théorème de Gauss : Soit $(a,b,c)\in\mathbb Z^3$. On suppose que $a|bc$ et $a\wedge b=1$, alors $a|c$.

Corollaire : Soit $a,b,n\in\mathbb Z$.

Si $a|n$, $b|n$ et $a\wedge b=1$, alors $ab|n$.
Si $a\wedge n=1$ et si $b\wedge n=1$, alors $ab\wedge n=1$.

Le théorème de Gauss permet aussi de démontrer que tout rationnel $r\in\mathbb Q^*$ s'écrit de manière unique $r=\frac pq$ avec $p\in\mathbb Z$, $q\in\mathbb N^*$ et $p\wedge q=1$. Cette écriture s'appelle la forme irréductible de $r$.

Nombres premiers

Un entier $p\geq 2$ est dit premier si ses seuls diviseurs positifs sont $1$ et $p$.

Proposition : Soit $n\in\mathbb N$ tel que $n\geq 2$. Alors $n$ admet au moins un diviseur premier. De plus, si $n$ n'est pas premier, alors il admet un diviseur premier inférieur ou égal à $\sqrt n$.

Théorème : L'ensemble des nombres premiers est infini.

Théorème fondamental de l'arithmétique : Tout entier $n\geq 2$ s'écrit de manière unique $n=p_1^{\alpha_1}\cdots p_r^{\alpha_r}$ où $p_1<p_2<\dots<p_r$ sont des nombres premiers et $\alpha_1,\dots,\alpha_k$ sont dans $\mathbb N^*$. On dit que $n=p_1^{\alpha_1}\cdots p_r^{\alpha_r}$ est la décomposition en produit de facteurs premiers de $n$.

Si $n\geq 2$ et $p$ est un nombre premier, on appelle valuation $p$-adique de $n$, et on note $v_p(n)$, le plus grand entier $k\geq 0$ tel que $p^k|n$. La valuation $p$-adique de $n$ est l'exposant de $p$ dans la décomposition en produit de facteurs premiers de $n$.

Proposition : Soit $a,b\geq 2$ et $p$ un nombre premier. Alors $v_p(ab)=v_p(a)+v_p(b)$.

Application à la divisibilité, au calcul du pgcd et du ppcm : si $a,b\geq 2$ se décomposent sous la forme $$a=p_1^{\alpha_1}\cdots p_r^{\alpha_r}$$ $$b=p_1^{\beta_1}\cdots p_r^{\beta_r}$$ où les $p_i$ sont des nombres premiers et $\alpha_i,\beta_i\in\mathbb N$, alors \begin{eqnarray*} a|b&\iff&\forall i\in\{1,\dots,r\},\ \alpha_i\leq \beta_i\\ a\wedge b&=&p_1^{\min(\alpha_1,\beta_1)}\cdots p_r^{\min(\alpha_r,\beta_r)}\\ a\vee b&=&p_1^{\max(\alpha_1,\beta_1)}\cdots p_r^{\max(\alpha_r,\beta_r)}. \end{eqnarray*}

Congruences

Soient $a$ et $b$ deux entiers relatifs et $n$ un entier naturel. On dit que $a$ et $b$ sont congrus modulo n s'il existe $k\in\mathbb Z$ tel que $a-b=kn$. On note $$a\equiv b\ [n].$$

La relation "être congrue modulo $n$", qui est une relation d'équivalence, est compatible avec les opérations $+,\times$ : $$\left\{ \begin{array}l a\equiv b\ [n]\\ c\equiv d\ [n] \end{array} \right. \implies \left\{ \begin{array}l a+c\equiv b+d\ [n]\\ a\times c\equiv b\times d\ [n] \end{array}\right. $$

Petit théorème de Fermat : Si $p$ est un nombre premier et $a\in \mathbb Z$, alors $a^{p}\equiv a\ [p]$. De plus, si $p$ ne divise pas $a$, alors $a^{p-1}\equiv 1\ [p]$.

Arithmétique et sous-groupes de $\mathbb Z$

Théorème : Les sous-groupes de $\mathbb Z$ sont les $n\mathbb Z$, avec $n\in\mathbb N$.
Théorème : Soit $a,b$ deux entiers tels que $(a,b)\neq (0,0)$. Alors $a\mathbb Z+b\mathbb Z$ et $a\mathbb Z\cap b\mathbb Z$ sont deux sous-groupes de $\mathbb Z$. Soit $d,m\in\mathbb N$ tels que \begin{align*} a\mathbb Z+b\mathbb Z&=d\mathbb Z\\ a\mathbb Z\cap b\mathbb Z&=m\mathbb Z. \end{align*} Alors $d=a\wedge b$ et $m=a\vee b$.
Le théorème précédent contient en particulier la moitié du théorème de Bézout : si $a\wedge b=1$, alors $a\mathbb Z+b\mathbb Z=\mathbb Z$, et donc il existe $(u,v)\in\mathbb Z^2$ avec $au+bv=1$.

Anneaux $\mathbb Z/n\mathbb Z$

Théorème : Les idéaux de $\mathbb Z$ sont les ensembles $n\mathbb Z$ pour $n\in\mathbb N$.
Soit $n\geq 2$. La relation de congruence modulo $n$ est une relation d'équivalence sur $\mathbb Z$ : $a\equiv b\ [n]\iff a-b\in n\mathbb Z$. On note $\bar a$ la classe d'équivalence de $a$, et $\mathbb Z/n\mathbb Z$ l'ensemble des classes d'équivalence pour cette relation. On a en particulier $\mathbb Z/n\mathbb Z=\{\bar 0,\bar 1,\dots,\overline {n-1}\}.$
Théorème : On munit $\mathbb Z/n\mathbb Z$ d'une structure d'anneaux en posant $$\bar a+\bar b=\overline{a+b}$$ $$\bar a\times \bar b=\overline{a\times b}.$$
Théorème : $\bar k$ est inversible dans $\mathbb Z/n\mathbb Z$ si et seulement $k\wedge n=1$.
Corollaire : $(\mathbb Z/n\mathbb Z,+,\times)$ est un corps si et seulement si $n$ est premier.
Théorème chinois : Si $n,m\geq 2$ sont premiers entre eux, alors l'anneau produit $\mathbb Z/n\mathbb Z\times \mathbb Z/m\mathbb Z$ est isomorphe à l'anneau $\mathbb Z/nm\mathbb Z$.
Le théorème des restes chinois peut encore se reformuler de la façon suivante en termes de congruences :
Théorème des restes chinois : Soit $m$ et $n$ des entiers premiers entre eux. Alors, pour tout $(a,b)\in\mathbb Z^2$, le système $$\left\{ \begin{array}{rcl} x&\equiv&a\ [m]\\ x&\equiv&b\ [n] \end{array}\right.$$ admet au moins une solution. De plus, si $x_0$ est une solution particulière, l'ensemble des solutions est $\{x_0+kmn;\ k\in\mathbb Z\}.$