Arithmétique SM
Table des matières
Arithmétique dans \(\mathbb{N}\)
1ère Année Baccalauréat – Sciences Mathématiques
Divisibilité dans \(\mathbb{Z}\)
Définition
Définition
Soient \(a, b \in \mathbb{Z}\). On dit que \(a\) divise \(b\) (ou \(b\) est multiple de \(a\)), et on note \(a \mid b\), s’il existe \(k \in \mathbb{Z}\) tel que \(b = k a\).
Exemples : \(3 \mid 12\) (\(12 = 4 \cdot 3\)), \(-5 \mid 20\), \(0 \mid 0\), \(1 \mid n\) pour tout \(n\).
Propriétés
Proposition
Pour tous \(a, b, c \in \mathbb{Z}\) :
(a) Réflexivité : \(a \mid a\).
(b) Transitivité : \(a \mid b\) et \(b \mid c \Rightarrow a \mid c\).
(c) Antisymétrie : \(a \mid b\) et \(b \mid a \Rightarrow a = \pm b\).
(d) Linéarité : si \(a \mid b\) et \(a \mid c\), alors \(a \mid (\alpha b + \beta c)\) pour tous \(\alpha, \beta \in \mathbb{Z}\).
(e) \(a \mid b\) et \(b \neq 0 \Rightarrow |a| \leq |b|\).
(f) \(a \mid b \Rightarrow a \mid b^n\) pour tout \(n \in \mathbb{N}^*\).
Démonstration
(d) Linéarité. Si \(b = a k_1\) et \(c = a k_2\), alors \(\alpha b + \beta c = a(\alpha k_1 + \beta k_2)\), qui est multiple de \(a\). \(\square\)
Division euclidienne
Théorème
(Division euclidienne) Pour tous \(a \in \mathbb{Z}\) et \(b \in \mathbb{N}^*\), il existe un unique couple \((q, r) \in \mathbb{Z} \times \mathbb{N}\) tel que :
\[a = b q + r \quad \text{avec} \quad 0 \leq r < b.\]
\(q\) est le quotient et \(r\) le reste de la division euclidienne de \(a\) par \(b\).
Remarque
\(a\) est divisible par \(b\) ssi \(r = 0\).
Exemple
Division euclidienne de \(73\) par \(11\) : \(73 = 11 \cdot 6 + 7\), donc \(q = 6\), \(r = 7\).
Division euclidienne de \(-73\) par \(11\) : \(-73 = 11 \cdot (-7) + 4\), donc \(q = -7\), \(r = 4\) (et non \(-6\) et \(-7\)).
PGCD et algorithme d’Euclide
PGCD
Définition
Soient \(a, b \in \mathbb{Z}\) non tous deux nuls. Le plus grand commun diviseur de \(a\) et \(b\), noté \(\mathrm{pgcd}(a, b)\) ou \(a \wedge b\), est le plus grand entier strictement positif qui divise à la fois \(a\) et \(b\).
Par convention, \(\mathrm{pgcd}(0, 0)\) n’est pas défini ; \(\mathrm{pgcd}(a, 0) = |a|\) pour \(a \neq 0\).
Proposition
\[\mathrm{pgcd}(a, b) = \mathrm{pgcd}(b, a) \quad ; \quad \mathrm{pgcd}(a, b) = \mathrm{pgcd}(|a|, |b|).\]
Algorithme d’Euclide
Théorème
(Lemme d’Euclide) Pour \(a \in \mathbb{Z}\) et \(b \in \mathbb{N}^*\), si \(a = b q + r\) (avec \(0 \leq r < b\)), alors :
\[\mathrm{pgcd}(a, b) = \mathrm{pgcd}(b, r).\]
Démonstration
Tout diviseur commun de \(a\) et \(b\) divise \(r = a - bq\) (linéarité), donc est diviseur commun de \(b\) et \(r\). Inversement, tout diviseur commun de \(b\) et \(r\) divise \(a = bq + r\), donc est diviseur commun de \(a\) et \(b\). Les ensembles de diviseurs communs coïncident, leurs plus grands éléments aussi. \(\square\)
Méthode
Algorithme d’Euclide pour calculer \(\mathrm{pgcd}(a, b)\) :
-
Effectuer la division euclidienne : \(a = b q_1 + r_1\) avec \(0 \leq r_1 < b\).
-
Si \(r_1 = 0\), \(\mathrm{pgcd} = b\).
-
Sinon, \(\mathrm{pgcd}(a, b) = \mathrm{pgcd}(b, r_1)\) : on recommence avec \(b\) et \(r_1\).
La suite des restes est strictement décroissante et finit toujours par atteindre \(0\). Le dernier reste non nul est le PGCD.
Exemple
Calculer \(\mathrm{pgcd}(252, 198)\).
Identité de Bézout
Théorème
(Bézout) Pour \(a, b \in \mathbb{Z}\) non tous deux nuls, il existe \(u, v \in \mathbb{Z}\) tels que :
\[a u + b v = \mathrm{pgcd}(a, b).\]
On les trouve par l’algorithme d’Euclide étendu (on remonte les calculs).
Exemple
Trouver \(u, v\) tels que \(252 u + 198 v = 18\).
Nombres premiers entre eux
Définition
On dit que \(a\) et \(b\) sont premiers entre eux si \(\mathrm{pgcd}(a, b) = 1\).
Théorème
(Théorème de Bézout) \(a\) et \(b\) sont premiers entre eux ssi il existe \(u, v \in \mathbb{Z}\) tels que \(a u + b v = 1\).
Théorème
(Lemme de Gauss) Si \(a \mid b c\) et \(\mathrm{pgcd}(a, b) = 1\), alors \(a \mid c\).
Démonstration
Par Bézout, \(a u + b v = 1\) pour certains \(u, v\). Multiplions par \(c\) : \(a u c + b c v = c\). Comme \(a \mid a u c\) et \(a \mid b c\), on a \(a \mid (a u c + b c v) = c\). \(\square\)
PPCM
Définition
Le plus petit commun multiple de \(a, b \in \mathbb{Z}^*\), noté \(\mathrm{ppcm}(a, b)\) ou \(a \vee b\), est le plus petit entier strictement positif qui est multiple à la fois de \(a\) et \(b\).
Proposition
Pour \(a, b \in \mathbb{N}^*\) :
\[\mathrm{pgcd}(a, b) \cdot \mathrm{ppcm}(a, b) = a b.\]
Congruences
Définition
Définition
Soient \(a, b \in \mathbb{Z}\) et \(n \in \mathbb{N}^*\). On dit que \(a\) est congru à \(b\) modulo \(n\), et on note \(a \equiv b \pmod{n}\), si \(n \mid (a - b)\).
De manière équivalente : \(a\) et \(b\) ont le même reste dans la division euclidienne par \(n\).
Exemple
\(17 \equiv 5 \pmod{12}\) (car \(17 - 5 = 12\)).
\(-7 \equiv 3 \pmod{5}\) (car \(-7 - 3 = -10\)).
Tout entier est congru à un unique reste modulo \(n\), élément de \(\{0, 1, \ldots, n-1\}\).
Propriétés
Proposition
(Relation d’équivalence) Pour tous \(a, b, c \in \mathbb{Z}\) et \(n \in \mathbb{N}^*\) :
(a) Réflexivité : \(a \equiv a \pmod{n}\).
(b) Symétrie : \(a \equiv b \pmod{n} \Rightarrow b \equiv a \pmod{n}\).
(c) Transitivité : \(a \equiv b \pmod{n}\) et \(b \equiv c \pmod{n} \Rightarrow a \equiv c \pmod{n}\).
Théorème
(Règles de calcul) Si \(a \equiv a' \pmod{n}\) et \(b \equiv b' \pmod{n}\), alors :
\[a + b \equiv a' + b' \pmod{n} \quad ; \quad a b \equiv a' b' \pmod{n} \quad ; \quad a^k \equiv (a')^k \pmod{n} \;\, (k \in \mathbb{N}).\]
Remarque
Attention : la simplification par un diviseur commun n’est pas toujours valide. On peut diviser par \(c\) ssi \(\mathrm{pgcd}(c, n) = 1\).
Ex : \(4 \equiv 10 \pmod{6}\) mais on ne peut pas simplifier par \(2\) (\(\mathrm{pgcd}(2, 6) = 2 \neq 1\)) : on aurait \(2 \equiv 5 \pmod{6}\), ce qui est faux.
Applications aux congruences
Exemple
Montrer que pour tout \(n \in \mathbb{N}\), \(7^n - 1\) est divisible par \(6\).
Exemple
Déterminer le reste de la division de \(3^{100}\) par \(7\).
Critères de divisibilité
Proposition
Soit \(n = \overline{a_k a_{k-1} \cdots a_1 a_0}\) l’écriture en base \(10\) d’un entier.
\(\bullet\)\(n\) divisible par \(2 \;\Leftrightarrow\; a_0 \in \{0, 2, 4, 6, 8\}\).
\(\bullet\)\(n\) divisible par \(5 \;\Leftrightarrow\; a_0 \in \{0, 5\}\).
\(\bullet\)\(n\) divisible par \(3 \;\Leftrightarrow\; a_0 + a_1 + \cdots + a_k\) divisible par \(3\).
\(\bullet\)\(n\) divisible par \(9 \;\Leftrightarrow\; a_0 + a_1 + \cdots + a_k\) divisible par \(9\).
\(\bullet\)\(n\) divisible par \(11 \;\Leftrightarrow\; a_0 - a_1 + a_2 - \cdots\) divisible par \(11\).
Synthèse
Récapitulatif
| Notion | Caractérisation |
|---|---|
| \(a \mid b\) | \(\exists k \in \mathbb{Z},\, b = k a\) |
| Division euclidienne | \(a = bq + r\), \(0 \leq r < b\) (unique) |
| PGCD | plus grand diviseur commun, calculé par Euclide |
| Bézout | \(a u + b v = \mathrm{pgcd}(a, b)\) pour certains \(u, v \in \mathbb{Z}\) |
| Premiers entre eux | \(\mathrm{pgcd}(a, b) = 1 \,\Leftrightarrow\, \exists u, v,\, a u + b v = 1\) |
| Gauss | \(a \mid bc\) et \(\mathrm{pgcd}(a, b) = 1 \Rightarrow a \mid c\) |
| PPCM | \(\mathrm{ppcm}(a,b) \cdot \mathrm{pgcd}(a,b) = a b\) (pour \(a, b > 0\)) |
| Congruence | \(a \equiv b \pmod n \,\Leftrightarrow\, n \mid (a - b)\) |
Pièges classiques
Remarque
-
Division euclidienne avec \(a < 0\). Le reste est toujours \(\geq 0\).
-
Simplification dans une congruence. On ne peut diviser par \(c\) que si \(\mathrm{pgcd}(c, n) = 1\).
-
\(\mathrm{pgcd}(a, 0) = |a|\). Cas particulier souvent oublié.
-
Bézout fonctionne seulement avec le PGCD. L’équation \(a u + b v = c\) a des solutions ssi \(\mathrm{pgcd}(a, b) \mid c\).
-
Critère de divisibilité par 11. Alternance des signes.
Fin du chapitre 4 – Arithmétique dans \(\mathbb{N}\)