1 – Diviseurs et multiples
L'arithmétique étudie les nombres entiers. On travaille dans \(\mathbb{Z} = \{\ldots\ ;\ -2\ ;\ -1\ ;\ 0\ ;\ 1\ ;\ 2\ ;\ \ldots\}\), l'ensemble des entiers relatifs. Elle remonte aux Éléments d'Euclide (IIIe siècle av. J.-C.) et sert aujourd'hui en cryptographie et dans les codes de contrôle.
Définition 1 : Soient \(a\), \(b \in \mathbb{Z}\). On dit que \(a\) divise \(b\) s'il existe un entier relatif \(k\) tel que \(b = ka\). On note \(a \mid b\).
On dit aussi que \(a\) est un diviseur de \(b\), que \(b\) est un multiple de \(a\), ou que \(b\) est divisible par \(a\).
On dit aussi que \(a\) est un diviseur de \(b\), que \(b\) est un multiple de \(a\), ou que \(b\) est divisible par \(a\).
Remarques :
• \(a \mid b\) est une affirmation (vraie ou fausse), et non un nombre : ne pas confondre \(a \mid b\) avec la fraction \(\dfrac{b}{a}\).
Pour \(a \neq 0\) : \(a \mid b \Leftrightarrow \dfrac{b}{a} \in \mathbb{Z}\).
• \(0\) est multiple de tout entier (\(0 = 0 \times a\)), mais \(0\) ne divise que \(0\).
• \(1\) et \(-1\) divisent tout entier ; tout entier \(a\) divise \(a\) et \(-a\).
• \(a \mid b \Leftrightarrow (-a) \mid b \Leftrightarrow a \mid (-b)\) : les diviseurs d'un entier vont par paires opposées. On cherche donc les diviseurs positifs, puis on ajoute leurs opposés.
• \(a \mid b\) est une affirmation (vraie ou fausse), et non un nombre : ne pas confondre \(a \mid b\) avec la fraction \(\dfrac{b}{a}\).
Pour \(a \neq 0\) : \(a \mid b \Leftrightarrow \dfrac{b}{a} \in \mathbb{Z}\).
• \(0\) est multiple de tout entier (\(0 = 0 \times a\)), mais \(0\) ne divise que \(0\).
• \(1\) et \(-1\) divisent tout entier ; tout entier \(a\) divise \(a\) et \(-a\).
• \(a \mid b \Leftrightarrow (-a) \mid b \Leftrightarrow a \mid (-b)\) : les diviseurs d'un entier vont par paires opposées. On cherche donc les diviseurs positifs, puis on ajoute leurs opposés.
Exemple 1 :
a) \(-6\) divise-t-il \(42\) ? \(4\) divise-t-il \(30\) ?
b) Montrer que pour tout \(n \in \mathbb{Z}\), \(3\) divise \(6n + 9\).
a) \(42 = (-7) \times (-6)\) avec \(-7 \in \mathbb{Z}\), donc \(-6 \mid 42\).
En revanche, \(\dfrac{30}{4} = 7{,}5 \notin \mathbb{Z}\), donc \(4\) ne divise pas \(30\) : on note \(4 \nmid 30\).
b) \(6n + 9 = 3(2n + 3)\) et \(2n + 3\) est un entier relatif : donc \(3 \mid 6n + 9\).
Propriété 1 : Soient \(a\) et \(b\) deux entiers avec \(b \neq 0\). Si \(a \mid b\), alors \(|a| \leq |b|\). En particulier, un entier non nul n'a qu'un nombre fini de diviseurs.
Démonstration
Si \(a \mid b\), on a \(b = ka\) avec \(k \in \mathbb{Z}\). Comme \(b \neq 0\), on a \(k \neq 0\), donc \(|k| \geq 1\) et \(|b| = |k| \times |a| \geq |a|\). □
Méthode (lister les diviseurs d'un entier \(n \geq 1\)) : on teste les entiers \(d\) de \(1\) à \(\sqrt{n}\) ; chaque diviseur \(d\) trouvé fournit le couple \(\left( d\ ;\ \dfrac{n}{d} \right)\) car \(n = d \times \dfrac{n}{d}\). On ajoute ensuite les opposés.
Exemple 2 :
Déterminer l'ensemble des diviseurs de \(60\) dans \(\mathbb{Z}\).
• \(\sqrt{60} \approx 7{,}7\) : on teste \(d\) de \(1\) à \(7\). \[\begin{aligned} 60 &= 1 \times 60 = 2 \times 30 = 3 \times 20 \\ &= 4 \times 15 = 5 \times 12 = 6 \times 10 \end{aligned}\] et \(7 \nmid 60\).
• Diviseurs positifs : \(1\ ;\ 2\ ;\ 3\ ;\ 4\ ;\ 5\ ;\ 6\ ;\ 10\ ;\ 12\ ;\ 15\ ;\ 20\ ;\ 30\ ;\ 60\) (12 diviseurs).
• Dans \(\mathbb{Z}\), \(60\) a donc \(24\) diviseurs : ces nombres et leurs opposés.
Exemple 3 :
Déterminer les couples \((x\ ;\ y)\) d'entiers naturels tels que \(x^{2} - y^{2} = 15\).
• \(x^{2} - y^{2} = 15 \Leftrightarrow (x - y)(x + y) = 15\). Comme \(x + y \geq 0\) et que le produit vaut \(15 > 0\), on a \(0 < x - y \leq x + y\).
• Les diviseurs positifs de \(15\) sont \(1\ ;\ 3\ ;\ 5\ ;\ 15\), d'où deux cas : \[\begin{cases} x - y = 1 \\ x + y = 15 \end{cases} \quad \text{ou} \quad \begin{cases} x - y = 3 \\ x + y = 5 \end{cases}\] qui donnent \((x\ ;\ y) = (8\ ;\ 7)\) ou \((x\ ;\ y) = (4\ ;\ 1)\).
• Vérification : \(64 - 49 = 15\) ✓ et \(16 - 1 = 15\) ✓. Conclusion : \(S = \{(8\ ;\ 7)\ ;\ (4\ ;\ 1)\}\).
Remarque : Ce type d'équation dont on cherche les solutions entières est appelé équation diophantienne.
2 – Propriétés de la divisibilité
Propriété 2 : Soient \(a\), \(b\), \(c\) trois entiers relatifs.
• Transitivité : si \(a \mid b\) et \(b \mid c\), alors \(a \mid c\).
• Si \(a \mid b\), alors \(a \mid bc\).
• Si \(a \mid b\) et \(b \mid a\), alors \(a = b\) ou \(a = -b\).
• Transitivité : si \(a \mid b\) et \(b \mid c\), alors \(a \mid c\).
• Si \(a \mid b\), alors \(a \mid bc\).
• Si \(a \mid b\) et \(b \mid a\), alors \(a = b\) ou \(a = -b\).
Démonstration
• Si \(b = ka\) et \(c = k'b\) avec \(k, k' \in \mathbb{Z}\), alors \(c = (k'k)a\) avec \(k'k \in \mathbb{Z}\), donc \(a \mid c\).• De même \(bc = (kc)a\).
• Si \(b = ka\) et \(a = k'b\), alors \(a = k'ka\). Si \(a = 0\), alors \(b = 0 = a\).
Sinon, \(k'k = 1\) avec \(k, k'\) entiers, donc \(k = k' = 1\) ou \(k = k' = -1\) : \(b = a\) ou \(b = -a\). □
Propriété 3 (combinaisons linéaires) : Soient \(a\), \(b\), \(c\) trois entiers relatifs. Si \(a \mid b\) et \(a \mid c\), alors :
• \(a \mid b + c\) et \(a \mid b - c\).
• Plus généralement, pour tous entiers relatifs \(u\) et \(v\) : \(a \mid bu + cv\).
• \(a \mid b + c\) et \(a \mid b - c\).
• Plus généralement, pour tous entiers relatifs \(u\) et \(v\) : \(a \mid bu + cv\).
Remarque : \(bu + cv\) est appelée une combinaison linéaire de \(b\) et \(c\).
Démonstration
Il existe \(k, k' \in \mathbb{Z}\) tels que \(b = ka\) et \(c = k'a\). Alors : \[bu + cv = kau + k'av = (ku + k'v)a\] avec \(ku + k'v \in \mathbb{Z}\), donc \(a \mid bu + cv\). □
Point de vigilance : les réciproques de ces deux propriétés sont fausses.
Contre-exemples : \(3 \mid 4 + 5\), mais \(3 \nmid 4\) et \(3 \nmid 5\). De même, \(6 \mid 3 \times 4\), mais \(6 \nmid 3\) et \(6 \nmid 4\).
Contre-exemples : \(3 \mid 4 + 5\), mais \(3 \nmid 4\) et \(3 \nmid 5\). De même, \(6 \mid 3 \times 4\), mais \(6 \nmid 3\) et \(6 \nmid 4\).
Méthode (trouver les entiers \(n\) tels que \(n + a\) divise une expression) : on fait apparaître une combinaison des deux expressions qui ne dépend plus de \(n\). On obtient une condition nécessaire ; on vérifie ensuite chaque valeur trouvée.
Exemple 4 :
Déterminer les entiers naturels \(n\) tels que \(n + 1\) divise \(n + 5\).
• Si \(n + 1 \mid n + 5\) : comme \(n + 1 \mid n + 1\), \(n + 1\) divise la différence \((n + 5) - (n + 1) = 4\).
Or \(n + 1 \geq 1\), donc \(n + 1 \in \{1\ ;\ 2\ ;\ 4\}\), soit \(n \in \{0\ ;\ 1\ ;\ 3\}\).
• Réciproquement : \(n = 0\) : \(1 \mid 5\) ✓ ; \(n = 1\) : \(2 \mid 6\) ✓ ; \(n = 3\) : \(4 \mid 8\) ✓.
• Conclusion : \(S = \{0\ ;\ 1\ ;\ 3\}\).
Exemple 5 :
Déterminer les entiers relatifs \(n\) tels que \(n - 2\) divise \(3n + 1\).
• Si \(n - 2 \mid 3n + 1\) : comme \(n - 2 \mid 3(n - 2) = 3n - 6\), \(n - 2\) divise \((3n + 1) - (3n - 6) = 7\).
Donc \(n - 2 \in \{-7\ ;\ -1\ ;\ 1\ ;\ 7\}\), soit \(n \in \{-5\ ;\ 1\ ;\ 3\ ;\ 9\}\).
• Réciproquement : \(-7 \mid -14\) ✓ ; \(-1 \mid 4\) ✓ ; \(1 \mid 10\) ✓ ; \(7 \mid 28\) ✓.
• Conclusion : \(S = \{-5\ ;\ 1\ ;\ 3\ ;\ 9\}\).
