Divisibilité, division euclidienne, congruences

On suppose 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. On considère 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\).

Cette preuve modélise le partage par soustractions successives.
On considère 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}\).
Dividende négatif : Si \(\textcolor{olive}{a}<0\), on applique ce qui précède à \(-\textcolor{olive}{a}\in\mathbb{N}\) : \(-\textcolor{olive}{a}=\textcolor{colordef}{b}q_0+r_0\) avec \(0\le r_0<\textcolor{colordef}{b}\). Si \(r_0=0\), alors \(\textcolor{olive}{a}=\textcolor{colordef}{b}(-q_0)+0\) ; sinon \(\textcolor{olive}{a}=\textcolor{colordef}{b}(-q_0-1)+(\textcolor{colordef}{b}-r_0)\) avec \(0<\textcolor{colordef}{b}-r_0<\textcolor{colordef}{b}\). Dans les deux cas, l'existence s'étend à tout \(\mathbb{Z}\).
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'\).

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\).

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}\).

1. \(a-a=0\), et \(0\) est divisible par tout \(n\ge 2\). Donc \(a \equiv a \pmod{n}\).
2. 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}\).
3. 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}\).

Puisque \(a \equiv b \pmod{n}\) et \(c \equiv d \pmod{n}\), il existe des entiers relatifs \(u\) et \(v\) tels que \(a - b = un\) et \(c - d = vn\).

1. \((a+c)-(b+d) = (a-b)+(c-d) = un + vn = (u+v)n\), donc \(n \mid \bigl((a+c)-(b+d)\bigr)\), d'où \(a+c \equiv b+d \pmod{n}\).
2. \((a-c)-(b-d) = (a-b)-(c-d) = un - vn = (u-v)n\), d'où \(a-c \equiv b-d \pmod{n}\).
3. En écrivant \(ac - bd = ac - bc + bc - bd\) : $$ ac - bd = c(a-b) + b(c-d) = cun + bvn = (cu+bv)n, $$ donc \(n \mid (ac-bd)\), d'où \(ac \equiv bd \pmod{n}\).
4. Par récurrence sur \(k\). Pour \(k=0\), \(a^0 = b^0 = 1\) (avec la convention \(0^0 = 1\)). Si \(a^k \equiv b^k \pmod{n}\) pour un entier naturel \(k\), alors en appliquant le point 3 aux congruences \(a^k \equiv b^k \pmod{n}\) et \(a \equiv b \pmod{n}\), on obtient \(a^k \cdot a \equiv b^k \cdot b \pmod{n}\), c'est-à-dire \(a^{k+1} \equiv b^{k+1} \pmod{n}\).

On écrit \(N = 10q + a_0\), où l'entier naturel \(q\) est le nombre de dizaines de \(N\), et \(N = 100q' + (10a_1 + a_0)\), où l'entier naturel \(q'\) est le nombre de centaines de \(N\) (avec \(a_1 = 0\) si \(N\) n'a qu'un chiffre).

• Critères par \(2\), \(5\), \(10\). Comme \(10 \equiv 0\) modulo \(2\), modulo \(5\) et modulo \(10\), la compatibilité donne \(N = 10q + a_0 \equiv 0 \times q + a_0 = a_0\) modulo chacun de ces nombres. Ainsi \(N \equiv 0\) si et seulement si \(a_0 \equiv 0\).
• Critères par \(4\), \(25\). Comme \(100 = 4 \times 25\), \(100 \equiv 0\) modulo \(4\) et modulo \(25\), donc \(N = 100q' + (10a_1 + a_0) \equiv 10a_1 + a_0\) modulo chacun de ces nombres.
• Critère par \(9\). Comme \(10 = 9 + 1\), \(10 \equiv 1 \pmod{9}\), et par compatibilité avec les puissances \(10^j \equiv 1^j = 1 \pmod{9}\) pour tout entier naturel \(j\). Alors $$\begin{aligned}[t] N &= a_m \times 10^m + \dots + a_1 \times 10 + a_0\\ &\equiv a_m \times 1 + \dots + a_1 \times 1 + a_0 \pmod{9} && \text{(compatibilité)}\\ &\equiv a_m + \dots + a_1 + a_0 \pmod{9}. \end{aligned}$$ Ainsi \(N\) et la somme de ses chiffres ont le même reste modulo \(9\), et \(N\) est divisible par \(9\) si et seulement si la somme de ses chiffres l'est.

Les critères par \(3\), avec \(10 \equiv 1 \pmod{3}\), et par \(11\), avec \(10 \equiv -1 \pmod{11}\), énoncés dans la proposition, se démontrent de la même façon : ces deux démonstrations sont laissées en exercice.