Divisibilité et congruences en L1 de maths : exercices corrigés

---

---

Pour démarrer

Exercice 1 – Divisions euclidiennes de 2026 et de son opposé

1. Effectuer la division euclidienne de 2026 par 17, puis celle de \(-2026\) par 17.
2. Expliquer comment passer directement du reste de 2026 à celui de \(-2026\).
3. Un entier \(a\) a pour reste 3 dans la division par 17. Déterminer les restes de \(a^2\), de \(a^3\) et de \(5a + 20\) dans la division par 17.

Exercice 2 – Euclide étendu sur 2431 et 1001

1. Calculer \(2431 \wedge 1001\) par l’algorithme d’Euclide.
2. En remontant l’algorithme, trouver deux entiers \(u, v\) tels que \(2431u + 1001v = 2431 \wedge 1001\). Vérifier le résultat.
3. Décomposer 2431 et 1001 en facteurs premiers et retrouver le PGCD.

Exercice 3 – PGCD d’expressions dépendant de n

Soit \(n \in \mathbf{Z}\).

1. Montrer que \(5n + 3\) et \(3n + 2\) sont premiers entre eux.
2. Ensuite, établir que \((2n + 1) \wedge (n + 3)\) vaut 1 ou 5.
3. Enfin, pour quels entiers \(n\) ce PGCD vaut-il 5 ?

Exercice 4 – Restes de grandes puissances

1. Déterminer le chiffre des unités de \(7^{2026}\).
2. De même, quel est le reste de \(6^{100}\) dans la division par 13 ?
3. Enfin, montrer que, pour tout \(n \in \mathbf{N}\), le nombre \(4^n – 1\) est divisible par 3.

Exercice 5 – PGCD et PPCM par les facteurs premiers

1. Décomposer 5040 et 1386 en produits de facteurs premiers.
2. En déduire \(5040 \wedge 1386\) et \(5040 \vee 1386\), puis vérifier la relation entre PGCD, PPCM et produit.
3. Combien 5040 possède-t-il de diviseurs positifs ? Justifier la méthode de dénombrement.

Exercice 6 – Vrai ou faux sur la divisibilité

Pour chaque affirmation, où \(a, b, c\) sont des entiers et \(n \geqslant 2\), donner une preuve ou un contre-exemple.

1. Si \(a \mid bc\), alors \(a \mid b\) ou \(a \mid c\).
2. Lorsque \(a \equiv b \pmod{n}\), on a aussi \(a^2 \equiv b^2 \pmod{n}\).
3. Si \(a^2 \equiv b^2 \pmod{n}\), alors \(a \equiv b\) ou \(a \equiv -b \pmod{n}\).
4. Enfin, \(ac \equiv bc \pmod{n}\) avec \(c \not\equiv 0 \pmod{n}\) entraîne \(a \equiv b \pmod{n}\).

Pour s’entraîner

Exercice 7 – Une équation diophantienne à simplifier

1. Existe-t-il des entiers \(x, y\) avec \(51x + 33y = 10\) ? Même question avec 12 au second membre.
2. Montrer que la seconde équation équivaut à \(17x + 11y = 4\). Trouver une relation de Bézout entre 17 et 11.
3. Déterminer ensuite toutes les solutions entières de \(17x + 11y = 4\).
4. Pour finir, lister les solutions telles que \(0 \leqslant x \leqslant 50\).

Exercice 8 – Affranchir une lettre avec deux timbres

On dispose de timbres à 7 centimes et de timbres à 12 centimes en quantité illimitée. On veut affranchir une lettre pour exactement 2 euros, soit 200 centimes. On note \(x\) et \(y\) les nombres de timbres de chaque sorte.

1. Traduire le problème par une équation. Vérifier que \(7 \times (-5) + 12 \times 3 = 1\).
2. Ensuite, déterminer toutes les solutions entières, positives ou non, de l’équation.
3. Par conséquent, de combien de façons peut-on affranchir la lettre ?

Exercice 9 – Entiers premiers entre eux et produits

