Terminale E · Leçon 6
Arithmétique dans ℤ
Divisibilité et division euclidienne dans ℤ
Avant d'étudier les nombres premiers ou les congruences, il faut solidifier la notion la plus élémentaire : celle de diviseur. Toute l'arithmétique en découle.
Soit \(a, b \in \mathbb{Z}\). On dit que \(b\) divise \(a\), noté \(b \mid a\), s'il existe un entier \(k \in \mathbb{Z}\) tel que \(a = k b\). On dit alors que \(a\) est un multiple de \(b\).
Si \(b \mid a\) et \(b \mid a'\), alors pour tous entiers \(u, v\), on a \(b \mid (ua + va')\) : la divisibilité se conserve par combinaison linéaire à coefficients entiers. En particulier, elle se conserve par addition et soustraction.
Quelques cas particuliers à mémoriser : \(1\) divise tout entier ; tout entier divise \(0\) ; si \(b \mid a\) et \(a \ne 0\), alors \(|b| \le |a|\). L'ensemble des multiples de \(b\) dans \(\mathbb{Z}\) se note \(b\mathbb{Z}\).
Facile. On a \(3 \mid 12\) car \(12 = 3 \times 4\). On a aussi \(3 \mid (-12)\) car \(-12 = 3 \times (-4)\). En revanche, \(3 \nmid 10\) car il n'existe pas d'entier \(k\) tel que \(10 = 3k\).
Intermédiaire. Montrons que si \(5 \mid a\) et \(5 \mid b\), alors \(5 \mid (2a - 3b)\). On écrit \(a = 5k\) et \(b = 5m\), donc \(2a - 3b = 10k - 15m = 5(2k - 3m)\). C'est bien un multiple de \(5\).
Plus avancé. Montrons que si \(7 \mid (a + 2b)\) et \(7 \mid (3a - b)\), alors \(7 \mid a\) et \(7 \mid b\). On calcule \((a+2b) + 2(3a-b) = 7a\), donc \(7 \mid 7a\), ce qui donne \(7 \mid a\). De même, \(3(a+2b)-(3a-b)=7b\), donc \(7 \mid b\).
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 euclidien et \(r\) le reste euclidien de la division de \(a\) par \(b\).
Le piège classique concerne les entiers négatifs. La règle est simple : on cherche le plus grand multiple de \(b\) qui reste inférieur ou égal à \(a\), de sorte que le reste soit dans \(\{0, 1, \ldots, |b|-1\}\).
Pour diviser \(-37\) par \(5\), on cherche \(q\) tel que \(5q \le -37\) et \(-37 - 5q < 5\). On trouve \(q = -8\) (car \(5 \times (-8) = -40 \le -37\) et \(5 \times (-7) = -35 > -37\)). Alors \(r = -37 - 5\times(-8) = 3\).
\[ -37 = 5 \times (-8) + 3 \quad (0 \le 3 < 5). \]\(127 = 9 \times 14 + 1\) : quotient \(14\), reste \(1\).
\(-100 = 7 \times (-15) + 5\), car \(7 \times (-15) = -105\) et \(-105 + 5 = -100\), avec \(0 \le 5 < 7\). Le quotient est \(-15\), le reste \(5\).
\(28 = 4 \times 7 + 0\) : le reste est \(0\), donc \(4 \mid 28\).
Ne jamais écrire \(-37 = 5 \times (-7) + (-2)\), même si le calcul est juste arithmétiquement. La condition \(r \ge 0\) est violée : \(-2 < 0\). Ce couple \((q, r)\) n'est pas le résultat de la division euclidienne.
Figure interactive — Division euclidienne
La droite des entiers montre graphiquement comment le dividende \(a\) se positionne entre deux multiples consécutifs de \(b\). Le reste \(r\) est la distance entre \(a\) et le multiple inférieur \(bq\).
Congruences et restes
Les congruences sont une façon de travailler dans un « monde circulaire » : modulo \(n\), on identifie tous les entiers qui ont le même reste par \(n\). C'est le langage naturel des cycles, des calendriers et des codes.
Soit \(n \in \mathbb{N}^{*}\). On dit que \(a\) et \(b\) sont congrus modulo \(n\), noté \(a \equiv b\ [n]\), si \(n \mid (a - b)\). De façon équivalente, \(a\) et \(b\) ont le même reste dans la division euclidienne par \(n\).
Si \(a \equiv a'\ [n]\) et \(b \equiv b'\ [n]\), alors on peut additionner, soustraire et multiplier membre à membre :
\[ a + b \equiv a' + b'\ [n] \qquad a - b \equiv a' - b'\ [n] \qquad a \times b \equiv a' \times b'\ [n]. \]Par récurrence sur la propriété multiplicative, on obtient aussi la compatibilité avec les puissances entières :
\[ a \equiv a'\ [n] \implies a^k \equiv a'^k\ [n] \quad \text{pour tout } k \in \mathbb{N}. \]La division n'est pas compatible avec les congruences en général. Contre-exemple : \(4 \equiv 10\ [6]\) (car \(6 \mid -6\)), mais si on divise par \(2\), on obtiendrait \(2 \equiv 5\ [3]\), qui est faux (\(3 \nmid -3\)). On peut diviser une congruence par \(k\) uniquement si \(\text{pgcd}(k, n) = 1\), c'est-à-dire si \(k\) est premier avec le module.
Pour trouver le reste de \(a^n\) modulo \(m\), on cherche la période du cycle des restes de \(a^1, a^2, a^3, \ldots\) modulo \(m\). Le procédé : on réduit d'abord \(a\) modulo \(m\), on calcule les puissances successives jusqu'à retrouver \(1\) (ou la valeur de départ), puis on exprime \(n\) en fonction de cette période.
Exemple type Bac. Calculer le reste de \(7^{100}\) dans la division par \(5\).
Étape 1 — Réduction : \(7 \equiv 2\ [5]\), donc \(7^{100} \equiv 2^{100}\ [5]\).
Étape 2 — Cycle des restes de \(2^k\) modulo \(5\) :
\[ 2^1 \equiv 2,\quad 2^2 \equiv 4,\quad 2^3 \equiv 3,\quad 2^4 \equiv 1,\quad 2^5 \equiv 2,\ldots\ [5]. \]La période est \(4\). Étape 3 — Décomposition de l'exposant : \(100 = 4 \times 25\), donc \(2^{100} = (2^4)^{25} \equiv 1^{25} = 1\ [5]\).
Conclusion : le reste de \(7^{100}\) dans la division par \(5\) est \(\mathbf{1}\).
Critère de divisibilité par 9. Puisque \(10 \equiv 1\ [9]\), on a \(10^j \equiv 1\ [9]\) pour tout \(j \ge 0\). Tout entier \(N = a_k \cdot 10^k + \cdots + a_1 \cdot 10 + a_0\) vérifie donc \(N \equiv a_k + \cdots + a_1 + a_0\ [9]\). Ainsi \(9 \mid N\) si et seulement si la somme de ses chiffres est divisible par 9. Application : \(N = 2\,016\), somme des chiffres \(= 9\), donc \(9 \mid 2016\). Vérifié : \(2016 = 9 \times 224\).
Reste de \(3^{2025}\) modulo \(7\). Cycle de \(3^k\) mod 7 : \(3, 2, 6, 4, 5, 1\) (période 6). \(2025 = 6 \times 337 + 3\), donc \(3^{2025} \equiv 3^3 = 27 \equiv 6\ [7]\). Le reste est \(\mathbf{6}\).
Parité de \(n^2 + n\). Quel que soit \(n\), soit \(n \equiv 0\ [2]\) soit \(n \equiv 1\ [2]\). Dans les deux cas, \(n^2 + n = n(n+1)\) est le produit de deux entiers consécutifs, donc \(n^2 + n \equiv 0\ [2]\) : \(n^2 + n\) est toujours pair.
Figure interactive — Horloge modulaire
La roue montre les classes de congruence modulo \(n\). Chaque entier est placé sur la roue selon son reste par \(n\). Deux entiers se trouvent sur la même case si et seulement si ils sont congrus modulo \(n\).
PGCD, PPCM et algorithme d'Euclide
Lorsqu'on veut simplifier une fraction ou savoir si deux entiers partagent un facteur commun, on cherche leur plus grand commun diviseur. L'algorithme d'Euclide est la méthode efficace pour le calculer, quel que soit l'ordre de grandeur des entiers.
Pour \(a, b \in \mathbb{Z}\) non tous nuls, le plus grand commun diviseur \(\text{pgcd}(a, b)\) est le plus grand entier naturel qui divise à la fois \(a\) et \(b\). Le plus petit commun multiple \(\text{ppcm}(a, b)\) est le plus petit entier naturel non nul qui est divisible à la fois par \(a\) et par \(b\).
On dit que \(a\) et \(b\) sont premiers entre eux (ou copremiers) si \(\text{pgcd}(a,b) = 1\). C'est la condition clé pour appliquer le théorème de Gauss et Bézout.
Si \(d = \text{pgcd}(a, b)\), alors \(a/d\) et \(b/d\) sont premiers entre eux. Par ailleurs, \(\text{pgcd}(ka, kb) = k \cdot \text{pgcd}(a, b)\) pour tout entier \(k > 0\).
Si \(a = bq + r\) est la division euclidienne de \(a\) par \(b\), alors :
\[\text{pgcd}(a, b) = \text{pgcd}(b, r).\]En répétant le procédé (on remplace \((a, b)\) par \((b, r)\) à chaque étape), la suite des restes est strictement décroissante et positive, donc elle atteint nécessairement \(0\). Le dernier reste non nul est le PGCD.
On présente les divisions successives en colonnes. À chaque ligne on écrit \(a_k = b_k q_k + r_k\) avec \(0 \le r_k < b_k\), puis on passe à \((a_{k+1}, b_{k+1}) = (b_k, r_k)\). On s'arrête quand \(r_k = 0\).
Calcul de \(\text{pgcd}(252, 198)\) :
\[ \begin{aligned} 252 &= 198 \times 1 + 54 \\ 198 &= 54 \times 3 + 36 \\ 54 &= 36 \times 1 + 18 \\ 36 &= 18 \times 2 + 0 \quad \leftarrow \text{reste nul} \end{aligned} \]Dernier reste non nul : \(\mathbf{18}\). Donc \(\text{pgcd}(252, 198) = 18\). Et \(\text{ppcm}(252, 198) = \dfrac{252 \times 198}{18} = 2772\).
Rapide. \(\text{pgcd}(48, 18)\) : \(48 = 18 \times 2 + 12\) ; \(18 = 12 \times 1 + 6\) ; \(12 = 6 \times 2 + 0\). Donc \(\text{pgcd}(48,18) = 6\).
Intermédiaire. \(\text{pgcd}(1071, 462)\) : \(1071 = 462 \times 2 + 147\) ; \(462 = 147 \times 3 + 21\) ; \(147 = 21 \times 7 + 0\). Donc \(\text{pgcd}(1071, 462) = 21\).
Astuce de vérification. On vérifie que le PGCD trouvé divise bien les deux nombres. Ici : \(252 / 18 = 14\) et \(198 / 18 = 11\). De plus, \(\text{pgcd}(14, 11) = 1\) : les quotients sont bien premiers entre eux.
Figure interactive — Algorithme d'Euclide pas à pas
Choisissez deux entiers et observez la suite des divisions euclidiennes. Chaque barre représente un reste successif. La convergence vers \(0\) révèle le PGCD.
Bézout, Gauss et équations diophantiennes
L'identité de Bézout traduit le fait que le PGCD est une combinaison linéaire entière des deux nombres de départ. C'est elle qui permet de résoudre les équations diophantiennes — au programme du Bac — et qui donne sa puissance au théorème de Gauss.
Pour tous \(a, b \in \mathbb{Z}\), il existe des entiers \(u, v \in \mathbb{Z}\) tels que \(au + bv = \text{pgcd}(a, b)\). En particulier :
\[ \text{pgcd}(a, b) = 1 \iff \exists\, u, v \in \mathbb{Z},\quad au + bv = 1. \]Ce couple \((u, v)\) n'est pas unique : si \((u_0, v_0)\) est une solution, toutes les solutions sont de la forme \(\left(u_0 + \tfrac{b}{d}k,\ v_0 - \tfrac{a}{d}k\right)\) avec \(d = \text{pgcd}(a,b)\) et \(k \in \mathbb{Z}\).
Pour trouver \(u, v\) tels que \(23u + 17v = 1\), on applique d'abord l'algorithme d'Euclide (en notant chaque étape), puis on remonte en sens inverse en exprimant les restes successifs comme combinaisons de \(23\) et \(17\).
Étape 1 — Descente :
\[ \begin{aligned} 23 &= 17 \times 1 + 6 \\ 17 &= 6 \times 2 + 5 \\ 6 &= 5 \times 1 + 1 \\ 5 &= 1 \times 5 + 0 \end{aligned} \]Étape 2 — Remontée :
\[ \begin{aligned} 1 &= 6 - 5 \times 1 \\ &= 6 - (17 - 6 \times 2) \times 1 = 3 \times 6 - 17 \\ &= 3 \times (23 - 17 \times 1) - 17 = 3 \times 23 - 4 \times 17. \end{aligned} \]Donc \(23 \times 3 + 17 \times (-4) = 1\) : un couple de Bézout est \((u, v) = (3, -4)\).
Toujours vérifier le résultat en recalculant \(au + bv\) : \(23 \times 3 + 17 \times (-4) = 69 - 68 = 1\). Cela prend dix secondes et évite les erreurs de signe dans la remontée.
Si \(a \mid bc\) et \(\text{pgcd}(a, b) = 1\), alors \(a \mid c\).
Corollaire : si \(a \mid n\), \(b \mid n\) et \(\text{pgcd}(a, b) = 1\), alors \(ab \mid n\).
Une équation diophantienne est une équation de la forme \(ax + by = c\) cherchée dans \(\mathbb{Z}^2\). Elle admet des solutions si et seulement si \(\text{pgcd}(a, b) \mid c\).
Exemple. Résoudre dans \(\mathbb{Z}^{2}\) : \(5x - 3y = 1\).
Étape 1 — Existence : \(\text{pgcd}(5, 3) = 1\), qui divise \(1\) : des solutions existent.
Étape 2 — Solution particulière : par inspection (ou Euclide), \(5 \times 2 - 3 \times 3 = 10 - 9 = 1\). Donc \((x_0, y_0) = (2, 3)\).
Étape 3 — Solution générale : si \((x, y)\) est solution, alors \(5(x - 2) = 3(y - 3)\). Donc \(3 \mid 5(x-2)\) ; comme \(\text{pgcd}(3,5) = 1\), Gauss donne \(3 \mid (x - 2)\), soit \(x = 2 + 3k\) pour \(k \in \mathbb{Z}\). On substitue : \(y = \dfrac{5x - 1}{3} = \dfrac{5(2+3k)-1}{3} = \dfrac{9+15k}{3} = 3 + 5k\).
\[ \mathcal{S} = \{(2 + 3k,\ 3 + 5k),\ k \in \mathbb{Z}\} \]Application de Gauss. Sachant que \(7 \mid 3n\) et \(\text{pgcd}(7,3)=1\), on conclut par Gauss que \(7 \mid n\). Simple mais puissant.
Équation sans solution. \(6x + 4y = 3\) : \(\text{pgcd}(6, 4) = 2\) et \(2 \nmid 3\), donc cette équation n'a aucune solution entière.
Équation avec second membre non unitaire. Résoudre \(7x + 5y = 11\). Bézout donne \(7 \times 3 + 5 \times (-4) = 1\), donc en multipliant par 11 : \(7 \times 33 + 5 \times (-44) = 11\). Solution particulière \((33, -44)\). Solution générale : \(x = 33 + 5k\), \(y = -44 - 7k\), \(k \in \mathbb{Z}\).
Les théorèmes de Bézout et Gauss sont traités dans ce cours sur des exemples numériques concrets. Leurs démonstrations générales ne sont pas exigibles au Bac. L'essentiel est de maîtriser la remontée d'Euclide et la méthode de résolution des équations diophantiennes.
Nombres premiers et décomposition
Les nombres premiers sont les atomes de l'arithmétique : tout entier supérieur à \(1\) se décompose de façon unique en produit de nombres premiers. Cette décomposition éclaire d'un seul coup le PGCD, le PPCM et le nombre de diviseurs.
Un entier \(p \ge 2\) est dit premier s'il admet exactement deux diviseurs positifs : \(1\) et \(p\) lui-même. Un entier \(n \ge 2\) non premier est dit composé.
Pour tester si \(n\) est premier, il suffit de vérifier qu'aucun entier premier \(p \le \sqrt{n}\) ne divise \(n\). En effet, si \(n = ab\) avec \(a \le b\), alors \(a^2 \le ab = n\), donc \(a \le \sqrt{n}\).
Exemple. \(\sqrt{197} \approx 14{,}03\). On teste les premiers \(2, 3, 5, 7, 11, 13\) : aucun ne divise \(197\). Donc \(\mathbf{197}\) est premier.
Contre-exemple. \(221 = 13 \times 17\). \(\sqrt{221} \approx 14{,}9\), et \(13 \le 14{,}9\) divise \(221\) : \(221\) est composé.
On divise successivement par les premiers dans l'ordre croissant (\(2, 3, 5, 7, \ldots\)) jusqu'à ce que le quotient soit \(1\).
\(360 \div 2 = 180\) ; \(180 \div 2 = 90\) ; \(90 \div 2 = 45\) ; \(45 \div 3 = 15\) ; \(15 \div 3 = 5\) ; \(5 \div 5 = 1\). Donc \(360 = 2^3 \times 3^2 \times 5\).
Nombre de diviseurs positifs de \(360\) : \(\tau(360) = (3+1)(2+1)(1+1) = 4 \times 3 \times 2 = \mathbf{24}\).
Il existe une infinité de nombres premiers.
Esquisse de la démonstration d'Euclide. Supposons par l'absurde qu'il n'en existe qu'un nombre fini \(p_1, \ldots, p_k\). Considérons \(N = p_1 p_2 \cdots p_k + 1\). Alors \(N \ge 2\) admet un diviseur premier \(p\). Mais \(p\) ne peut être aucun des \(p_i\) car \(N \equiv 1\ [p_i]\) pour tout \(i\). Contradiction : l'ensemble des premiers ne peut être fini.
Tout entier \(n \ge 2\) s'écrit de façon unique (à l'ordre des facteurs près) comme produit de nombres premiers :
\[ n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_r^{\alpha_r} \qquad (p_1 < p_2 < \cdots < p_r \text{ premiers},\ \alpha_i \ge 1). \]Pour \(a = \prod p_i^{\alpha_i}\) et \(b = \prod p_i^{\beta_i}\) (en complétant par des exposants nuls si nécessaire) :
\[ \text{pgcd}(a,b) = \prod p_i^{\min(\alpha_i,\beta_i)} \qquad \text{ppcm}(a,b) = \prod p_i^{\max(\alpha_i,\beta_i)}. \]Exemple : \(360 = 2^3 \times 3^2 \times 5\) et \(126 = 2 \times 3^2 \times 7\). Alors \(\text{pgcd}(360, 126) = 2^1 \times 3^2 = 18\) et \(\text{ppcm}(360, 126) = 2^3 \times 3^2 \times 5 \times 7 = 2520\).
Crible d'Ératosthène (manuel). Pour lister les premiers jusqu'à 30 : on barre les multiples de \(2, 3, 5\) (car \(\sqrt{30} < 6\)). Il reste : \(2, 3, 5, 7, 11, 13, 17, 19, 23, 29\) — dix nombres premiers.
Nombre de diviseurs. \(n = 2^4 \times 3 \times 5^2\) a \((4+1)(1+1)(2+1) = 30\) diviseurs positifs.
Condition de divisibilité par \(p\) premier. Si \(p\) est premier et \(p \mid ab\), alors \(p \mid a\) ou \(p \mid b\) : c'est une version forte de Gauss, spécifique aux nombres premiers.
Figure interactive — Crible d'Ératosthène
Le crible filtre les nombres composés un premier à la fois. Sélectionnez un premier pour voir ses multiples barrés. Les cases restantes non barrées sont des nombres premiers.
Résumé
\(a = bq + r\) avec \(0 \le r < |b|\). Le reste est toujours positif ou nul, y compris quand \(a < 0\).
Compatibles avec \(+\), \(-\), \(\times\) et les puissances. Pour les grands exposants : chercher la période du cycle des restes. La division ne se simplifie que si \(\text{pgcd}(k, n) = 1\).
\(\text{pgcd}(a,b) = \text{pgcd}(b, r)\). Répéter jusqu'au reste nul. \(\text{pgcd} \times \text{ppcm} = |ab|\).
\(\text{pgcd}(a,b) = 1 \iff \exists\, u, v,\ au + bv = 1\). Si \(a \mid bc\) et \(\text{pgcd}(a,b)=1\), alors \(a \mid c\). Clés des équations diophantiennes.
Tester les premiers jusqu'à \(\sqrt{n}\). Décomposition unique. \(\tau(n) = \prod (\alpha_i + 1)\) diviseurs. \(\text{pgcd}\) et \(\text{ppcm}\) via \(\min\)/\(\max\) des exposants.
Sujet type Bac
On considère les entiers \(a = 357\) et \(b = 231\). Les cinq questions suivantes sont progressives : chaque résultat sert à la suivante.
Question 1 — Division euclidienne. Effectuer la division euclidienne de \(a\) par \(b\). Vérifier le résultat.
On cherche \(q\) et \(r\) tels que \(357 = 231q + r\) avec \(0 \le r < 231\). Le quotient est \(q = 1\) (car \(231 \times 1 = 231 \le 357 < 231 \times 2 = 462\)). Donc \(r = 357 - 231 = 126\).
\[357 = 231 \times 1 + 126 \quad (0 \le 126 < 231)\]Vérification : \(231 + 126 = 357\). Correct.
Question 2 — Algorithme d'Euclide. Calculer \(\text{pgcd}(357, 231)\) par l'algorithme d'Euclide. En déduire \(\text{ppcm}(357, 231)\).
On reprend le reste de la question 1 et on continue :
\[ \begin{aligned} 357 &= 231 \times 1 + 126 \\ 231 &= 126 \times 1 + 105 \\ 126 &= 105 \times 1 + 21 \\ 105 &= 21 \times 5 + 0 \end{aligned} \]Le dernier reste non nul est \(21\), donc \(\text{pgcd}(357, 231) = \mathbf{21}\).
On en déduit :
\[ \text{ppcm}(357, 231) = \frac{357 \times 231}{21} = \frac{82467}{21} = \mathbf{3927}. \]Question 3 — Identité de Bézout. Trouver des entiers \(u, v\) tels que \(357u + 231v = 21\).
Puisque \(\text{pgcd}(357, 231) = 21\), Bézout assure l'existence de \(u, v\). On remonte l'algorithme. On commence par exprimer chaque reste en fonction des précédents :
\[ \begin{aligned} 21 &= 126 - 105 \times 1 \\ &= 126 - (231 - 126) = 2 \times 126 - 231 \\ &= 2(357 - 231) - 231 = 2 \times 357 - 3 \times 231. \end{aligned} \]Donc \(357 \times 2 + 231 \times (-3) = 21\) : un couple de Bézout est \((u, v) = (2, -3)\).
Vérification : \(357 \times 2 - 231 \times 3 = 714 - 693 = 21\). Correct.
Question 4 — Équation diophantienne. Résoudre dans \(\mathbb{Z}^{2}\) l'équation \(357x + 231y = 42\).
Le membre de droite est \(42 = 2 \times 21\). Comme \(\text{pgcd}(357, 231) = 21\) divise \(42\), l'équation admet des solutions.
En multipliant par \(2\) la relation de Bézout \(357 \times 2 + 231 \times (-3) = 21\) : \(357 \times 4 + 231 \times (-6) = 42\). Une solution particulière est \((x_0, y_0) = (4, -6)\).
Solution générale : si \((x, y)\) est solution, \(357(x - 4) + 231(y + 6) = 0\), soit \(357(x-4) = -231(y+6)\). En divisant par \(\text{pgcd}(357,231) = 21\) : \(17(x-4) = -11(y+6)\). Comme \(\text{pgcd}(17, 11) = 1\), Gauss donne \(11 \mid (x-4)\), soit \(x - 4 = 11k\), d'où \(x = 4 + 11k\). Alors \(y + 6 = -17k\), soit \(y = -6 - 17k\).
\[ \mathcal{S} = \{(4 + 11k,\ -6 - 17k),\ k \in \mathbb{Z}\} \]Question 5 — Congruences et grand exposant. Calculer le reste de \(231^{50}\) dans la division par \(17\).
Étape 1 — On réduit \(231\) modulo \(17\) : \(231 = 17 \times 13 + 10\), donc \(231 \equiv 10\ [17]\). Ainsi \(231^{50} \equiv 10^{50}\ [17]\).
Étape 2 — On note que \(10 \equiv -7\ [17]\), donc \(10^{50} \equiv (-7)^{50} = 7^{50}\ [17]\) (l'exposant est pair).
Étape 3 — Cycle de \(7^k\) modulo \(17\) (le théorème de Fermat donne la période divisant \(16\)) : \(7^1 \equiv 7\), \(7^2 \equiv 49 \equiv 15 \equiv -2\), \(7^4 \equiv (-2)^2 = 4\), \(7^8 \equiv 16 \equiv -1\), \(7^{16} \equiv 1\ [17]\). La période est \(16\).
Étape 4 — Décomposition : \(50 = 16 \times 3 + 2\), donc \(7^{50} = (7^{16})^3 \times 7^2 \equiv 1^3 \times (-2) = -2 \equiv 15\ [17]\).
Conclusion : le reste de \(231^{50}\) dans la division par \(17\) est \(\mathbf{15}\).