PGCD, Bézout et nombres premiers en maths sup (MPSI) : exercices corrigés

---

---

Pour démarrer

Exercice 1 – Division euclidienne avec un dividende négatif

1. Effectuer la division euclidienne de \(1000\) par \(37\), puis celle de \(-217\) par \(15\).
2. Soit \(n \in \mathbb{N}\). Écrire \(n^2 + 5 = (n + 2)(n – 2) + 9\). Pour quelles valeurs de \(n\) cette égalité est-elle la division euclidienne de \(n^2 + 5\) par \(n + 2\) ?
3. Ensuite, donner le reste de la division de \(n^2 + 5\) par \(n + 2\) lorsque \(n = 3\).

Exercice 2 – Algorithme d’Euclide pour 3289 et 2717

1. Calculer \(3289 \wedge 2717\) par l’algorithme d’Euclide.
2. En déduire la forme irréductible de la fraction \(\dfrac{2717}{3289}\).
3. Enfin, calculer \(3289 \vee 2717\).

Exercice 3 – Coefficients de Bézout pour 97 et 35

1. Justifier que \(97\) et \(35\) sont premiers entre eux.
2. À l’aide de l’algorithme d’Euclide étendu, trouver des entiers \(u\) et \(v\) tels que \(97u + 35v = 1\).
3. Ensuite, en déduire un inverse de \(35\) modulo \(97\), choisi dans \(\{0, \ldots, 96\}\).
4. Enfin, déterminer tous les couples \((u, v) \in \mathbb{Z}^2\) tels que \(97u + 35v = 1\).

Exercice 4 – Diviseurs de 7560 et valuations

1. Écrire la décomposition primaire de \(7560\) et celle de \(4410\).
2. Dénombrer les diviseurs positifs de \(7560\).
3. Calculer \(7560 \wedge 4410\) et \(7560 \vee 4410\) à l’aide des valuations, puis vérifier la relation entre PGCD, PPCM et produit.

Exercice 5 – Inverse de 17 modulo 60

1. Montrer que \(17\) est inversible modulo \(60\) et déterminer son inverse dans \(\{0, \ldots, 59\}\).
2. Ensuite, résoudre la congruence \(17x \equiv 5\;[60]\).

Exercice 6 – Restes de puissances modulo 13

La figure montre les restes de \(5^k\) modulo \(13\) pour \(k\) allant de \(0\) à \(12\).

1. Justifier, sans la figure, que \(5^{12} \equiv 1\;[13]\).
2. Calculer le reste de \(5^{2026}\) dans la division par \(13\), puis montrer que \(13\) divise \(5^{2026} + 1\).
3. De même, déterminer le reste de \(3^{100}\) modulo \(13\).

Exercice 7 – Entiers premiers entre eux par Bézout

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

1. Trouver une combinaison entière de \(2n + 1\) et \(3n + 2\) égale à \(\pm 1\). En déduire que la fraction \(\dfrac{2n + 1}{3n + 2}\) est irréductible.
2. Ensuite, montrer que \(n^2 + n + 1\) et \(n + 1\) sont premiers entre eux.

Exercice 8 – Nombres premiers entre 100 et 130

1. Expliquer pourquoi, pour tester la primalité d’un entier \(n \leqslant 130\), il suffit d’essayer les diviseurs premiers \(2\), \(3\), \(5\), \(7\) et \(11\).
2. En déduire la liste des nombres premiers compris entre \(100\) et \(130\).
3. Enfin, décomposer \(1001\) en facteurs premiers.

Pour s’entraîner

Exercice 9 – Équation diophantienne 39x + 24y = 15

1. Résoudre dans \(\mathbb{Z}^2\) l’équation \(39x + 24y = 15\).
2. L’équation \(39x + 24y = 20\) a-t-elle des solutions entières ?

Exercice 10 – Stylos à 7 euros et cahiers à 11 euros

Une association achète des stylos à \(7\) euros et des cahiers à \(11\) euros. Elle dépense exactement \(200\) euros. La figure représente la droite d’équation \(7x + 11y = 200\) dans le quart de plan \(x \geqslant 0\), \(y \geqslant 0\).

1. Déterminer un inverse de \(7\) modulo \(11\).
2. Montrer que si \((x, y)\) est solution, alors \(x \equiv 5\;[11]\).
3. En déduire toutes les façons de dépenser exactement \(200\) euros.

Exercice 11 – Quand n + 3 divise n² + 10

1. Pour \(n \in \mathbb{Z}\), effectuer la division de \(n^2 + 10\) par \(n + 3\) sous la forme \(n^2 + 10 = (n + 3)Q(n) + R\), avec \(R\) entier.
2. En déduire tous les entiers \(n \neq -3\) tels que \(n + 3\) divise \(n^2 + 10\).

Exercice 12 – Racines rationnelles d’un polynôme à coefficients entiers

On considère \(P(x) = 6x^3 – 5x^2 – 2x + 1\). Soit \(r = p/q\) une racine rationnelle de \(P\), écrite sous forme irréductible avec \(q \geqslant 1\).

1. Montrer que \(p\) divise \(1\) et que \(q\) divise \(6\), en utilisant le lemme de Gauss.
2. Ensuite, dresser la liste des racines rationnelles possibles.
3. Enfin, déterminer toutes les racines de \(P\) et factoriser \(P\).

Exercice 13 – PGCD égal à 12 et PPCM égal à 360