Soit \(a, b, c\) des entiers.

1. On suppose \(a \wedge b = 1\) et \(a \wedge c = 1\). En multipliant deux relations de Bézout, montrer que \(a \wedge bc = 1\).
2. En déduire que si \(a \wedge b = 1\), alors \(a^m \wedge b^k = 1\) pour tous \(m, k \in \mathbf{N}^{*}\).
3. Par ailleurs, montrer que \((a + kb) \wedge b = a \wedge b\) pour tout \(k \in \mathbf{Z}\).
4. Enfin, prouver que \(n(n+1)(n+2)\) est divisible par 6 pour tout entier \(n\), en utilisant le corollaire du lemme de Gauss.

Exercice 10 – Une infinité de premiers congrus à 3 modulo 4

1. Montrer qu’un produit d’entiers tous congrus à 1 modulo 4 est congru à 1 modulo 4.
2. Soit \(N \geqslant 3\) un entier congru à 3 modulo 4. Montrer que \(N\) admet un diviseur premier congru à 3 modulo 4.
3. Raisonner par l’absurde : si \(p_1, \dots, p_k\) étaient les seuls premiers de reste 3 modulo 4, étudier \(N = 4 p_1 \cdots p_k – 1\) et aboutir ainsi à une contradiction.

Exercice 11 – Inverse de 37 modulo 101 et système de congruences

1. Justifier que 37 est inversible modulo 101, puis calculer un inverse par l’algorithme d’Euclide étendu.
2. En déduire les solutions de \(37x \equiv 5 \pmod{101}\).
3. Déterminer les entiers \(x\) tels que \(x \equiv 3 \pmod{8}\) et \(x \equiv 5 \pmod{9}\). Montrer que l’ensemble des solutions est une classe modulo 72.

Exercice 12 – Un multiple de 2730 pour tout entier n

1. Décomposer 2730 en facteurs premiers.
2. Soit \(p\) un nombre premier tel que \(p – 1\) divise 12. Montrer que \(n^{13} \equiv n \pmod{p}\) pour tout entier \(n\).
3. En déduire que \(n^{13} – n\) est divisible par 2730 pour tout \(n \in \mathbf{Z}\).

Exercice 13 – Tester à la main la division par 9 et par 11

Un entier naturel s’écrit en base 10 sous la forme \(N = \sum_{k=0}^{m} c_k 10^k\), avec des chiffres \(c_k \in \{0, \dots, 9\}\).

1. Montrer que \(N\) est congru modulo 9 à la somme de ses chiffres.
2. De même, établir que \(N \equiv \sum_{k=0}^{m} (-1)^k c_k \pmod{11}\).
3. Application : déterminer les restes de \(2\,026\,189\) dans les divisions par 9 et par 11.
4. Trouver le chiffre \(x\) pour lequel le nombre de chiffres successifs 3, 1, \(x\), 5, 2 est divisible par 11.

Exercice 14 – Sommes de carrés et restes modulo 4 et 8

Le diagramme donne le reste de \(n^2\) modulo 8 pour les premiers entiers.

1. Déterminer les restes possibles d’un carré modulo 4. Peut-on écrire 2027 sous la forme \(x^2 + y^2\) avec \(x, y\) entiers ?
2. Ensuite, montrer qu’un carré est congru à 0, 1 ou 4 modulo 8.
3. En déduire qu’aucun entier congru à 7 modulo 8 n’est somme de trois carrés. Donner un exemple supérieur à 2000.

Exercice 15 – Nombres de Mersenne et exposant premier

Pour \(n \geqslant 2\), on pose \(M_n = 2^n – 1\).

1. Pour \(x \in \mathbf{Z}\) et \(a, b \in \mathbf{N}^{*}\), factoriser \(x^{ab} – 1\) par \(x^a – 1\).
2. Prouver qu’un exposant composé donne un nombre \(M_n\) composé. Que peut-on dire de \(n\) quand \(M_n\) est premier ?
3. Un exposant premier suffit-il à rendre \(M_n\) premier ? Tester la divisibilité de \(M_{11}\) par 23.

