Divisibilité et division euclidienne

Plan du chapitre "Arithmétique dans ℤ"

Divisibilité dans {\mathbb{Z}}, diviseurs, multiples

Définition
Soient {a} et {b} deux entiers relatifs. On dit que {b} divise {a}, ou encore {b} est un diviseur de {a}, ou encore {a} est divisible par {b}, ou encore {a} est un multiple de {b}, s’il existe {q} dans {\mathbb{Z}} tel que {a=qb}. On note alors {b\mid a}.
Définition
Pour tout {n} de {\mathbb{Z}}, on note {n\mathbb{Z}=\{qn,\,q\in\mathbb{Z}\}} l’ensemble des multiples de {n}.
On note {\mathcal{D}(n)} l’ensemble des diviseurs de {n} dans {\mathbb{Z}}.
L’ensemble {\mathcal{D}(n)\cap \mathbb{N}} est donc l’ensemble des diviseurs positifs ou nuls de {n}.
Pour tous {a,b} dans {\mathbb{Z}}, on a les équivalences : {\;b\mid a\Leftrightarrow a\in b\mathbb{Z}\Leftrightarrow b\in\mathcal{D}(a)}.

Remarques sur la relation de divisibilité

En écrivant {a\mid b}, on définit une relation binaire sur l’ensemble {\mathbb{Z}}.
Cette relation est réflexive (on a toujours {a\mid a}) et transitive (si {a\mid b} et {b\mid c}, alors {a\mid c}).
Mais ce n’est pas une relation d’ordre car elle n’est pas antisymétrique.
Plus précisément, on a l’équivalence : {(a\mid b \;\text{et}\; b\mid a)\Leftrightarrow a=\pm\, b}.

En revanche, la restriction de la relation de divisibilité à {\mathbb{N}} est une relation d’ordre (partiel).

On dit de deux entiers relatifs qui se divisent mutuellement (c’est-à-dire : qui sont égaux ou opposés, ou encore : qui ont la même valeur absolue) qu’ils sont associés.
On retiendra que deux entiers associés ont exactement les mêmes propriétés par rapport à la relation de divisibilité (et c’est la raison pour laquelle on choisira souvent celui des deux qui est positif).

Quelques cas particuliers

  • La notation {2\mathbb{Z}} désigne l’ensemble des entiers pairs, et on a {\mathcal{D}(2)=\{-2,-1,1,2\}}.

    De même {\begin{cases}12\mathbb{Z}=\{12\,k,\;k\in\mathbb{Z}\}=\{\cdots,-36,-24,-12,0,12,24,36,\cdots\}\\\mathcal{D}(12)=\{-12,-6,-4,-3,-2,-1,1,2,3,4,6,12\}\end{cases}}

    Ou encore {\begin{cases}13\mathbb{Z}=\{13\,k,\;k\in\mathbb{Z}\}=\{\cdots,-39,-26,-13,0,13,26,39,\cdots\}\\\mathcal{D}(13)=\{-13,-1,1,13\}\end{cases}}

  • L’entier {0} est multiple de tout entier {b} (car {0=0b}), ou encore : tout entier {b} divise {0}.

    En revanche, {0} ne divise que lui-même car {a=q0\Rightarrow a=0} (ou encore : le seul multiple de {0} est {0}).
    On peut donc écrire : {\mathcal{D}(0)=\mathbb{Z}}, et {0\mathbb{Z}=\{0\}}.

  • Les entiers {1} et {-1} divisent tout entier {a} (considérer {a=a1=(-a)(-1)}).
    Ainsi tout entier est multiple de {1} et {-1}. On peut donc écrire : {1\mathbb{Z}=(-1)\mathbb{Z}=\mathbb{Z}}.

    En revanche les seuls diviseurs de {-1} et {1} sont {-1} et {1} eux-mêmes.
    Ainsi {\mathcal{D}(1)=\mathcal{D}(-1)=\{-1,1\}}.

Propriétés diverses sur les ensembles {\mathcal{D}(n)} et {n\mathbb{Z}}.

  • Il nous arrivera souvent de considérer {\mathcal{D}(n)\cap\mathbb{N}}, ensemble des diviseurs positifs ou nuls de {n}.
  • Les ensembles {\mathcal{D}(n)} et {n\mathbb{Z}} ne sont jamais vides, car ils contiennent {n}.
    Les ensembles {\mathcal{D}(n)} et {n\mathbb{Z}} sont tous deux symétriques par rapport à l’origine.
    Si {n\ne0} : l’ensemble {\mathcal{D}(n)} est inclus dans {[[-n,n]]} donc est fini; en revanche {n\mathbb{Z}} est infini.

  • Pour tous entiers relatifs {a,b}, on a : {\;a\mathbb{Z}\subset b\mathbb{Z}\Leftrightarrow b\mid a\Leftrightarrow\mathcal{D}(b)\subset\mathcal{D}(a)}.
    On en déduit : {\;a\mathbb{Z}=b\mathbb{Z}\Leftrightarrow|\,a\,|=|\,b\,|\Leftrightarrow\mathcal{D}(a)=\mathcal{D}(b)}.
    Les égalités {(-n)\mathbb{Z}=n\mathbb{Z}} et {\mathcal{D}(-n)=\mathcal{D}(n)} font qu’on se limite souvent à {n\ge0}.

  • Si {a,b} sont dans {n\mathbb{Z}}, et si {u,v} sont dans {\mathbb{Z}}, alors {au+bv} est dans {n\mathbb{Z}}.
    C’est faux pour {\mathcal{D}(n)} : par exemple {3} et {5} sont dans {\mathcal{D}(15)} mais pas {3+5}.

