Définition

Soient $a$ et $b$ deux entiers relatifs. On dit que $b$ divise $a$ (ou que $a$ est un multiple de $b$) s’il existe $k\in \mathbb{Z}$ tel que $a=kb$. On note ceci par $b\mid a$.

Propriétés

• Tout entier relatif $b$ divise $0$ (car $0=0\times b$).

• $1$ divise tout entier relatif $a$ (car $a=a\times 1$).

• Si $c\mid a$ et $c\mid b$ alors $c\mid (au+bv)$ pour tout $u$, $v\in \mathbb{Z}$.

Théorème de la division euclidienne

Soient $a$, $b\in \mathbb{Z}$. On suppose $b\ne 0$. On appelle division euclidienne de $a$ par $b$, l’opération qui à $(a,b)$, associe le couple d’entiers relatifs $(q,r)$ tel que $a=bq+r$ où $0\le r<|b|$. Un tel couple existe forcément et est unique.

Vocabulaire

En reprenant les notations du théorème, $a$ s’appelle le dividende, $b$ le diviseur, $q$ le quotient et $r$ le reste de la division euclidienne.

Propriété

Soit $n\in \mathbb{N}$ tel que $n\ne 0$. Deux entiers relatifs $a$ et $b$ ont le même reste dans la division euclidienne par $n$ si et seulement si $a-b$ est un multiple de $n$.

Définition

On dit que deux entiers relatifs $a$ et $b$ sont congrus modulo $n$ (où $n$ est un entier naturel supérieur ou égal à $2$) si $a$ et $b$ ont le même reste dans la division euclidienne par $n$. On note alors $a\equiv b\mathrm{mod}n$.

Propriétés

Soit $n\ge 2$. Pour tout $a$, $b$, $c\in \mathbb{Z}$ :

• $a\equiv a\mathrm{mod}n$ (réflexivité)

• Si $a\equiv b\mathrm{mod}n$, alors $b\equiv a\mathrm{mod}n$ (symétrie)

• Si $a\equiv b\mathrm{mod}n$, et si $b\equiv c\mathrm{mod}n$, alors $a\equiv c\mathrm{mod}n$ (transitivité)

Propriétés

Soit $n\ge 2$. Soient $a$, $b$, $c$ et $d\in \mathbb{Z}$ tels que $a\equiv b\mathrm{mod}n$ et $c\equiv d\mathrm{mod}n$. Alors on a la compatibilité avec :

• L’addition : $a+c\equiv b+d\mathrm{mod}n$.

• La multiplication : $ac\equiv bd\mathrm{mod}n$.

• Les puissances : pour tout $k\in \mathbb{N}$, $a^k\equiv b^k\mathrm{mod}n$.

Définition

Soient $a$, $b\in \mathbb{Z}$ non tous nuls. Le Plus Grand Commun Diviseur de $a$ et $b$ (noté $\mathrm{PGCD}(a;b)$) est le plus grand entier positif qui les divise simultanément.

Propriétés

Soient $a$, $b\in \mathbb{Z}$ non tous nuls.

• $\mathrm{PGCD}(a;b)=\mathrm{PGCD}(b;a)$

• $\mathrm{PGCD}(a;1)=1$

• $\mathrm{PGCD}(a;0)=a$

• Pour tout $k\in \mathbb{N}$, $\mathrm{PGCD}(ka;kb)=k\mathrm{PGCD}(a;b)$

• Si $b\mid a$, alors $\mathrm{PGCD}(a;b)=|b|$

Algorithme d’Euclide

Soient $a$, $b\in \mathbb{Z}$ non tous nuls. Pour obtenir $\mathrm{PGCD}(a;b)$, on procède comme suit :

1. On fait la division euclidienne de $a$ par $b$ et on appelle $r$ le reste.

2. Si $r=0$, alors $\mathrm{PGCD}(a;b)=b$.

3. Sinon on recommence l’étape 1 en remplaçant $a$ par $b$ et $b$ par $r$.

Nombres premiers entre eux

On dit que deux nombres sont premiers entre eux si leur $\mathrm{PGCD}$ est égal à 1.

