Divisibilité et arithmétique modulaire

Divisibilité

Définition Relations de divisibilité

On dit qu'un entier relatif $b$ divise un entier relatif $a$ s'il existe un entier relatif $k$ tel que :$$a = kb.$$On note $b\mid a$.
Nous pouvons également utiliser les formulations suivantes :

$b$ est un diviseur de $a$,
$b$ est un facteur de $a$,
$a$ est divisible par $b$,
$a$ est un multiple de $b$.

Exemple

Considérons les nombres $10$ et $5$.
Puisque nous pouvons écrire $\textcolor{olive}{10} = \textcolor{colorprop}{2}\times \textcolor{colordef}{5}$, nous pouvons dire que :

$\textcolor{colordef}{5}$ divise $\textcolor{olive}{10}$,
$\textcolor{colordef}{5}$ est un diviseur (ou facteur) de $\textcolor{olive}{10}$,
$\textcolor{olive}{10}$ est divisible par $\textcolor{colordef}{5}$,
$\textcolor{olive}{10}$ est un multiple de $\textcolor{colordef}{5}$.

Remarques

Soient $a$ et $b$ deux entiers relatifs.

$1$ divise tout entier relatif $a$ car $a=1\times a$ (donc $1\mid a$).
Si $a$ est un multiple de $b$ et si $a\neq 0$, alors $|a|\ge |b|$.
Si $a$ divise $b$ et si $b$ divise $a$, avec $a\neq 0$ et $b\neq 0$, alors $a=b$ ou $a=-b$.

Proposition Combinaisons linéaires

Soient $a,b,c$ trois entiers relatifs.
Si $a\mid b$ et $a\mid c$, alors pour tous entiers relatifs $m$ et $n$,$$a \mid (mb+nc).$$

Preuve

Supposons que $a \mid b$ et $a \mid c$.
Par définition, il existe des entiers relatifs $k$ et $\ell$ tels que$$b = ka \quad \text{et} \quad c = \ell a.$$Soient $m$ et $n$ deux entiers relatifs quelconques. Considérons la combinaison linéaire $mb+nc$ :$$\begin{aligned}mb + nc &= m(ka) + n(\ell a) \\ &= (mk + n\ell)a.\end{aligned}$$Comme $m,k,n,\ell$ sont des entiers, le terme $(mk+n\ell)$ est aussi un entier relatif.
Par conséquent, par définition, $a$ divise $mb+nc$.

Division euclidienne (avec reste)

Theorem Division euclidienne

Soient $\textcolor{olive}{a}$ un entier relatif et $\textcolor{colordef}{b}$ un entier naturel non nul (donc $\textcolor{colordef}{b}>0$).
Il existe un unique couple $(\textcolor{colorprop}{q},\textcolor{orange}{r})$ d'entiers relatifs tel que$$\textcolor{olive}{a}=\textcolor{colordef}{b}\,\textcolor{colorprop}{q}+\textcolor{orange}{r}\quad\text{et}\quad0\le \textcolor{orange}{r}<\textcolor{colordef}{b}.$$

$\textcolor{olive}{a}$ est le $\textcolor{olive}{\text{dividende}}$,
$\textcolor{colordef}{b}$ est le $\textcolor{colordef}{\text{diviseur}}$,
$\textcolor{colorprop}{q}$ est le $\textcolor{colorprop}{\text{quotient}}$,
$\textcolor{orange}{r}$ est le $\textcolor{orange}{\text{reste}}$.

Preuve

Cette preuve modélise le partage par soustractions successives.
Considérons l'algorithme suivant pour $\textcolor{olive}{a}\in\mathbb{N}$ et $\textcolor{colordef}{b}\in\mathbb{N}^*$ :

Initialisation : Poser $\textcolor{orange}{r}=\textcolor{olive}{a}$ et $\textcolor{colorprop}{q}=0$.
Boucle : Tant que $\textcolor{orange}{r}\ge \textcolor{colordef}{b}$ faire : $$ \textcolor{orange}{r}\leftarrow \textcolor{orange}{r}-\textcolor{colordef}{b} \quad\text{et}\quad \textcolor{colorprop}{q}\leftarrow \textcolor{colorprop}{q}+1. $$

Terminaison : Comme $\textcolor{colordef}{b}>0$, la valeur de $\textcolor{orange}{r}$ décroît à chaque étape et reste positive ou nulle. Elle finit donc par satisfaire $\textcolor{orange}{r}<\textcolor{colordef}{b}$ en un temps fini.
Invariant : La relation $\textcolor{olive}{a}=\textcolor{colordef}{b}\textcolor{colorprop}{q}+\textcolor{orange}{r}$ est conservée à chaque itération. À l'arrêt, on a bien $0\le \textcolor{orange}{r}<\textcolor{colordef}{b}$.
Unicité : Si $\textcolor{olive}{a}=\textcolor{colordef}{b}q+r=\textcolor{colordef}{b}q'+r'$ avec $0\le r,r'<\textcolor{colordef}{b}$, alors $\textcolor{colordef}{b}(q-q')=r'-r$. Or $-(\textcolor{colordef}{b}-1)\le r'-r\le \textcolor{colordef}{b}-1$, donc le seul multiple de $\textcolor{colordef}{b}$ dans cet intervalle est $0$. Ainsi $r=r'$ et $q=q'$.

