L'essentiel en une page
| Théorème | Énoncé |
|---|---|
| Division euclidienne | \(a = bq + r\), \(0 \le r < \lvert b\rvert\) |
| Euclide | le PGCD est le dernier reste non nul |
| Bézout | \(au + bv = \mathrm{PGCD}(a\,;b)\) |
| Bézout (réciproque) | \(au + bv = 1 \Rightarrow a\wedge b = 1\) |
| Gauss | \(a\mid bc\) et \(a\wedge b = 1 \Rightarrow a\mid c\) |
| Fermat | \(p\) premier, \(p\nmid a\) : \(a^{p-1} \equiv 1 \pmod p\) |
Congruences : on peut additionner, multiplier, élever à une puissance ; pour « diviser », il faut un inverse modulo \(n\).
Équation \(ax+by=c\) : solvable si et seulement si \(d = a\wedge b\) divise \(c\) ; solutions \(x = x_0 + \frac bd k\), \(y = y_0 - \frac ad k\).
Divisibilité d'une expression : écrire \(N = (n+a)Q + r\) ; alors \(n+a \mid N\) équivaut à \(n+a \mid r\).
Ce que je dois savoir faire
- Appliquer Euclide puis remonter pour Bézout.
- Résoudre une congruence linéaire avec un inverse.
- Utiliser Fermat pour un reste de puissance.
- Résoudre une équation diophantienne complète.
- Résoudre un système de congruences.
Les pièges à éviter
- Gauss exige l'hypothèse « premiers entre eux ».
- Fermat exige \(p\) premier et \(p \nmid a\).
- Une diophantienne a une infinité de solutions.
- Vérifier la solution particulière avant de généraliser.
Testez-vous en 3 minutes
PGCD de \(18\) et \(24\) ? Inverse de \(3\) modulo \(7\) ? \(2^6\) modulo \(7\) ? Solutions de \(x \equiv 1 \pmod 4\) ?
Réponses
\(6\) ; \(5\) ; \(1\) ; \(x = 1 + 4k\).