DIVISIBILITÉ, DIVISION EUCLIDIENNE

Ensembles

L'ensemble \(\left\{0;1;2;3;...\right\}\) est appelé ensemble des entiers naturels. On le note \(\mathbb{N}\).

L'ensemble \(\left\{... ; -3 ; -2 ; -1 ; 0 ; 1 ; 2 ; 3 ; ...\right\}\) est appelé ensemble des entiers relatifs noté \(\mathbb{Z}\).

Remarques

l'ensemble des entiers naturels est inclus dans celui des entiers relatifs. On note \(\mathbb{N} \subset \mathbb{Z}\).
La somme et le produit de deux entiers naturels sont des entiers naturels.
La somme et le produit de deux entiers relatifs sont des entiers relatifs.

Propriété

Toute partie non vide de \(\mathbb{N}\) admet un plus petit élément.

Exemple : \(A = \left\{12 ; 14 ; 16 ; 18 \right\}\) est une partie de \(\mathbb{N}\); son plus petit élément est \(12\).

Soit \(B\) l'ensemble des entiers naturels impairs. \(B\) est une partie de \(\mathbb{N}\); son plus petit élément est \(1\).

Remarques

ceci n'est plus vrai pour les parties de \(\mathbb{Z}\).

Cette propriété nous servira pour démontrer l'existence d'objets mathématiques.

Divisibilité

On se place ici dans l'ensemble \(\mathbb{Z}\)

Définition

Soient \(a\) et \(b\) deux entiers relatifs.

On dit que \(a\) divise \(b\) ou que \(b\) est un multiple de \(a\) s'il existe un entier relatif \(q\) tel que \(b=a\times q\).

Remarques

On peut aussi dire que \(b\) est divisible par \(a\), ou que \(a\) est un diviseur de \(b\).

Il est important de traduire ce critère de divisibilité par une égalité car cela permet de faire ... des calculs.

Exemple : \(54=6\times 9\) donc on peut dire que \(6\) et \(9\) sont des diviseurs de \(54\) ou que \(54\) est un multiple de \(6\) ou de \(9\).

L'ensemble des multiples de \(5\) est l'ensemble de tous les entiers relatifs qui s'écrivent \(5k\) avec \(k{\in}\mathbb{Z}\).

Propriété

Soient \(a\) et \(b\) deux entiers relatifs. Si \(a\) divise \(b\) alors \(\left|a\right|\leqslant \left|b\right|\).

En conséquence tout entier relatif admet un nombre fini de diviseurs.

Preuve

Soient \(a\) et \(b\) deux entiers relatifs tels que \(a\) divise \(b\) et \(b\neq 0\).

Puisque \(a\) divise \(b\), on peut écrire \(b={ak}\) avec \(k{\in}\mathbb{Z}\), donc \(\left|b\right|=\left|{ak}\right|=\left|a\right|\times \left|k\right|\).

Soit \(b\) un entier relatif non nul.

Donc \(a\) peut prendre au maximum \(2\times \left|b\right|+1\) valeurs.

Le nombre de diviseurs de \(b\) est donc fini (et inférieur à \(2\times \left|b\right|+1\))

Propriété

Soient \(a\), \(b\) et \(c\) des entiers relatifs.

Si \(a\) divise \(b\) et \(b\) divise \(c\), alors \(a\) divise \(c\).
Si \(a\) divise \(b\), alors pour tout entier relatif \(k\), \(ka\) divise \(kb\).
Si \(a\) divise \(b\) et \(c\) alors pour tous entiers relatifs \(u\) et \(v\), \(a\) divise \(bu+cv\).

Remarques

Pour la troisième assertion, en particulier \(a\) divise \(b+c\) et \(b-c\).

Ce sont ces propriétés qui permettent de résoudre la majorité des exercices.

\(au+bv\) s'appelle une combinaison linéaire de \(a\) et \(b\).

Division Euclidienne.

Propriété

Soit \(b\) un entier naturel non nul. Pour tout entier naturel \(a\), il existe un entier naturel \(n\) tel que \({nb}>a\).

Remarques

en d'autres termes si l'on choisit deux entiers \(a\) et \(b\) non nuls, il existera toujours un multiple de \(b\) qui soit plus grand que \(a\). Cela revient à dire que l'ensemble des multiples de \(b\) n'est pas majoré.

Preuve

\(b\) est un entier naturel non nul donc \(b{\geq}1\).

En multipliant chaque membre de l'inégalité par \(a+1\) on obtient \((a+1)b{\geq}a+1>a\).

