Série 2 — Bézout, Gauss, congruences et petit théorème de Fermat.
Exercice 1
Déterminer le PGCD de \(2\,023\) et \(1\,071\), puis une relation de Bézout.
Correction
\(2\,023 = 1\times1\,071 + 952\) ; \(1\,071 = 1\times952 + 119\) ; \(952 = 8\times119 + 0\) : le PGCD est \(119\). Remontée : \(119 = 1\,071 - 952 = 1\,071 - (2\,023 - 1\,071) = 2\times1\,071 - 2\,023\).
Exercice 2
Résoudre dans \(\mathbb{Z}^2\) : \(5x - 3y = 1\).
Correction
Solution particulière : \((2\,;3)\) car \(10 - 9 = 1\). Solutions générales : \(x = 2 + 3k\) et \(y = 3 + 5k\), \(k\in\mathbb{Z}\).
Exercice 3
Déterminer le reste de \(7^{100}\) modulo \(11\).
Correction
D'après le petit théorème de Fermat, \(7^{10} \equiv 1 \pmod{11}\). \(100 = 10\times10\), donc \(7^{100} \equiv 1 \pmod{11}\) : le reste est \(1\).
Exercice 4
Résoudre le système de congruences \(\begin{cases} x \equiv 2 \pmod 3 \\ x \equiv 3 \pmod 5 \end{cases}\).
Correction
\(x = 2 + 3k\) ; on veut \(2 + 3k \equiv 3 \pmod 5\), soit \(3k \equiv 1 \pmod 5\). L'inverse de \(3\) modulo \(5\) est \(2\) : \(k \equiv 2 \pmod 5\), donc \(k = 2 + 5m\) et \(x = 8 + 15m\).
Exercice 5
Montrer que, pour tout \(n\in\mathbb{Z}\), \(n^5 - n\) est divisible par \(30\).
Correction
\(n^5 - n = n(n^4-1) = n(n^2-1)(n^2+1) = (n-1)n(n+1)(n^2+1)\). Le produit de trois entiers consécutifs est divisible par \(6\) ; pour \(5\), on applique Fermat : \(n^5 \equiv n \pmod 5\). Comme \(5\) et \(6\) sont premiers entre eux, le produit est divisible par \(30\).
Exercice 6
Montrer que si \(d = \mathrm{PGCD}(a\,;b)\), alors \(\mathrm{PGCD}\left(\dfrac ad\,;\dfrac bd\right) = 1\).
Correction
D'après Bézout, \(au + bv = d\) ; en divisant par \(d\) : \(\dfrac ad u + \dfrac bd v = 1\). D'après la réciproque de Bézout, les deux quotients sont premiers entre eux.
Exercice 7
Déterminer les entiers \(n\) tels que \(n + 3\) divise \(n^2 + 1\).
Correction
\(n^2 + 1 = (n+3)(n-3) + 10\), donc \(n+3\) doit diviser \(10\). Les diviseurs de \(10\) sont \(\pm1\), \(\pm2\), \(\pm5\), \(\pm10\) : \(n \in \{-2\,;-4\,;-1\,;-5\,;2\,;-8\,;7\,;-13\}\).