Divisibilité

Divisibilité dans $\mathbb{Z}$

On rappelle que l’ensemble des entiers naturels — c’est-à-dire, des entiers positifs — est noté $\mathbb{N}$ et que l’ensemble des entiers relatifs est noté $\mathbb{Z}$.

Soit $a$ et $b$ deux entiers relatifs avec $b\neq 0$.

On dit que $a$ divise $b$ s’il existe un entier relatif $k$ tel que $b = ka$. On note ceci $a \mid b$.
On dit également que $a$ est un diviseur de $b$ ou que $b$ est un multiple de $a$.

Exemple : $4\mid 24$. En effet, $24 = 6 \times 4$. On a bien l’existence d’un entier relatif (ici, 6), tel que $24 = k \times 4$.

Exemple : L’ensemble des diviseurs de 8 est $\{-8 ; -4; -2; -1; 1; 2; 4; 8\}$.

Exemple : Pour tout entier relatif $p$, on a $p\mid p$, $-p \mid p$, $1\mid p$ et $-1\mid p$.

Exemple : Montrons que pour tout entier naturel $n$, $12n + 7$ n’est pas un multiple de 4.

Nous raisonnerons par l’absurde : nous supposerons que le contraire de cette affirmation est vraie et aboutirons à une absurdité. Cela nous permettra de conclure que l’hypothèse de départ n’était pas raisonnable.

Supposons qu’il existe un entier $n$ pour lequel $12n+7$ est un multiple de 4. Cela signifie qu’il existe un entier $k$ tel que $12n+7=4k$. Mais alors, $7=4k-12=4(k-3)$. On a écrit 7 comme le produit de 4 et d’un entier : 7 serait donc un multiple de 4. C’est absurde ! Notre hypothèse de départ était donc fausse.

Ainsi, pour tout entier naturel $n$, $12n+7$ n’est pas un multiple de 4.

Soit $a$, $b$ et $c$ trois entiers relatifs, avec $a$ et $b$ non nuls.
Si $a\mid b$ et $b\mid c$, alors $a\mid c$. On dit que la relation de divisibilité est transitive.

Traduisons les hypothèses de l’énoncé

$a\mid b$ : il existe un entier relatif $k$ tel que $b = ka$
$b\mid c$ : il existe un entier relatif $k’$ tel que $c = k’b$

Ainsi, $c = k’b=k’ \times ka = (k’k) \times a$. On a écrit $c$ sous la forme d’un entier multiplié par $a$. $c$ est donc un multiple de $a$ et donc $a\mid c$.

Soit $a$ et $b$ deux entiers relatifs tels que $a\mid b$. Alors tout diviseur de $a$ est un diviseur de $b$.

Il s’agit de la contraposée de la précédente proposition.

Exemple : On souhaite déterminer si 246 est un diviseur de 7416487.

D’une part, 246 est pair : on a $2\mid 246$
Si $246\mid 7416487$, alors, d’après la propriété précédente, on aurait également que $2\mid 7416487$. Ce qui n’est pas le cas.

Ainsi, 246 n’est pas un diviseur de 7416487.

Soit $a$, $b$ et $c$ trois entiers relatifs. On suppose que $a$ et $b$ sont des multiples de $c$.

Alors, pour tous entiers relatifs $u$ et $v$, $ua+vb$ est un multiple de $c$.

Exemple : On sait que 21 et 36 sont des multiples de 3. Alors, $17 \times 21 + 147 \times 36$ est aussi un multiple de 3.

Traduisons le fait que $a$ et $b$ sont des multiples de $c$.

Il existe un entier relatif $k$ tel que $a=kc$.
Il existe un entier relatif $k’$ tel que $b=k’c$.

Ainsi, \[ua+vb = ukc+vk’c = (uk+vk’)c\]
On a écrit $ua+vb$ sous la forme d’un entier relatif multiplié par $c$ : $ua+vb$ est donc un multiple de $c$.

Exemple : Déterminons les entiers relatifs $n$ pour lesquels $n+4$ divise $3n+17$.

Nous procéderons par analyse-synthèse : nous allons d’abord établir une liste de candidats puis nous vérifierons pour chacun de ces candidats s’il convient.

Analyse : Soit $n$ un entier naturel tel que $n+4 \mid 3n+17$. On sait par ailleurs que $n+4 \mid n+4$. Ainsi, $n+4$ divise également $3n+17 -3(n+4)$. Or, $3n+17-3(n+4)=3n+17-3n-12=5$. Ainsi, $n+4$ divise 5. Or, les diviseurs de 5 sont $-5$, $-1$, $1$ et $5$. Cela nous laisse 4 possibilités.

$n+4 = -5$ et donc $n=-9$
$n+4=-1$ et donc $n=-5$
$n+4 = 1$ et donc $n=-3$
$n+4=5$ et donc $n=1$

Synthèse : Il reste à vérifier, parmi les valeurs trouvées, celles qui fonctionnent.

Si $n=-9$, alors $n+4=-5$ et $3n+17 = -10$. On a bien $-5 \mid -10$.
Si $n=-5$, alors $n+4=-1$ et $3n+17 = 2$. On a bien $-1 \mid 2$.
Si $n=-3$, alors $n+4=1$ et $3n+17 = 8$. On a bien $1 \mid 8$.
Si $n=1$, alors $n+4=5$ et $3n+17 = 20$. On a bien $5 \mid 20$.