Comparaisons dans {\mathbb{N}} entre ordre naturel et ordre pour la divisibilité.

  • On sait que {\mathbb{N}} est muni de sa relation d’ordre naturelle, notée {\le}.
    C’est un ordre total pour lequel {\min(\mathbb{N})=0}, mais {\max(\mathbb{N})} n’existe pas.
    On sait que toute partie non vide de {\mathbb{N}} possède un plus petit élément.
    On sait également que tout partie finie non vide de {\mathbb{N}} possède un plus grand élément.
  • Passons maintenant à la relation de divisibilité sur {\mathbb{N}}.
    C’est une relation d’ordre partiel (il y a des entiers non comparables, par exemple {2} et {3}).

    Pour la relation de divisibilité, le minimum de {\mathbb{N}} est {1} (car {1} divise tous les éléments de {\mathbb{N}}), et le maximum de {\mathbb{N}} est {0} (car {0} est un multiple de tout {n} de {\mathbb{N}}).

    Une partie non vide de {\mathbb{N}} peut ne pas avoir de plus petit élément au sens de la division.
    Par exemple (et on parle bien de la relation « divisibilité » !) :

    • Si {A=\{6,9,12,15,18\}}, il n’y a ni minimum ni maximum.
    • Si {A=\{3,6,9,12,15,18\}},{3} est minimum mais il n’y a pas de maximum.
    • Si {A=\{6,9,12,15,18,180\}}, il n’y a pas de minimum, et {180} est maximum.
    • Si {A=\{3,6,9,12,15,18,180\}}, {3} est minimum, et {180} est maximum.
    • Si {A=\{0,1,3,6,9,12,15,18,180\}}, {1} est minimum, et {0} est maximum!
  • On n’est donc pas à l’abri d’une ambiguïté quand on parle de divisibilité dans {\mathbb{N}} et qu’on utilise les expressions “plus petit que”, “plus grand que”, “maximum”, “minimum”.
    Remarquons tout de même que, pour {(a,b)} dans {\mathbb{N}^{*}\times\mathbb{N}^{*}}, on a : {a\mid b\Rightarrow a\le b}.
    Mais dans {\mathbb{N}^{2}}, l’implication {a\mid b\Rightarrow a\le b} est fausse à cause du cas {a\ge 1} et {b=0}.

Théorème de la division euclidienne

Définition (division euclidienne dans ℤ)
Soit {(a,b)} dans {\mathbb{Z}\times\mathbb{N}^*}.
Il existe un unique couple {(q,r)} de {\mathbb{Z}\times\mathbb{N}} tel que {a=qb+r} et {0\le r\le b-1}.
Le passage du couple {(a,b)} au couple {(q,r)} s’appelle division euclidienne de {a} par {b}.
Dans cette division, {a} est le dividende, {b} le diviseur, {q}
le quotient, et {r} le reste.

Rapport entre divisibilité et division euclidienne

Attention à ne pas confondre la relation de divisibilité avec la divisition euclidienne.
On rappelle que {a\mid b} est une expression booléenne (vraie ou fausse) quels que soient {a} et {b} dans {\mathbb{Z}}.

En revanche, effectuer la division euclidienne de {a} par {b} suppose que {b} est strictement positif.

Plus précisément, soient {a} et {b} deux entiers, avec {b>0} : dire que {b} divise {a}, c’est dire que le reste dans la division de {a} par {b} est nul.

Division euclidienne de {a} ou de {-a} par {b}

Soit {a=qb+r} la division euclidienne de {a} par {b}.

Si {a} est multiple de {b} (c’est-à-dire {r=0}), la division de {-a} par {b} s’écrit : {-a=(-q)b}.

Sinon (si {1\le r\le b-1}), elle s’écrit : {-a=q'b+r'}, avec {q'=-q-1} et {r'=b-r}.

Par exemple, avec {a=2014} et {b=27}, on a : {\begin{cases}2014=74\cdot27+16\\-2014=-74\cdot27-16=(-75)\cdot27+11\end{cases}}

On vérifie tous ces résultats avec la fonction \texttt{divmod} du langage Python :

>>> [divmod(2014,27), divmod(-2014,27)]
[(74, 16), (-75, 11)]

Le quotient entier est la partie entière du quotient

Soit {q} le quotient dans la division euclidienne de {a} par {b} (souvent appelé quotient entier de {a} par {b}).

Alors {q} est la partie entière du rationnel {x=\dfrac ab}.

En effet {a=bq+r} équivaut à {x=q+\dfrac{r}{b}} et on a {0\le \dfrac{r}{b}\lt 1}, donc {q=\Bigl\lfloor\dfrac{a}{b}\Big\rfloor}.

Rappel : l’opérateur « // » de Python fournit ce quotient entier, mais « / » renvoie un flottant.

>>> [2014//27, -2014//27, 2014/27]
[74, -75, 74.5925925925926]

Page suivante : pgcd et algorithme d’Euclide