PGCD et Arithmétique : Cours Complet Terminale Maths

Terminale spécialité maths — divisibilité, algorithme d'Euclide, Bézout, Gauss, congruences

Term

Niveau

Spé maths

Matière

Sections

2026

Programme

📚 Navigation
🏠 Hub Maths Lycée
🔢 Dénombrement
📈 Suites
💠 Complexes
📋 Formulaire maths

📋 Sommaire

1. Divisibilité dans ℤ
8. Théorème de Bézout
2. Division euclidienne
9. Théorème de Gauss
3. PGCD — définition
10. Congruences
4. Algorithme d'Euclide
11. Équations diophantiennes
5. PPCM
12. Exercices types bac
6. Nombres premiers
13. Questions fréquentes
7. Entiers premiers entre eux

Section 01

Divisibilité dans ℤ

Définition : Soient a, b ∈ ℤ avec b ≠ 0. On dit que b divise a (ou que a est un multiple de b), noté b | a, s'il existe k ∈ ℤ tel que a = k × b.

Notation	Signification	Exemple
b \| a	b divise a	3 \| 12 car 12 = 4×3
b ∤ a	b ne divise pas a	5 ∤ 13 car 13 = 2×5 + 3
a ≡ 0 [b]	a est multiple de b	18 ≡ 0 [6]

📝 Exemples

Diviseurs de 12 : ±1, ±2, ±3, ±4, ±6, ±12.
7 | 42 (car 42 = 6×7) ; 7 ∤ 43 (car 43 = 6×7 + 1).
Si 4 | a et 4 | b, alors 4 | (3a − 2b) car 3a − 2b = 3(4k) − 2(4m) = 4(3k−2m).

Section 02

Division euclidienne

Pour tout a ∈ ℤ et b ∈ ℤ* (b > 0), il existe un unique couple (q, r) tel que :
a = b × q + r avec 0 ≤ r < b

📘 Vocabulaire : a est le dividende, b le diviseur, q le quotient, r le reste.
b | a ⟺ r = 0 (le reste est nul).

📝 Exemples

127 ÷ 13 : 127 = 13 × 9 + 10. Quotient = 9, reste = 10.
−47 ÷ 7 : −47 = 7 × (−7) + 2 (car 7×(−7)=−49, et −47−(−49)=2). Quotient = −7, reste = 2.
144 ÷ 12 : 144 = 12 × 12 + 0. Reste = 0 → 12 | 144.

Section 03

PGCD — définition et propriétés

Définition : Le Plus Grand Commun Diviseur (PGCD) de deux entiers a et b (non tous deux nuls) est le plus grand entier positif qui divise à la fois a et b. On le note PGCD(a, b) ou pgcd(a, b) ou encore (a, b) en notation anglo-saxonne.

Propriété	Formule
Commutativité	PGCD(a, b) = PGCD(b, a)
PGCD avec 0	PGCD(a, 0) = \|a\|
PGCD avec 1	PGCD(a, 1) = 1
Multiples	PGCD(ka, kb) = \|k\| × PGCD(a, b)
Division euclidienne	PGCD(a, b) = PGCD(b, r) où r est le reste de a÷b
Lien PPCM	PGCD(a,b) × PPCM(a,b) = \|a × b\|

Section 04

Algorithme d'Euclide

Principe : On effectue des divisions euclidiennes successives en remplaçant (a, b) par (b, r) jusqu'à obtenir un reste nul. Le dernier reste non nul est le PGCD.

✅ Méthode :
a = b × q₁ + r₁ (0 ≤ r₁ < b)
b = r₁ × q₂ + r₂ (0 ≤ r₂ < r₁)
r₁ = r₂ × q₃ + r₃ (0 ≤ r₃ < r₂)
⋮
r_ = r_ × q_n + 0
→ PGCD(a, b) = r_ (dernier reste non nul)

📝 Exemple — PGCD(252, 105)

252 = 105 × 2 + 42
105 = 42 × 2 + 21
42 = 21 × 2 + 0

Le dernier reste non nul est 21. Donc PGCD(252, 105) = 21.

📝 Exemple — PGCD(1071, 462)

1071 = 462 × 2 + 147
462 = 147 × 3 + 21
147 = 21 × 7 + 0

PGCD(1071, 462) = 21.

Section 05

PPCM — Plus Petit Commun Multiple

Définition : Le PPCM de a et b est le plus petit entier strictement positif qui est multiple à la fois de a et de b.