Il suffit de prendre \(n=a+1\) on a alors \({nb}>a\). D'où l'existence d'un entier n qui convient.

Rappel : technique de la division des entiers naturels.

Pour effectuer la division de \(26\) par \(3\) on cherche le plus grand multiple de \(3\) qui soit inférieur à \(26\). On remarque que \(3\times 8\leqslant 26<3\times 9\). On peut alors affirmer que \(26=3\times8+2\).

On appelle \(26\) le dividende, \(3\) le diviseur, \(8\) le quotient et \(2\) le reste.

Dans la division euclidienne le reste est toujours strictement inférieur au diviseur.

Propriété

Division euclidienne dans \(\mathbb{N}\).

Soient \(a\) un entier naturel et \(b\) un entier naturel non nul.

Il existe un unique couple d'entiers naturels \((q\mathrm ;r)\) tel que \(a={bq}+r\) et \(r<b\).

\(q\) est appelé le quotient de \(a\) par \(b\) et \(r\) le reste de la division euclidienne de \(a\) par \(b\).

Remarques

si \(r = 0\), \(a\) est divisible par \(b\).

Preuve

Soit \(a\) un entier naturel et \(b\) un entier naturel non nul.

Existence du couple \((q ; r)\)

Considérons l'ensemble \(E\) des entiers naturels \(n\) tels que \(a<{bn}\). \(E = \left\{n \in \mathbb{N} | a < bn\right\}\).

Puisque \(b\) est non nul, on sait d'après la propriété d'Archimède que l'ensemble \(E\) est non vide.

\(E\) est donc une partie non vide de \(\mathbb{N}\), \(E\) a donc un plus petit élément.

Ce plus petit élément \(p\) n'est pas nul, car \(0\) n'appartient pas à E.

On a donc \(p \geq 1\). Posons \(q=p-1\). Alors \(q{\in}\mathbb{N}\).

D'autre part \(q\notin E\) . (le plus petit élément de E est \(p\) et \(q<p\))

Puisque \(q\notin E\), on a \({bq}{\leq}a\) et comme \(p{\in}E\), on a aussi \(a<{bp}\) c'est-à-dire \(a<b(q+1)\).

On a donc trouvé un entier naturel \(q\) tel que \({bq}{\leq}a<b(q+1)\).

Posons \(r=a-{bq}\), on a \(r \in \mathbb{N}\) et \(a={bq}+r\).

D'autre part \({bq}{\leq}a<b(q+1) \Leftrightarrow {bq}{\leq}a<{bq}+b \Leftrightarrow 0{\leq}a-{bq}<b \Leftrightarrow 0{\leq}r<b\).

Il existe donc un couple \((q\mathrm ;r)\) d'entiers naturels tel que \(a={bq}+r\) et \(r<b\).

Unicité du couple \((q ; r)\)

Pour démontrer que ce couple est unique, supposons qu'il existe un deuxième couple \((q' ; r')\) vérifiant les mêmes conditions.