Théorème de Bachet-Bézout

Soient $a$ et $b$ deux entiers relatifs non nuls. On note $d$ leur PGCD. Alors il existe deux entiers relatifs $u$ et $v$ tels que $ua+vb=d$.

Théorème de Bézout

Une conséquence de ce théorème est que $a$ et $b$ sont premiers entre eux si et seulement s’il existe deux entiers relatifs $u$ et $v$ tels que $ua+vb=1$.

Résolution d’une congruence simple

Supposons que l’on souhaite résoudre une congruence du type $ax\equiv b\mathrm{mod}n$ d’inconnue $x$. On pose $d=PGCD(a;n)$. Alors :

1. Si $d$ ne divise pas $b$, on cherche deux entiers $u$ et $v$ tels que $au+nv=1$ (avec l’algorithme d’Euclide étendu par exemple). Les solutions de la congruence sont alors les entiers $x$ vérifiant $x\equiv ub\mathrm{mod}n$.

2. Si $d\mid b$, cela revient à résoudre la congruence $\frac{a}{d}x\equiv \frac{b}{d}\mathrm{mod}\frac{n}{d}$, et on se ramène au cas 1 (avec la nouvelle congruence à résoudre).

Lemme de Gauss

Soient $a$, $b$ et $c$ trois entiers non nuls. Si $c\mid ab$ et $c$ est premier avec $a$, alors $c\mid b$.

Corollaire

Soient $a$, $b$ et $c$ trois entiers non nuls. Si $b\mid a$, $c\mid a$ et que $b$ et $c$ sont premiers entre eux, alors $bc\mid a$.

Définition

Une équation diophantienne linéaire en deux variables $x$ et $y$ est une équation de la forme $(E):ax+by=c$ où les coefficients $a$, $b$ et $c$ sont des entiers relatifs et où les solutions sont également des entiers relatifs.

Solutions de $(E)$

En reprenant les notations précédentes, on pose $d=\mathrm{PGCD}(a;b)$. Alors :

• Si $d\mid c$, on cherche une solution particulière à $(E)$ que l’on note $(x_0;y_0)$. Alors les solutions de $(E)$ sont les couples $(x_k;y_k)$ où $x_k=x_0+k\frac{b}{d}$ et $y_k=y_0-k\frac{a}{d}$.

• Sinon, $(E)$ n’a pas de solution.

Nombre premier

Un nombre entier $p\ge 2$ est dit premier si ses seuls diviseurs positifs sont $1$ et lui-même.

Propriétés

Soit $n\in \mathbb{N}$ supérieur ou égal à 2, alors on a les propriétés suivantes :

• Si $n$ n’admet aucun diviseur premier inférieur ou égal à $\sqrt{n}$, alors $n$ est premier.

• Si $n$ n’est pas premier alors $n$ admet au moins un diviseur premier inférieur ou égal à $\sqrt{n}$.

• Si $n$ est premier et $n$ ne divise pas un entier $m$, alors $n$ et $m$ sont premiers entre eux.

Lemme d’Euclide

Soit $p$ un nombre premier et $a$ et $b$ deux entiers. Si $p\mid ab$ alors $p\mid a$ ou $p\mid b$.

Infinité de nombres premiers

Il existe une infinité de nombres premiers.

Petit théorème de Fermat

Soit $p$ un nombre premier et $a$ un entier non divisible par $p$. Alors $a^{p-1}\equiv 1\mathrm{mod}p$.

Théorème fondamental de l’arithmétique

Soit $n\in \mathbb{N}$ supérieur ou égal à 2, alors $n$ peut s’écrire de la façon suivante : $$n=p_1^{{\alpha }_1}\times p_2^{{\alpha }_2}\times \cdots \times p_n^{{\alpha }_n}$$ où $p_1$, $p_2$, ... , $p_n$ des nombres premiers tels que $p_1<p_2<\cdots <p_n$ et ${\alpha }_1$, ${\alpha }_2$, ... , ${\alpha }_n$ des entiers naturels non nuls.