1. Soient \(a\) et \(b\) deux entiers tels que \(0 < a \leqslant b\). Montrer que \(a \wedge b = 12\) et \(a \vee b = 360\) si et seulement si \(a = 12\alpha \), \(b = 12\beta \) avec \(\alpha \beta = 30\) et \(\alpha \wedge \beta = 1\).
2. En déduire tous les couples \((a, b)\) qui conviennent.

Exercice 14 – Zéros terminaux de 250!

1. Rappeler la formule donnant \(v_p(n!)\) et justifier pourquoi chaque entier \(k \leqslant n\) y est compté \(v_p(k)\) fois.
2. Calculer \(v_2(250!)\), \(v_3(250!)\) et \(v_5(250!)\).
3. Déterminer le nombre de chiffres \(0\) qui terminent l’écriture en base dix de \(250!\).
4. Enfin, déterminer le plus grand entier \(k\) tel que \(6^k\) divise \(250!\).

Exercice 15 – Produit de deux entiers premiers entre eux qui est un carré

Dans cet exercice, \(a\) et \(b\) désignent des entiers strictement positifs.

1. Montrer, à l’aide des valuations, que si \(a^2\) divise \(b^2\), alors \(a\) divise \(b\).
2. On suppose \(a \wedge b = 1\) et \(ab\) carré parfait. Montrer que \(a\) et \(b\) sont des carrés parfaits.
3. Déterminer les entiers \(n \in \mathbb{N}\) tels que \(n(n + 1)\) soit un carré parfait.

Exercice 16 – Congruences linéaires modulo 35

1. Résoudre la congruence \(8x \equiv 6\;[35]\).
2. Ensuite, résoudre \(21x \equiv 14\;[35]\).
3. Enfin, montrer que \(21x \equiv 10\;[35]\) n’a aucune solution.

Exercice 17 – Divisibilité de n⁷ − n par 42

1. Montrer que pour tout \(n \in \mathbb{Z}\), \(n^7 \equiv n\;[7]\).
2. Établir ensuite que \(n^7 \equiv n\;[3]\) et \(n^7 \equiv n\;[2]\).
3. En déduire que \(42\) divise \(n^7 – n\) pour tout entier \(n\).

Exercice 18 – Relation de Bézout pour trois entiers

1. Calculer \(d = 84 \wedge 140 \wedge 210\).
2. Déterminer des entiers \(u\), \(v\), \(w\) tels que \(84u + 140v + 210w = d\).
3. Les entiers \(84/d\), \(140/d\) et \(210/d\) sont-ils premiers entre eux deux à deux ?

Pour approfondir

Exercice 19 – PGCD de 2^a − 1 et 2^b − 1

Soient \(a\) et \(b\) deux entiers naturels non nuls, et \(a = bq + r\) la division euclidienne de \(a\) par \(b\).

1. Montrer que \(2^b – 1\) divise \(2^{bq} – 1\).
2. Vérifier que \(2^a – 1 = 2^r(2^{bq} – 1) + (2^r – 1)\), puis en déduire que \((2^a – 1) \wedge (2^b – 1) = (2^b – 1) \wedge (2^r – 1)\).
3. Démontrer que \((2^a – 1) \wedge (2^b – 1) = 2^{a \wedge b} – 1\).
4. Calculer \((2^{84} – 1) \wedge (2^{60} – 1)\).
5. Enfin, montrer que si \(2^n – 1\) est premier, alors \(n\) est premier.

Exercice 20 – Problème : une infinité de premiers congrus à 5 modulo 6

1. Montrer que tout nombre premier \(p \geqslant 5\) vérifie \(p \equiv 1\;[6]\) ou \(p \equiv 5\;[6]\).
2. Montrer qu’un produit d’entiers tous congrus à \(1\) modulo \(6\) est encore congru à \(1\) modulo \(6\).
3. On suppose qu’il n’existe qu’un nombre fini de premiers congrus à \(5\) modulo \(6\), notés \(p_1, \ldots, p_r\). On pose \(N = 6p_1 \cdots p_r – 1\). Montrer que \(N\) n’est divisible ni par \(2\), ni par \(3\), ni par aucun des \(p_i\).
4. En étudiant les facteurs premiers de \(N\), aboutir à une contradiction et conclure.
5. Pourquoi la même méthode ne s’applique-t-elle pas directement aux premiers congrus à \(1\) modulo \(6\) ?

Exercice 21 – Problème : un chiffrement par puissances modulo 55

On code un message par un entier \(m \in \{0, \ldots, 54\}\). Le chiffré est le reste \(c\) de \(m^3\) modulo \(55\). Le destinataire calcule ensuite le reste de \(c^{27}\) modulo \(55\).

1. Décomposer \(55\) en facteurs premiers et vérifier que \(3 \times 27 – 1\) est un multiple de \(4\) et de \(10\).
2. Montrer que pour tout entier \(m\), \(m^{81} \equiv m\;[5]\), en distinguant selon que \(5\) divise \(m\) ou non.
3. Montrer de même que \(m^{81} \equiv m\;[11]\), puis en déduire que \(55\) divise \(m^{81} – m\).
4. Expliquer pourquoi le destinataire retrouve toujours le message \(m\).
5. Chiffrer le message \(m = 7\), puis vérifier le déchiffrement par exponentiation rapide, en calculant successivement \(13^2\), \(13^4\), \(13^8\) et \(13^{16}\) modulo \(55\).

Pour aller plus loin

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

Télécharger ou imprimer cette fiche «pGCD, Bézout et nombres premiers en maths sup (MPSI) : exercices corrigés» au format PDF afin de pouvoir travailler en totale autonomie.

---

OK

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