Pour approfondir

Exercice 16 – PGCD de deux nombres de Mersenne

Soit \(m, n \in \mathbf{N}^{*}\) et \(M_k = 2^k – 1\).

1. Écrire la division euclidienne \(m = nq + r\). Montrer que \(M_m \equiv M_r \pmod{M_n}\).
2. En déduire \(M_m \wedge M_n = M_n \wedge M_r\), puis \(M_m \wedge M_n = M_{m \wedge n}\), avec la convention \(M_0 = 0\).
3. Par exemple, calculer \((2^{36} – 1) \wedge (2^{24} – 1)\).
4. À quelle condition \(M_m\) et \(M_n\) sont-ils premiers entre eux ?

Exercice 17 – Le théorème de Wilson

Soit \(p\) un nombre premier impair.

1. Montrer que \(x^2 \equiv 1 \pmod{p}\) si et seulement si \(x \equiv 1\) ou \(x \equiv -1 \pmod{p}\).
2. Ensuite, prouver que chaque \(a \in \{2, \dots, p – 2\}\) a un unique inverse modulo \(p\) dans \(\{2, \dots, p – 2\}\), distinct de \(a\).
3. En regroupant les facteurs par paires, montrer que \((p – 1)! \equiv -1 \pmod{p}\). Vérifier aussi le cas \(p = 2\).
4. Réciproquement, soit \(n \geqslant 2\) tel que \((n – 1)! \equiv -1 \pmod{n}\). Montrer que \(n\) est premier.

Exercice 18 – Zéros terminaux de 2026 factorielle

Soit \(p\) premier. Pour \(N \geqslant 1\), l’entier \(v_p(N)\) désigne la plus grande puissance \(j\) telle que \(p^j \mid N\). La partie entière de \(x\) est notée \(\lfloor x \rfloor\).

1. Soit \(k \geqslant 1\). Combien d’entiers de \(\{1, \dots, n\}\) sont divisibles par \(p^k\) ? Justifier que la réponse est \(\lfloor n / p^k \rfloor\).
2. En déduire la formule de Legendre : \(v_p(n!) = \sum_{k \geqslant 1} \lfloor n / p^k \rfloor\), la somme étant finie.
3. Calculer \(v_5(2026!)\) et \(v_2(2026!)\).
4. Par combien de zéros se termine \(2026!\) écrit en base dix ?

Exercice 19 – Problème sur un chiffrement RSA miniature

On prend \(p = 11\), \(q = 17\), \(n = pq = 187\) et \(e = 7\). Un message est un entier \(m\) avec \(0 \leqslant m < n\). On le chiffre en \(c\), reste de \(m^e\) modulo \(n\).

1. Calculer \(\varphi = (p – 1)(q – 1)\) et vérifier que \(e \wedge \varphi = 1\).
2. Trouver l’entier \(d\), avec \(0 < d < \varphi\), tel que \(ed \equiv 1 \pmod{\varphi}\).
3. Chiffrer le message \(m = 5\), en calculant par carrés successifs modulo 187.
4. Soit \(m\) un entier quelconque. Montrer que \(m^{ed} \equiv m \pmod{p}\), en distinguant selon que \(p\) divise \(m\) ou non. Faire de même modulo \(q\).
5. En déduire que \(m^{ed} \equiv m \pmod{n}\). Expliquer pourquoi \(d\) permet de déchiffrer.
6. Vérifier le déchiffrement du message obtenu à la question 3, en calculant \(c^{d}\) modulo 11 puis modulo 17.

Pour aller plus loin

Télécharger puis imprimer cette fiche en PDF.

Télécharger ou imprimer cette fiche «divisibilité et congruences en L1 de maths : exercices corrigés» au format PDF afin de pouvoir travailler en totale autonomie.

---

OK

 Maths PDF c'est 16 224 780 cours et exercices de maths téléchargés en PDF et 4 250 exercices.