PPCM(a, b) = |a × b| / PGCD(a, b)

📝 Exemples

PPCM(12, 18) : PGCD(12,18) = 6. PPCM = 12×18/6 = 216/6 = 36.

PPCM(252, 105) : PGCD = 21 (calculé ci-dessus). PPCM = 252×105/21 = 26460/21 = 1260.

Application — fractions : Pour calculer 5/12 + 7/18, le dénominateur commun est PPCM(12,18) = 36 :
5/12 + 7/18 = 15/36 + 14/36 = 29/36.

Section 06

Nombres premiers

Définition : Un entier p ≥ 2 est premier s'il a exactement deux diviseurs positifs : 1 et lui-même.

📘 Liste des premiers nombres premiers :
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, …

2 est le seul nombre premier pair. Tout entier ≥ 2 est soit premier, soit produit de nombres premiers (décomposition unique en facteurs premiers, théorème fondamental de l'arithmétique).

✅ Critère de primalité : Pour tester si n est premier, il suffit de vérifier qu'il n'est divisible par aucun premier p ≤ √n.

📝 Décomposition en facteurs premiers

360 : 360 = 8×45 = 2³×3²×5.
1764 : 1764 = 4×441 = 4×21² = 2²×3²×7² = 2²×3²×7².
PGCD via décomposition : PGCD(360, 1764) = 2²×3² = 36.
PPCM via décomposition : PPCM(360, 1764) = 2³×3²×5×7² = 8×9×5×49 = 17640.

Section 07

Entiers premiers entre eux

Définition : a et b sont premiers entre eux (ou copremiers) si PGCD(a, b) = 1. On note parfois a ∧ b = 1.

📘 Simplification de fractions : La fraction a/b est irréductible si et seulement si a et b sont premiers entre eux, c'est-à-dire PGCD(a, b) = 1.

Pour réduire a/b : diviser numérateur et dénominateur par PGCD(a, b).

📝 Exemples

252/105 : PGCD = 21 → 252/105 = 12/5. PGCD(12,5) = 1 → fraction irréductible.

PGCD(34, 15) :
34 = 15×2 + 4 | 15 = 4×3 + 3 | 4 = 3×1 + 1 | 3 = 1×3 + 0.
PGCD = 1 → 34 et 15 sont premiers entre eux.

Section 08

Théorème de Bézout

PGCD(a, b) = d ⟺ il existe u, v ∈ ℤ tels que au + bv = d

Corollaire (cas particulier important) : a et b sont premiers entre eux ⟺ il existe u, v ∈ ℤ tels que au + bv = 1.

✅ Algorithme d'Euclide étendu — méthode de remontée :
On exprime chaque reste en fonction des précédents (en remontant l'algorithme d'Euclide), jusqu'à exprimer le PGCD en fonction de a et b.

📝 Exemple — trouver u, v tels que 252u + 105v = 21

On reprend les calculs d'Euclide et on remonte :

252 = 105×2 + 42 → 42 = 252 − 105×2
105 = 42×2 + 21 → 21 = 105 − 42×2

Substitution : 21 = 105 − 42×2 = 105 − (252 − 105×2)×2 = 105 − 252×2 + 105×4 = 105×5 − 252×2.
Donc 252×(−2) + 105×5 = 21. Solution : u = −2, v = 5.

📝 Exemple — coefficient de Bézout pour PGCD(34,15) = 1

34 = 15×2 + 4 → 4 = 34 − 15×2
15 = 4×3 + 3 → 3 = 15 − 4×3
4 = 3×1 + 1 → 1 = 4 − 3×1

Remontée : 1 = 4 − 3 = 4 − (15−4×3) = 4×4 − 15 = 4×(34−15×2) − 15 = 34×4 − 15×9.
34×4 + 15×(−9) = 1. Solution : u = 4, v = −9.

Section 09

Théorème de Gauss

Si a | bc et PGCD(a, b) = 1 alors a | c

📝 Applications du théorème de Gauss

Exemple 1 : 7 | 3n et PGCD(7,3) = 1 → 7 | n.

Exemple 2 : 6 | 35k. PGCD(6,35) = 1 (car 6=2×3 et 35=5×7 → aucun facteur commun) → 6 | k.

Exemple 3 (preuve d'irrationalité) : Montrons que √2 est irrationnel.
Supposons √2 = p/q avec p, q premiers entre eux. Alors p² = 2q² → 2 | p² → 2 | p (théorème de Gauss car 2 premier).
Posons p = 2k : 4k² = 2q² → q² = 2k² → 2 | q. Contradiction avec PGCD(p,q) = 1.

Section 10

Congruences

Définition : Soit n ∈ ℕ* (le modulo). On dit que a est congru à b modulo n, noté a ≡ b [n], si n | (a − b), c'est-à-dire si a et b ont le même reste dans la division par n.

a ≡ b [n] ⟺ n | (a − b) ⟺ ∃ k ∈ ℤ : a = b + kn

✅ Propriétés des congruences :
Si a ≡ b [n] et c ≡ d [n], alors :
— a + c ≡ b + d [n]    (addition)
— a − c ≡ b − d [n]    (soustraction)
— a × c ≡ b × d [n]    (multiplication)
— aᵏ ≡ bᵏ [n] pour tout k ∈ ℕ    (puissance)

📝 Applications des congruences

Calculer le reste de 2¹⁰⁰ divisé par 7 :
2¹ ≡ 2 [7] ; 2² ≡ 4 [7] ; 2³ ≡ 8 ≡ 1 [7].
Période 3 : 2³ ≡ 1 [7]. 100 = 3×33 + 1 → 2¹⁰⁰ = (2³)³³×2¹ ≡ 1³³×2 ≡ 2 [7].

Critère de divisibilité par 9 :
10 ≡ 1 [9], donc 10ᵏ ≡ 1 [9]. Un entier est divisible par 9 si et seulement si la somme de ses chiffres est divisible par 9.

Derniers chiffres d'une puissance :
Calculer le dernier chiffre de 7⁵⁷. Travailler mod 10.
7¹≡7, 7²≡9, 7³≡3, 7⁴≡1 [10]. Période 4. 57=4×14+1 → 7⁵⁷ ≡ 7¹ ≡ 7 [10].

Section 11

Équations diophantiennes

Définition : Une équation diophantienne est une équation de la forme ax + by = c avec a, b, c ∈ ℤ, dont on cherche les solutions dans ℤ.

📘 Existence de solutions : L'équation ax + by = c admet des solutions entières ⟺ PGCD(a, b) | c.

✅ Méthode de résolution :
1. Vérifier que PGCD(a,b) | c. Si non, pas de solution.
2. Trouver une solution particulière (x₀, y₀) par l'algorithme d'Euclide étendu (Bézout).
3. La solution générale est : x = x₀ + (b/d)t, y = y₀ − (a/d)t, avec t ∈ ℤ et d = PGCD(a,b).

📝 Exemple — résoudre 34x + 15y = 1

PGCD(34,15) = 1 | 1 → solutions existent.
D'après Bézout (section 8) : 34×4 + 15×(−9) = 1.
Solution particulière : x₀ = 4, y₀ = −9.
Solution générale (d=1) : x = 4 + 15t, y = −9 − 34t, t ∈ ℤ.
Vérification : 34(4+15t) + 15(−9−34t) = 136+510t − 135 − 510t = 1 ✓.

📝 Exemple — résoudre 6x + 10y = 8

PGCD(6,10) = 2. 2 | 8 → solutions existent.
Diviser par 2 : 3x + 5y = 4.
PGCD(3,5) = 1. Bézout : 3×2 + 5×(−1) = 1 → multiplier par 4 : 3×8 + 5×(−4) = 4.
Solution particulière : x₀ = 8, y₀ = −4.
Solution générale : x = 8 + 5t, y = −4 − 3t, t ∈ ℤ.

Section 12

Exercices types bac

📝 Exercice 1 — PGCD et irréductibilité

Montrer que pour tout entier n, PGCD(2n+1, n+1) = 1.
Posons d = PGCD(2n+1, n+1). Alors d | (2n+1) et d | (n+1).
d | (2(n+1) − (2n+1)) = 2n+2−2n−1 = 1.
Donc d | 1, soit d = 1. CQFD.

📝 Exercice 2 — congruences et dernier chiffre

Déterminer le reste de 3²⁰²⁶ dans la division par 4.
3 ≡ −1 [4] → 3² ≡ 1 [4]. 2026 = 2×1013 → 3²⁰²⁶ = (3²)¹⁰¹³ ≡ 1¹⁰¹³ ≡ 1 [4].

📝 Exercice 3 — équation diophantienne avec contrainte

Résoudre 7x + 3y = 1 dans ℤ, puis trouver la solution avec x > 0 minimal.
PGCD(7,3)=1 | 1 → solutions existent.
Par Bézout : 7×1 + 3×(−2) = 7−6 = 1. Solution particulière x₀=1, y₀=−2.
Solution générale : x = 1+3t, y = −2−7t.
x > 0 minimal : t = 0 → x = 1, y = −2.

📝 Exercice 4 — application du théorème de Gauss

Sachant que PGCD(n, 6) = 1, montrer que n² ≡ 1 [12].
PGCD(n,6)=1 → PGCD(n,2)=1 et PGCD(n,3)=1 → n est impair et non multiple de 3.
n impair → n = 2k+1 → n² = 4k²+4k+1 = 4k(k+1)+1. k ou k+1 est pair → 8 | 4k(k+1) → n² ≡ 1 [8].
n non multiple de 3 → n ≡ ±1 [3] → n² ≡ 1 [3].
PGCD(8,3)=1 et 8 | (n²−1) et 3 | (n²−1) → 24 | (n²−1) → n² ≡ 1 [24], donc a fortiori n² ≡ 1 [12].

Section 13

Questions fréquentes

Pourquoi l'algorithme d'Euclide fonctionne-t-il ?

L'algorithme repose sur la propriété fondamentale : PGCD(a, b) = PGCD(b, r) où r est le reste de la division de a par b. Preuve : tout diviseur commun de a et b divise aussi r = a − bq, donc divise b et r. Réciproquement, tout diviseur commun de b et r divise a = bq + r. Les ensembles des diviseurs communs de (a,b) et (b,r) sont identiques, donc leurs PGCD sont égaux. En répétant, les restes forment une suite strictement décroissante d'entiers positifs, qui atteint forcément 0.

Quelle différence entre le théorème de Bézout et le théorème de Gauss ?

Ce sont deux outils complémentaires. Bézout dit : « si PGCD(a,b) = d, il existe une combinaison linéaire au + bv = d » — c'est un outil de construction (trouver des coefficients entiers). Gauss dit : « si a divise bc et est premier avec b, alors a divise c » — c'est un outil de transfert de divisibilité. En pratique, Bézout est utilisé pour résoudre des équations diophantiennes, Gauss pour faire des raisonnements par l'absurde ou démontrer des propriétés de divisibilité.

Comment trouver rapidement PGCD(a, b) quand les nombres sont petits ?

Pour des petits nombres (inférieurs à 100), la méthode la plus rapide est souvent la décomposition en facteurs premiers : PGCD(a,b) = produit des facteurs premiers communs avec les exposants minimaux. Par exemple, PGCD(48, 36) : 48 = 2⁴×3 et 36 = 2²×3² → PGCD = 2²×3 = 12. Pour des grands nombres, l'algorithme d'Euclide est plus efficace car évite la factorisation (qui peut être très longue pour les grands entiers).

Comment résoudre une équation diophantienne si le membre de droite n'est pas le PGCD ?

Si ax + by = c avec c ≠ PGCD(a,b) = d, on vérifie d'abord que d | c (condition nécessaire et suffisante d'existence). Si oui, on divise toute l'équation par d pour obtenir (a/d)x + (b/d)y = c/d, avec maintenant PGCD(a/d, b/d) = 1. On trouve une solution particulière via Bézout sur a/d et b/d, puis on multiplie par c/d. La solution générale suit : x = x₀ + (b/d)t, y = y₀ − (a/d)t pour t ∈ ℤ.

Comment utiliser les congruences pour montrer qu'un nombre n'est pas un carré parfait ?

Les carrés parfaits ont des restes très contraints modulo certains entiers. Modulo 4 : tout carré est ≡ 0 ou 1 [4] (car 0²≡0, 1²≡1, 2²≡0, 3²≡1). Donc si n ≡ 2 ou 3 [4], n n'est pas un carré parfait. Modulo 3 : tout carré est ≡ 0 ou 1 [3]. Modulo 8 : tout carré impair est ≡ 1 [8]. Exemple : 2026 = 4×506 + 2 → 2026 ≡ 2 [4] → 2026 n'est pas un carré parfait.

📚 Autres cours de maths lycée

🏠 Hub Maths Lycée
🔢 Dénombrement
💠 Complexes
📈 Suites
🎯 Probabilités
📊 Loi normale
📋 Formulaire maths lycée
🏫 Hub Lycée

📱 Bientôt : Révisez PGCD, Bézout et les congruences en mode flashcard avec l'application cours-et-fiches !