Fiche d'exercices Logimaths | Terminale maths expertes
Fiche d'exercices : PGCD et nombres premiers
8 exercices progressifs ⭐ → ⭐⭐⭐ : cherche d'abord, la correction est sous chaque énoncé
Échauffement
Exercice 1 : Algorithme d'Euclide⭐
- Calcule PGCD(462 ; 546) par l'algorithme d'Euclide.
- Déduis-en la forme irréductible de la fraction \dfrac{462}{546}.
👆 ▶ Correction de l'exercice 1
1. 546 = 462 × 1 + 84 ; 462 = 84 × 5 + 42 ; 84 = 42 × 2 + 0 : PGCD = 42.
2. \begin{aligned}\dfrac{462}{546} &= \dfrac{42 \times 11}{42 \times 13} \\ &= \dfrac{11}{13}\end{aligned}
2. \begin{aligned}\dfrac{462}{546} &= \dfrac{42 \times 11}{42 \times 13} \\ &= \dfrac{11}{13}\end{aligned}
Exercice 2 : Premiers entre eux⭐
- 35 et 48 sont-ils premiers entre eux ?
- Montre que deux entiers consécutifs n et n + 1 sont toujours premiers entre eux.
👆 ▶ Correction de l'exercice 2
1. 35 = 5 × 7 et 48 = 2⁴ × 3 : aucun facteur commun, oui.
2. Un diviseur commun d divise leur différence (n + 1) − n = 1 : d = 1. (C'est aussi une identité de Bézout : (n + 1) × 1 + n × (−1) = 1.)
2. Un diviseur commun d divise leur différence (n + 1) − n = 1 : d = 1. (C'est aussi une identité de Bézout : (n + 1) × 1 + n × (−1) = 1.)
Le cœur du chapitre
Exercice 3 : Bézout en pratique⭐⭐
- Vérifie que 17 et 12 sont premiers entre eux avec l'algorithme d'Euclide.
- En remontant les divisions, trouve des entiers u et v tels que {17u + 12v = 1}.
👆 ▶ Correction de l'exercice 3
1. 17 = 12 × 1 + 5 ; 12 = 5 × 2 + 2 ; 5 = 2 × 2 + 1 ; 2 = 1 × 2 + 0 : PGCD = 1 ✔.
2. On remonte : 1 = 5 − 2 × 2 = 5 − 2(12 − 5 × 2) = 5 × 5 − 2 × 12 = 5(17 − 12) − 2 × 12 = 5 × 17 − 7 × 12 : u = 5, v = −7 (vérification : 85 − 84 = 1 ✔).
2. On remonte : 1 = 5 − 2 × 2 = 5 − 2(12 − 5 × 2) = 5 × 5 − 2 × 12 = 5(17 − 12) − 2 × 12 = 5 × 17 − 7 × 12 : u = 5, v = −7 (vérification : 85 − 84 = 1 ✔).
Exercice 4 : Le théorème de Gauss⭐⭐
- 7 divise 3n. Que peut-on en déduire pour n ? Justifie.
- Un entier n est divisible par 4 et par 9. Montre qu'il est divisible par 36.
- Pourquoi « 6 divise 4 × 9 » ne permet-il PAS de dire que 6 divise 4 ou que 6 divise 9 ?
👆 ▶ Correction de l'exercice 4
1. 7 est premier avec 3 (7 est premier et ne divise pas 3) : par Gauss, 7 divise n.
2. 4 et 9 sont premiers entre eux : leur produit 36 divise n (corollaire de Gauss).
3. 6 n'est premier ni avec 4 ni avec 9 : l'hypothèse de Gauss tombe, et le contre-exemple le confirme (6 | 36 mais 6 ∤ 4 et 6 ∤ 9).
2. 4 et 9 sont premiers entre eux : leur produit 36 divise n (corollaire de Gauss).
3. 6 n'est premier ni avec 4 ni avec 9 : l'hypothèse de Gauss tombe, et le contre-exemple le confirme (6 | 36 mais 6 ∤ 4 et 6 ∤ 9).
Exercice 5 : Tests de primalité⭐⭐
- 139 est-il premier ? (quels diviseurs suffit-il de tester ?)
- 221 est-il premier ?
👆 ▶ Correction de l'exercice 5
1. \sqrt{139} < 12 : on teste 2, 3, 5, 7, 11 : aucun ne divise 139 : premier.
2. \sqrt{221} < 15 : on teste 2, 3, 5, 7, 11, 13… et 221 = 13 × 17 : composé (le piège des « presque premiers »).
2. \sqrt{221} < 15 : on teste 2, 3, 5, 7, 11, 13… et 221 = 13 × 17 : composé (le piège des « presque premiers »).
Exercice 6 : Décomposition et diviseurs⭐⭐
- Décompose 504 en facteurs premiers.
- Combien 504 a-t-il de diviseurs positifs ?
- Calcule PGCD(504 ; 300) à partir des décompositions (300 = 2^2 \times 3 \times 5^2).
👆 ▶ Correction de l'exercice 6
1. 504 = 2^3 \times 3^2 \times 7.
2. (3 + 1)(2 + 1)(1 + 1) = 24 diviseurs.
3. Facteurs communs avec les plus petits exposants : 2^2 \times 3 = 12.
2. (3 + 1)(2 + 1)(1 + 1) = 24 diviseurs.
3. Facteurs communs avec les plus petits exposants : 2^2 \times 3 = 12.
Pour aller plus loin
Exercice 7 : Équation diophantienne complète⭐⭐⭐
On veut résoudre dans ℤ² l'équation 5x - 3y = 1.
- Justifie l'existence de solutions et donne la solution particulière (2 ; 3).
- Montre que toute solution vérifie 5(x - 2) = 3(y - 3) et conclus avec Gauss.
👆 ▶ Correction de l'exercice 7
1. PGCD(5 ; 3) = 1 divise 1 : solutions existent. 5 × 2 − 3 × 3 = 10 − 9 = 1 ✔.
2. En soustrayant 5 × 2 − 3 × 3 = 1 : 5(x − 2) = 3(y − 3). 3 divise 5(x − 2) et 3 est premier avec 5 : par Gauss, 3 divise x − 2, soit x = 2 + 3k. En reportant : y = 3 + 5k.
Solutions : {(x\,;\,y) = (2 + 3k\,;\,3 + 5k),\ k \in \mathbb{Z}}.
2. En soustrayant 5 × 2 − 3 × 3 = 1 : 5(x − 2) = 3(y − 3). 3 divise 5(x − 2) et 3 est premier avec 5 : par Gauss, 3 divise x − 2, soit x = 2 + 3k. En reportant : y = 3 + 5k.
Solutions : {(x\,;\,y) = (2 + 3k\,;\,3 + 5k),\ k \in \mathbb{Z}}.
Exercice 8 : Synthèse type bac : Fermat au travail⭐⭐⭐
- Énonce le petit théorème de Fermat, puis justifie que {2^{12} \equiv 1 \;[13]}.
- Déduis-en le reste de 2^{2026} modulo 13 (2026 = 12 × 168 + 10, et 2^{10} = 1024).
- Le nombre 2^{2026} + 3 est-il divisible par 13 ?
👆 ▶ Correction de l'exercice 8
1. Si p est premier et ne divise pas a, alors a^{p-1} \equiv 1 \;[p]. Ici p = 13, a = 2 : {2^{12} \equiv 1 \;[13]}.
2. \begin{aligned}2^{2026} &= (2^{12})^{168} \times 2^{10} \\ &\equiv 2^{10} \;[13]\end{aligned} et 1024 = 13 \times 78 + 10 : reste 10.
3. \begin{aligned}2^{2026} + 3 &\equiv 10 + 3 \\ &= 13 \\ &\equiv 0 \;[13]\end{aligned} : oui, divisible par 13.
2. \begin{aligned}2^{2026} &= (2^{12})^{168} \times 2^{10} \\ &\equiv 2^{10} \;[13]\end{aligned} et 1024 = 13 \times 78 + 10 : reste 10.
3. \begin{aligned}2^{2026} + 3 &\equiv 10 + 3 \\ &= 13 \\ &\equiv 0 \;[13]\end{aligned} : oui, divisible par 13.