Les solutions de ce problème sont donc $-9$, $-5$, $-3$ et $1$.

Division euclidienne

Division euclidienne

Soit $a \in \mathbb{Z}$ et $b \in \mathbb{N}$, avec $b \neq 0$.

Il existe un unique couple d’entiers relatifs $(q;r)$ tel que $a=bq+r$ et $0 \leqslant r < b$.

Cette relation s’appelle la division euclidienne de $a$ par $b$.

$a$ est le dividende et $b$ le diviseur.
$q$ est le quotient de la division euclidienne de $a$ par $b$
$r$ est le reste de la division euclidienne de $a$ par $b$

Unicité : Supposons qu’il existe deux couples d’entiers relatifs $(q;r)$ et $(q’;r’)$ tels que $a=bq+r=bq’+r’$, avec $0 \leqslant r < b$ et $0 \leqslant r’ < b$

Alors, $bq-bq’=r’-r$ ce qui entraîne que $b(q-q’)=r’-r$. Ainsi, $b$ est un diviseur de $r-r’$. Or, $r’-r$ est strictement compris entre $-b$ et $b$. On a donc $r-r’=0$ et donc $r’=r$.

Ainsi, $b(q-q’)=0$, mais puisque $b$ est différent de 0, il en vient que $q-q’=0$ et donc que $q=q’$.

Exemple : Prenons $a=2122$ et $b=7$. On a alors $2122 = 7 \times 303 + 1$.

Le quotient de la division euclidienne de 2122 par 7 est 303
Le reste de cette division euclidienne est 1

Exemple : Prenons $a=247$ et $b=6$. On a bien $247 = 6 \times 40 + 7$. Pour autant, il ne s’agit pas de la division euclidienne de $247$ par $6$ : le reste doit être impérativement inférieur à 6.

Exemple : Soit $n$ un entier naturel. Déterminons le reste de la division euclidienne de $7n+13$ par $3n+2$.

D’une part, $7n+13 = 2 \times (3n+2) + n +9$

Il s’agit de la division euclidienne de $7n+13$ par $3n+2$ à condition que le reste soit positif et strictement inférieur au diviseur !

Puisque pour tout entier naturel $n$, $n+9 > 0$, il faut donc que $n+9 < 3n+2$, c’est-à-dire $-2n < -7$ et donc $n > \dfrac{7}{2}$. $n$ étant entier, on a donc $n+9 < 3n+2$ à partir de $n=4$.

Ainsi, si $n \geqslant 4$, le reste de la division euclidienne de $7n+13$ par $3n+2$ est $n+9$. Il faut alors traiter les autres valeurs de $n$ au cas par cas…

$\begin{tabular}{|c|c|c|c|c|} \hline $n$ & $7n+13$ & $3n+2$ & Div. Euc. & Reste \\ \hline 0 & 13 & 2 & 13 = $2 \times 6 + 1$ & 1 \\1 & 20 & 5 & 20 = $5 \times 4 + 0$ & 0 \\ 2 & 27 & 8 & 27 = $8 \times 3 + 3$ & 3 \\ 3 & 34 & 11 & 20 = $11 \times 3 + 1$ & 1 \\ \hline \end{tabular}$

Soit $a$ un entier relatif et $b$ un entier naturel non nul.

$b$ divise $a$ si et seulement si le reste de la division euclidienne de $a$ par $b$ est nul.

Si le reste de la division euclidienne de $a$ par $b$ est nul, alors il existe un entier relatif $q$ tel que $a=bq$. $b$ divise donc $a$.

Si $b$ divise $a$, alors il existe un entier relatif $q$ tel que $a=bq=bq+0$. Par unicité de la division euclidienne, le reste de la division de $a$ par $b$ vaut 0.

Soit $b$ un entier naturel supérieur ou égal à 2.

Pour tout entier relatif $a$, il existe un entier relatif $q$ tel que $a$ s’écrit sous l’une des formes suivantes : $bq$, $bq+1$, $bq+2$, … , $bq + (b-1)$

Exemple : Prenons $b=2$. Tout entier relatif s’écrit sous la forme $2k$ ou $2k+1$. Les premiers sont les nombres pairs et les seconds sont les nombres impairs.

Exemple : Soit $n$ un entier naturel. Montrons que $n^2+1$ n’est jamais divisible par 3.

Nous allons faire une disjonction de cas : d’après la propriété précédente, $n$ peut s’écrire sous la forme $3k$, $3k+1$ ou $3k+2$. Soit $k$ un entier relatif

$(3k)^2+1=9k^2+1$. Or, $3\mid 9$ donc $3 \mid 9k^2$. Si $9k^2+1$ était divisible par 3, alors $9k^2+1-9k^2$ le serait aussi… Mais cette quantité vaut 1, qui n’est pas divisible par 3. Ainsi, $9k^2+1$ n’est pas un multiple de 3.
$(3k+1)^2+1=9k^2+6q+2=3(3k^2+2k)$. De la même manière que pour le point précédent, puisque 2 n’est pas divisible par 3, $(3k+1)^2+1$ ne l’est pas non plus.
$(3k+2)^2+1=9k^2+12k+5=3(3k^2+4k)+5$, qui n’est pas un multiple de 3.

Dans tous les cas, $n^2+1$ n’est pas un multiple de 3.