on a \({bq}+r={bq}'+r' \Leftrightarrow b(q-q')=r'-r\).

Alors \(0{\leq}r<b\) donc \(-b<-r{\leq}0\) et \(0{\leq}r'<b\)

On en déduit alors que \(-b<r'-r<b\) c'est-à-dire \(\left|r'-r\right|<b\).

D'autre part \(r'-r=b(q-q')\), donc \(r'-r\) est un multiple de \(b\).]

Si \(r'-r\) était non nul, alors on aurait \(\left|r'-r\right|{\geq}\left|b\right|\) c'est-à-dire \(\left|r'-r\right|{\geq}b\) ce qui est en contradiction avec l'inégalité démontrée précédemment.

On a donc nécessairement \(r'-r=0\) et ,par conséquent, \(b(q'-q)=0\), donc \(q'-q=0\)

On obtient alors \(r'=r\) et \(q'=q\).

Le couple \((q;r)\) est donc unique.

Remarques

Les restes possibles pour une division euclidienne par \(2\) sont donc \(0\) et \(1\). Tout entier naturel pair s'écrit donc \(2k\) avec \(k{\in}\mathbb{Z}\) et tout entier naturel impair s'écrit \(2k + 1\) avec \(k{\in}\mathbb{Z}\) .

On va pouvoir étendre cette division euclidienne aux nombres entiers relatifs.

Propriété

Soit \(a\) un entier relatif et \(b\) un entier naturel non nul.

Il existe un unique couple \((q\mathrm ;r)\), \(q{\in}\mathbb{Z}\) et \(r{\in}\mathbb{N}\) tel que \(a=bq+r\) et \(r<b\)

\(a\) est le dividende, \(b\) le diviseur, \(q\) le quotient et \(r\) le reste.

On dit que le couple unique \((q\mathrm ;r)\) est le résultat de la division euclidienne de \(a\) par \(b\).

Remarques

Le quotient peut ne plus appartenir à \(\mathbb{N}\) mais à \(\mathbb{Z}\). Le reste, lui, doit toujours appartenir à \(\mathbb{N}\).

Preuve

Soit \(a\) un entier relatif et \(b\) un entier naturel non nul.

Si \(a\) est un entier positif ou nul, la propriété a déjà été justifiée.

Considérons un entier \(a\) négatif.

Existence

\(a\) étant négatif, on considère son opposé \(-a\) qui est un entier naturel.

D'après le résultat démontré sur les entiers naturels, il existe un unique couple \((q\mathrm ;r)\) , \(q{\in}\mathbb{N}\) et \(r{\in}\mathbb{N}\) tel que : \(-a={bq}+r\) et \(r<b\).

Donc \(a=-{bq}-r=b(-q)-r\).

Si \(r=0\), alors \(-r=0\) donc \(-r \in \mathbb{N}\), et le couple \((-q\mathrm ;-r)\) répond à la question.

Si \(r\neq 0\), le couple \((-q\mathrm ;-r)\) ne répond pas à la question car \(-r\notin \mathbb{N}\).

On peut alors écrire \(-a=b(-q-1)+b-r\)

On pose \(q'=-q-1\) et \(r'=b-r\).

\(q'{\in}\mathbb{Z}\); vérifions que \(r'{\in}\mathbb{N}\).

\(b\) et \(r\) étant des entiers, \(b-r\) est un entier, donc \(b-r{\in}\mathbb{Z}\).

De plus \(r\neq 0\) et \(0{\leq}r<b\), donc \(0<r<b\) donc \(-b<-r<0\) et \(b-b<b-r<b\) d'où \(0<b-r<b\) donc \(b-r{\in}\mathbb{N}\) et \(b-r<b\).

Le couple \((-q-1;b-r)\) répond donc à la question.

Unicité

L'unicité du couple se démontre exactement de la même façon que pour une division euclidienne dans \(\mathbb{N}\).

Congruences

Définition

Soient \(p\) un entier naturel. Soient \(a\) et \(b\) deux entiers relatifs. On dit que \(a\) est congru à \(b\) modulo \(p\), si \(a\) et \(b\) ont le même reste dans la division euclidienne par \(p\).

On notera \(a \equiv b \pmod p\) ou \(a \equiv b \pod{p}\)

Remarques

\(a \equiv b \pod{p} \Leftrightarrow b \equiv a \pod{p}\)
\(a \equiv 0 \pod{p} \Leftrightarrow a\) est divisible par \(p\).
Si \(a \equiv r \pod{b}\) et si \(0 \leq r < b\), alors \(r\) est le reste de la division euclidienne de \(a\) par \(b\).

Propriété

\(a\), \(b\), \(a'\) et \(b'\) sont quatres entiers relatifs, \(p\) est un entier naturel.

\(a \equiv b \pod{p} \Leftrightarrow b-a\) est un multiple de \(p\).
Si \(a \equiv b \pod{p}\) et si \(b \equiv c \pod{p}\) alors \(a \equiv c \pod{p}\)
Si \(a \equiv b \pod{p}\) et si \(a' \equiv b' \pod{p}\) alors \(a+a' \equiv b+b' \pod{p}\) ; \(a-a' \equiv b-b' \pod{p}\) ; \(aa' \equiv bb' \pod{p}\) ; \(a^n \equiv b^n \pod{p}\) avec \(n \in \mathbb{N}^*\)
Si \(a \equiv b \pod{p}\) alors, pour tout \(c \in \mathbb{Z}\) , \(a+c \equiv b+c \pod{p}\) ; \(a-c \equiv b-c \pod{p}\) ; \(ac \equiv bc \pod{p}\)

Remarques

La relation de congruence est compatible avec l'addition, la soustraction et la multiplication.

Attention, la relation de congruence n'est pas compatible avec la division ni avec la racine carrée.

On ne pourra en aucun cas simplifier dans une congruence comme on simplifie dans une égalité: Une congruence du type \(2x \equiv 2y \pod{p}\) ne pourra pas être simplifiée par \(2\)

Cependant les propriétés des congruences vont nous faciliter beaucoup de démonstrations.