Exemple

$$\begin{array}{ccccccccl} \textcolor{olive}{13} &=& \textcolor{colordef}{3} & \times & \textcolor{colorprop}{4} & + & \textcolor{orange}{1} & \text{avec} & 0 \leq\textcolor{orange}{1} < \textcolor{colordef}{3} \\ \textcolor{olive}{\text{Dividende}} &=& \textcolor{colordef}{\text{Diviseur}} & \times & \textcolor{colorprop}{\text{Quotient}} & + & \textcolor{orange}{\text{Reste}} & \text{avec} & 0 \leq\textcolor{orange}{\text{Reste}} < \textcolor{colordef}{\text{Diviseur}}\end{array}$$

Méthode Vérifier la divisibilité

Pour vérifier si un entier $a$ est divisible par un entier naturel non nul $b$, on effectue la division euclidienne de $a$ par $b$.

Si le reste est nul, alors $a$ est divisible par $b$.
Si le reste n'est pas nul, alors $a$ n'est pas divisible par $b$.

Exemple

$13$ est-il divisible par $5$ ?

Correction

Nous effectuons la division euclidienne de $13$ par $5$ :$$\textcolor{olive}{13}=\textcolor{colordef}{5}\times \textcolor{colorprop}{2}+\textcolor{orange}{3}.$$Le reste est $\textcolor{orange}{3}$ (il n'est pas nul). Par conséquent, $\textcolor{olive}{13}$ n'est pas divisible par $\textcolor{colordef}{5}$.

Congruences

Définition Entiers congrus modulo $n$

Soit $n$ un entier naturel ($n \ge 2$).
Deux entiers relatifs $a$ et $b$ sont dits congrus modulo $n$ si leur différence $a-b$ est divisible par $n$.
On note alors : $a \equiv b \pmod{n}$, ou parfois $a \equiv b \ (n)$, ou $a \equiv b \ [n]$.

Proposition Propriété du même reste

Deux entiers relatifs $a$ et $b$ sont congrus modulo $n$ si et seulement si $a$ et $b$ ont le même reste dans la division euclidienne par $n$.

Preuve

Soient$$a = nq_1 + r_1\quad\text{et}\quad b = nq_2 + r_2$$les divisions euclidiennes de $a$ et $b$ par $n$, avec $0 \le r_1, r_2 < n$.

Si $r_1=r_2$, alors $$ a-b = (nq_1 + r_1) - (nq_2 + r_2)=n(q_1-q_2), $$ donc $n\mid (a-b)$ et ainsi $a \equiv b \pmod{n}$.
Réciproquement, si $a \equiv b \pmod{n}$, alors $n\mid (a-b)$. Or $$ a-b = n(q_1-q_2) + (r_1-r_2), $$ donc $n\mid (r_1-r_2)$. Comme $-n < r_1-r_2 < n$, le seul multiple de $n$ dans cet intervalle est $0$. Ainsi $r_1-r_2=0$, donc $r_1=r_2$.

Exemple

Démontrer que $57 \equiv 15 \pmod{7}$.

Correction

Méthode 1 (Restes) : $57 = 7\times 8 + 1$ (reste $1$) et $15 = 7\times 2 + 1$ (reste $1$). Comme ils ont le même reste, $57 \equiv 15 \pmod{7}$.
Méthode 2 (Différence) : $57-15 = 42 = 7\times 6$. Comme la différence est un multiple de $7$, $57 \equiv 15 \pmod{7}$.

Proposition Congruence au reste

Un entier est congru à son reste dans la division euclidienne par $n$.

Preuve

Soit $a = nq + r$ la division euclidienne de $a$ par $n$.
Alors $a-r = nq$. Comme $nq$ est un multiple de $n$, on a $n\mid (a-r)$, donc $a \equiv r \pmod{n}$.

Exemple

Comme $2019 = 201\times 10 + 9$, on a $2019 \equiv 9 \pmod{10}$.

Proposition Relation d'équivalence

La congruence modulo $n$ est une relation d'équivalence, c'est-à-dire que pour tous entiers relatifs $a, b, c$ :

$a \equiv a \pmod{n}$ (réflexivité),
$a \equiv b \pmod{n} \Rightarrow b \equiv a \pmod{n}$ (symétrie),
$a \equiv b \pmod{n}$ et $b \equiv c \pmod{n} \Rightarrow a \equiv c \pmod{n}$ (transitivité).

Preuve

$a-a=0$, et $0$ est divisible par tout $n\ge 2$. Donc $a \equiv a \pmod{n}$.
Si $a \equiv b \pmod{n}$, alors $a-b=kn$ pour un certain entier relatif $k$. Donc $b-a=(-k)n$, et ainsi $b \equiv a \pmod{n}$.
Si $a \equiv b \pmod{n}$ et $b \equiv c \pmod{n}$, alors $a-b=kn$ et $b-c=mn$ pour certains entiers relatifs $k,m$. En additionnant : $$ (a-b)+(b-c)=kn+mn \implies a-c=(k+m)n, $$ donc $a \equiv c \pmod{n}$.

Exemple

Si $x \equiv y \pmod{5}$ et $y \equiv 12 \pmod{5}$, alors $x \equiv 12 \pmod{5}$. Comme $12 = 5\times 2 + 2$, on peut aussi dire que $x \equiv 2 \pmod{5}$.