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.