Série 2 — divisibilité, Bézout, Gauss et congruences.
Exercice 1
Déterminer le PGCD de \(1\,071\) et \(462\) par l'algorithme d'Euclide, puis écrire une relation de Bézout.
Correction
\(1\,071 = 2\times462 + 147\) ; \(462 = 3\times147 + 21\) ; \(147 = 7\times21\). Le PGCD est \(21\). Remontée : \(21 = 462 - 3\times147 = 462 - 3(1\,071 - 2\times462) = 7\times462 - 3\times1\,071\).
Exercice 2
Résoudre dans \(\mathbb{Z}\) l'équation \(5x \equiv 3 \pmod 7\).
Correction
\(5\times3 = 15 \equiv 1 \pmod 7\) : l'inverse de \(5\) est \(3\). Donc \(x \equiv 3\times3 = 9 \equiv 2 \pmod 7\) : \(x = 2 + 7k\), \(k\in\mathbb{Z}\).
Exercice 3
Déterminer le reste de la division euclidienne de \(2^{100}\) par \(7\).
Correction
\(2^3 = 8 \equiv 1 \pmod 7\), et \(100 = 3\times33 + 1\). Donc \(2^{100} = \left(2^3\right)^{33}\times2 \equiv 1^{33}\times2 = 2 \pmod 7\) : le reste est \(2\).
Exercice 4
Montrer que, pour tout \(n\in\mathbb{Z}\), \(n(n+1)(n+2)\) est divisible par \(6\).
Correction
Parmi trois entiers consécutifs, au moins un est pair et exactement un est multiple de \(3\). Le produit est donc divisible par \(2\) et par \(3\), qui sont premiers entre eux, donc par \(6\).
Exercice 5
Soient \(a\) et \(b\) premiers entre eux. Montrer que, si \(a \mid bc\), alors \(a \mid c\) (théorème de Gauss).
Correction
D'après Bézout, il existe \(u\) et \(v\) tels que \(au + bv = 1\). En multipliant par \(c\) : \(acu + bcv = c\). \(a\) divise \(acu\) et divise \(bcv\) (car \(a\mid bc\)), donc \(a \mid c\).
Exercice 6
Résoudre dans \(\mathbb{Z}^2\) l'équation \(7x + 5y = 1\).
Correction
Une solution particulière : \(x = 3\), \(y = -4\) (car \(21 - 20 = 1\)). Les solutions générales sont \(x = 3 + 5k\) et \(y = -4 - 7k\), avec \(k\in\mathbb{Z}\).
Exercice 7
Déterminer le chiffre des unités de \(3^{2\,024}\).
Correction
Les unités de \(3^n\) suivent le cycle \(3\), \(9\), \(7\), \(1\) de période \(4\). \(2\,024 = 4\times506\), donc le chiffre des unités est celui de \(3^4\), c'est-à-dire \(1\).