Maths Expertes · Math@mine
Un carillon sonne toutes les 12 minutes, un autre toutes les 18 minutes. Ils ont sonné ensemble à midi.
Euclide (IIIe siècle av. J.-C., Éléments VII) formule l’algorithme du PGCD et prouve que la liste des nombres premiers est infinie — deux résultats fondamentaux de la théorie des nombres. Thābit ibn Qurra (IXe siècle, Bagdad) approfondit la théorie des nombres et découvre une règle pour générer des nombres amiables.
Al-Farisi (XIIIe siècle) donne une nouvelle démonstration de l’infinité des nombres premiers, indépendamment de la preuve d’Euclide, montrant la vitalité de la tradition mathématique islamique en théorie des nombres.
📜 Lire l’article — Euclide et Thābit ibn Qurra : le plus vieil algorithme →
Appliquer l’algorithme d’Euclide à \(\pgcd(1071, 462)\), puis remonter les calculs pour exprimer ce PGCD comme combinaison linéaire \(1071u + 462v\) (théorème de Bézout).
Soit \(a, b \in \mathbb{Z}\) avec \(b \neq 0\). On dit que \(b\) divise \(a\), noté \(b \mid a\), s’il existe \(k \in \mathbb{Z}\) tel que \(a = kb\).
On dit aussi que \(a\) est un multiple de \(b\), ou que \(b\) est un diviseur de \(a\).
Pour tous \(a, b, c \in \mathbb{Z}\) :
1. Réflexivité. On a \(a = 1 \times a\), donc \(a \mid a\). ∎
2. Transitivité. \(a \mid b\) signifie \(b = ka\) pour un certain \(k \in \mathbb{Z}\). \(b \mid c\) signifie \(c = lb\) pour un certain \(l \in \mathbb{Z}\). Alors \(c = lb = l(ka) = (lk)a\), et \(lk \in \mathbb{Z}\), donc \(a \mid c\). ∎
3. Combinaison linéaire. \(a \mid b\) donne \(b = k_1 a\), \(a \mid c\) donne \(c = k_2 a\). Alors \(ub + vc = uk_1 a + vk_2 a = (uk_1 + vk_2)a\), et \(uk_1+vk_2 \in \mathbb{Z}\), donc \(a \mid (ub+vc)\). ∎
4. Double divisibilité. \(a \mid b\) donne \(b = ka\) et \(b \mid a\) donne \(a = lb\). En substituant : \(a = l(ka) = (lk)a\), donc \(lk = 1\) dans \(\mathbb{Z}\). Les seuls entiers de produit 1 sont \(l = k = 1\) ou \(l = k = -1\). Donc \(b = \pm a\). ∎
Toute partie non vide de \(\mathbb{N}\) admet un plus petit élément.
Cette propriété est spécifique à \(\mathbb{N}\) : elle est fausse dans \(\mathbb{Z}\) et dans les intervalles ouverts de \(\mathbb{R}\).
Résultat admis. Le bon ordre de \(\mathbb{N}\) est un axiome (ou une conséquence immédiate de la construction axiomatique des entiers naturels, Peano). Il est admis sans démonstration en Maths Expertes.
Lien avec la récurrence. Le bon ordre de \(\mathbb{N}\) est équivalent au principe de récurrence :
Esquisse (sens direct). Soit \(P(n)\) une propriété qui satisfait \(P(0)\) et « \(P(n) \Rightarrow P(n+1)\) ». Supposons par l’absurde que \(P\) n’est pas vraie pour tous les \(n\). Soit \(E = \{n \in \mathbb{N} : P(n)\text{ est fausse}\}\). Alors \(E\) est non vide, donc par le bon ordre, \(E\) a un plus petit élément \(n_0\). On a \(n_0 \ge 1\) (car \(P(0)\) vraie), donc \(n_0 - 1 \in \mathbb{N}\) et \(n_0 - 1 \notin E\) (minimalité). Donc \(P(n_0 - 1)\) est vraie, ce qui entraîne \(P(n_0)\) vraie par hérédité : contradiction. ∎
Pour tous \(a \in \mathbb{Z}\) et \(b \in \mathbb{Z}^*\), il existe un unique couple \((q, r) \in \mathbb{Z} \times \mathbb{N}\) tel que :
\(a = bq + r \quad \text{avec} \quad 0 \le r < |b|\)
\(q\) est le quotient et \(r\) est le reste de la division euclidienne de \(a\) par \(b\).
On a : \(b \mid a \Leftrightarrow r = 0\).
On suppose \(b > 0\) (le cas \(b < 0\) s’y ramène en remplaçant \(b\) par \(-b\)).
Existence. Considérons l’ensemble \(E = \{a - bk \mid k \in \mathbb{Z},\ a - bk \ge 0\} \subseteq \mathbb{N}\).
Cet ensemble est non vide : si \(a \ge 0\) on prend \(k = 0\) ; si \(a < 0\) on prend \(k = a\) (alors \(a - ba = a(1-b)\), et pour \(b \ge 1\) et \(a < 0\) ce nombre est positif).
Par la propriété de bon ordre de \(\mathbb{N}\), \(E\) admet un plus petit élément \(r = a - bq\), pour un certain \(q \in \mathbb{Z}\). On a donc \(a = bq + r\) avec \(r \ge 0\).
Montrons que \(r < b\). Si \(r \ge b\), alors \(r - b = a - bq - b = a - b(q+1) \ge 0\) est dans \(E\) et est strictement plus petit que \(r\), ce qui contredit la minimalité de \(r\). Donc \(r < b\).
Unicité. Supposons \(a = bq + r = bq' + r'\) avec \(0 \le r, r' < b\). Alors \(b(q-q') = r' - r\), donc \(b \mid (r'-r)\). Mais \(|r'-r| < b\), donc \(r'-r = 0\), soit \(r = r'\), puis \(q = q'\). ∎
\(123 = 17 \times 7 + 4\) : quotient \(q = 7\), reste \(r = 4\). Donc \(17 \nmid 123\).
\(-17 = (-6)\times 3 + 1\) : quotient \(q = -6\), reste \(r = 1 \ge 0\). ✓
Soit \(n \in \mathbb{N}^*\). On dit que \(a\) est congru à \(b\) modulo \(n\), noté \(a \equiv b \pmod{n}\), si \(n \mid (a - b)\), c’est-à-dire si \(a\) et \(b\) ont le même reste dans la division par \(n\).
La congruence modulo \(n\) est une relation d’équivalence. De plus, si \(a \equiv b \pmod{n}\) et \(c \equiv d \pmod{n}\), alors :
Addition. Si \(a \equiv b \pmod{n}\) et \(c \equiv d \pmod{n}\), alors \(n \mid (a-b)\) et \(n \mid (c-d)\). Par combinaison linéaire : \(n \mid (a-b)+(c-d) = (a+c)-(b+d)\), donc \(a+c \equiv b+d \pmod{n}\). ∎
Multiplication. On écrit \(ac - bd = ac - bc + bc - bd = c(a-b) + b(c-d)\). Puisque \(n \mid (a-b)\) et \(n \mid (c-d)\), par combinaison linéaire \(n \mid c(a-b) + b(c-d) = ac-bd\), donc \(ac \equiv bd \pmod{n}\). ∎
Puissance. Par récurrence sur \(k\). Pour \(k=0\) : \(a^0 = 1 \equiv 1 = b^0\). Si \(a^k \equiv b^k \pmod{n}\), alors par la règle de multiplication appliquée à \(a^k \equiv b^k\) et \(a \equiv b\) : \(a^{k+1} \equiv b^{k+1} \pmod{n}\). ∎
Relation d’équivalence. Réflexivité : \(n \mid (a-a) = 0\) ✓. Symétrie : \(n \mid (a-b) \Rightarrow n \mid (b-a)\) ✓. Transitivité : \(n\mid(a-b)\) et \(n\mid(b-c)\) donne \(n\mid(a-c)\) par combinaison linéaire ✓.
Pour calculer \(a^k \pmod{n}\) sans calculer \(a^k\) en entier, on utilise les congruences de façon répétée.
Astuce : écrire \(k\) en base 2 et utiliser la méthode d'exponentiation rapide.
Cherchons la période de \(3^k \pmod{7}\) :
\(3^1 \equiv 3\), \(3^2 \equiv 2\), \(3^3 \equiv 6\), \(3^4 \equiv 4\), \(3^5 \equiv 5\), \(3^6 \equiv 1 \pmod 7\).
La suite est périodique de période 6. Or \(100 = 16 \times 6 + 4\), donc \(3^{100} \equiv 3^4 \equiv 4 \pmod{7}\).
Le dernier chiffre de \(7^n\) dépend de \(n \pmod{4}\) : \(7^1=7\), \(7^2=49\), \(7^3=343\), \(7^4=2401\), \(7^5=16807\ldots\) (période 4).
\(2026 = 506 \times 4 + 2\), donc \(7^{2026} \equiv 7^2 \equiv 9 \pmod{10}\). Le dernier chiffre est 9.
Soit \(n \in \mathbb{N}^*\). Pour \(a \in \mathbb{Z}\), la classe de congruence de \(a\) modulo \(n\) est l’ensemble :
\(\overline{a} = [a]_n = \{b \in \mathbb{Z} \mid b \equiv a \pmod{n}\} = \{a + kn \mid k \in \mathbb{Z}\}.\)
Les classes \([0], [1], \ldots, [n-1]\) sont les seules classes distinctes (toute classe \([a]\) est égale à l’une d’elles, prise pour \(a \bmod n\)).
L’ensemble des classes de congruence modulo \(n\) se note :
\(\mathbb{Z}/n\mathbb{Z} = \{[0], [1], [2], \ldots, [n-1]\}.\)
Il contient exactement \(n\) éléments. Les opérations \(+\) et \(\times\) sur \(\mathbb{Z}\) passent au quotient grâce aux propriétés ci-dessus :
\([a] + [b] = [a+b], \qquad [a] \times [b] = [a \times b].\)
L’ensemble \(\mathbb{Z}/5\mathbb{Z} = \{[0], [1], [2], [3], [4]\}\). On note simplement \(0, 1, 2, 3, 4\).
Addition
| + | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 |
| 1 | 1 | 2 | 3 | 4 | 0 |
| 2 | 2 | 3 | 4 | 0 | 1 |
| 3 | 3 | 4 | 0 | 1 | 2 |
| 4 | 4 | 0 | 1 | 2 | 3 |
Multiplication
| × | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 |
| 2 | 0 | 2 | 4 | 1 | 3 |
| 3 | 0 | 3 | 1 | 4 | 2 |
| 4 | 0 | 4 | 3 | 2 | 1 |
Observation : dans \(\mathbb{Z}/5\mathbb{Z}\), tous les éléments non nuls (\(1, 2, 3, 4\)) ont un inverse multiplicatif (la valeur 1 apparaît dans chaque ligne ≠ 0). Par exemple \(2 \times 3 = 1\), donc \(2^{-1} = 3\). C’est une propriété générale : quand \(n\) est premier, tous les éléments non nuls de \(\mathbb{Z}/n\mathbb{Z}\) sont inversibles.
| × | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 | 5 |
| 2 | 0 | 2 | 4 | 0 | 2 | 4 |
| 3 | 0 | 3 | 0 | 3 | 0 | 3 |
| 4 | 0 | 4 | 2 | 0 | 4 | 2 |
| 5 | 0 | 5 | 4 | 3 | 2 | 1 |
Observations :
La classe \([a]\) est inversible dans \(\mathbb{Z}/n\mathbb{Z}\) (c’est-à-dire qu’il existe \([b]\) tel que \([a]\times[b] = [1]\)) si et seulement si \(\pgcd(a, n) = 1\).
La démonstration et le calcul effectif de l’inverse reposent sur le théorème de Bézout, étudié au chapitre 9, section 9.2.
Soit \(N = \overline{a_n a_{n-1} \ldots a_1 a_0}\) un entier écrit en base 10. Alors :
On a \(N = \sum_{k=0}^{n} a_k \cdot 10^k\). L’idée clé est de réduire \(10^k\) modulo le diviseur étudié.
Critères par 2 et 5. On a \(10 \equiv 0 \pmod{2}\) et \(10 \equiv 0 \pmod{5}\), donc \(10^k \equiv 0\) pour \(k \ge 1\). Ainsi \(N \equiv a_0 \pmod{2}\) et \(N \equiv a_0 \pmod{5}\) : seul le dernier chiffre importe. ∎
Critère par 3 (et 9). On a \(10 \equiv 1 \pmod{3}\) et \(10 \equiv 1 \pmod{9}\), donc \(10^k \equiv 1^k = 1\). Ainsi \(N \equiv \sum_k a_k \pmod{3}\) et \(N \equiv \sum_k a_k \pmod{9}\). ∎
Critère par 11. On a \(10 \equiv -1 \pmod{11}\), donc \(10^k \equiv (-1)^k\). Ainsi \(N \equiv \sum_k (-1)^k a_k = a_0 - a_1 + a_2 - \cdots \pmod{11}\). ∎
Le même raisonnement s’applique à toute base \(b\) et tout diviseur \(d\) : il suffit de connaître \(b \pmod{d}\) pour établir le critère correspondant.
Somme des chiffres : \(1+2+3+4+5+6 = 21\). Divisible par 3 mais pas par 9.
Somme alternée : \(6-5+4-3+2-1 = 3\). Pas divisible par 11.
Programmer l’algorithme d’Euclide pour calculer le PGCD de deux entiers :
pgcd(a, b) qui affiche chaque étape de la division euclidienne et renvoie le PGCDppcm(a, b) utilisant la relation \(\text{ppcm}(a,b) = \dfrac{|a \times b|}{\text{pgcd}(a,b)}\)Rappel Python : divmod(a, b) renvoie le couple (quotient, reste). math.gcd(a, b) est le PGCD natif Python.
Explorer l’exponentiation modulaire et les critères de divisibilité :
critere_div(N) qui affiche la somme des chiffres, la somme alternée, et en déduit la divisibilité par 3, 9 et 11Rappel Python : pow(a, n, m) calcule \(a^n \bmod m\) efficacement (exponentiation rapide). Critère par 3 : somme des chiffres divisible par 3. Critère par 11 : somme alternée divisible par 11.
Entre deux entiers et observe les divisions euclidiennes successives.
| Notion | Définition / Formule | Piège à éviter |
|---|---|---|
| Divisibilité | \(a \mid b \iff \exists\, k \in \mathbb{Z},\; b = ka\) | \(a \mid b\) signifie que \(a\) divise \(b\), pas l’inverse |
| Division euclidienne | \(a = bq + r\) avec \(0 \leq r < |b|\) | Le reste \(r\) est toujours positif ou nul |
| Congruences | \(a \equiv b \pmod{n} \iff n \mid (a - b)\) | On ne peut pas diviser une congruence par n’importe quel entier |
| Compatibilité | Si \(a \equiv a'\) et \(b \equiv b'\) (mod \(n\)), alors \(a+b\equiv a'+b'\), \(ab\equiv a'b'\) (mod \(n\)) | Pas de division en général (sauf si \(\pgcd(\text{diviseur},n)=1\)) |
| Critères de divisibilité | Par 2, 3, 5, 9, 11 — démontrés via les congruences | Critère par 11 : alterner les signes des chiffres |
Étapes : \(1071 = 462\times2 + 147\) ; \(462 = 147\times3 + 21\) ; \(147 = 21\times7 + 0\). Donc \(\pgcd = 21\). Remontée : \(21 = 462 - 147\times3 = 462 - (1071-462\times2)\times3 = 7\times462 - 3\times1071\). Bézout : \(21 = -3\times1071 + 7\times462\).
Divisibilité et congruences : teste d’abord ton intuition.
« Si \(a\) divise \(b+c\), alors \(a\) divise \(b\) et \(a\) divise \(c\). »
Cette affirmation est-elle vraie ?
C’est faux ! Contre-exemple : \(6 \mid 12\) (car \(5+7=12\)), mais \(6 \nmid 5\) et \(6 \nmid 7\). La divisibilité de la somme n’implique pas la divisibilité de chaque terme.
Mini-test : \(3 \mid 12\). Peut-on affirmer que \(3 \mid 5\) et \(3 \mid 7\) ?
Voir section 1
« \(\pgcd(a,b) \times \ppcm(a,b) = a + b\). »
Cette affirmation est-elle vraie ?
C’est faux ! La bonne formule est \(\pgcd(a,b) \times \ppcm(a,b) = a \times b\) (produit, pas somme). Par exemple : \(\pgcd(6,4)=2\), \(\ppcm(6,4)=12\), et \(2 \times 12 = 24 = 6 \times 4 \neq 6+4=10\).
Mini-test : \(\pgcd(12,8) = 4\) et \(\ppcm(12,8) = 24\). Quel est le produit \(12 \times 8\) ?
Voir ch. 9 §9.1 (preuve par Gauss) ou ch. 10 §10.3 (preuve par décomposition en facteurs premiers)
« Si \(a \equiv b \pmod{n}\) et \(c \equiv d \pmod{n}\), alors \(\frac{a}{c} \equiv \frac{b}{d} \pmod{n}\). »
Cette affirmation est-elle vraie ?
C’est faux ! On peut additionner, soustraire et multiplier les congruences, mais on ne peut pas diviser en général. Par exemple : \(6 \equiv 0 \pmod{3}\) et \(3 \equiv 0 \pmod{3}\), mais \(6/3 = 2\) et \(0/0\) n’a pas de sens.
Mini-test : \(10 \equiv 4 \pmod{6}\). Peut-on simplifier par 2 pour obtenir \(5 \equiv 2 \pmod{6}\) ?
Voir section 2
« Si un nombre est divisible par 6 et par 4, alors il est divisible par 24. »
Cette affirmation est-elle vraie ?
C’est faux ! Contre-exemple : 12 est divisible par 6 et par 4, mais \(12 \div 24\) ne tombe pas juste. Le résultat serait vrai si 6 et 4 étaient premiers entre eux, mais \(\pgcd(6,4) = 2 \neq 1\). On peut seulement affirmer que le nombre est divisible par \(\ppcm(6,4) = 12\).
Mini-test : un nombre est divisible par 3 et par 5. Il est nécessairement divisible par :
« Si \(p\) est un nombre quelconque et \(p \mid a^2\), alors \(p \mid a\). »
Cette affirmation est-elle vraie ?
C’est faux en général ! Si \(p\) n’est pas premier, le résultat peut échouer. Contre-exemple : \(4 \mid 36 = 6^2\) mais \(4 \nmid 6\). Le résultat est vrai seulement si \(p\) est premier (par le lemme d’Euclide).
Mini-test : \(9 \mid 36\). Est-ce que \(9 \mid 6\) ?
Voir section 1
« Si \(a\) divise \(b\) et \(a\) divise \(c\), alors \(a\) divise \(b+c\). »
Cette affirmation est-elle vraie ?
C’est vrai ! C’est une propriété fondamentale de la divisibilité. Si \(b = aq\) et \(c = aq'\), alors \(b+c = a(q+q')\), donc \(a \mid (b+c)\). Attention à ne pas confondre avec le piège 1 (le sens réciproque est faux).
Mini-test : \(4 \mid 12\) et \(4 \mid 20\). Alors \(4 \mid 32\) ?
Voir section 1