Méthodologie Complète - TD d'Arithmétique

Université de Poitiers - L2 Informatique

Table des matières

1. Décomposition en facteurs premiers

2. Calcul du PGCD

3. Reconstruction à partir de l'algorithme d'Euclide

4. Trouver des couples (a,b) connaissant PGCD et PPCM

5. Diviseurs communs à plusieurs nombres

6. Problèmes de congruence (restes)

7. Démonstrations de divisibilité

8. Nombres premiers entre eux - Propriétés

9. Contre-exemples en arithmétique

10. Propriétés structurelles des diviseurs

11. Carrés parfaits et nombres premiers entre eux

12. Divisibilité de puissances

13. Relations entre PGCD

14. PGCD de puissances

15. PGCD de produits

16. Formules avec PGCD et PPCM

1. Décomposition en facteurs premiers

Exercices concernés : 1

Rappel théorique
Tout entier naturel n ≥ 2 s'écrit de manière unique comme produit de nombres premiers :
n = p₁^α₁ × p₂^α₂ × ... × pₖ^αₖ

Méthodologie détaillée
Étape 1 : Commencer par les petits nombres premiers
 Tester d'abord 2 (si le nombre est pair)

Puis 3, 5, 7, 11, 13, 17, 19, 23, 29, 31...

Diviser autant de fois que possible par chaque nombre premier

Étape 2 : Critères de divisibilité rapides

Par 2 : dernier chiffre pair

Par 3 : somme des chiffres divisible par 3

Par 5 : dernier chiffre 0 ou 5

Par 9 : somme des chiffres divisible par 9

Par 11 : différence entre somme des chiffres de rang pair et impair divisible par 11

Étape 3 : S'arrêter quand

Le quotient devient 1

Ou quand on arrive à un nombre premier

Étape 4 : Écrire la décomposition

Regrouper les facteurs identiques en puissances

Écrire dans l'ordre croissant

⚠️ Pièges à éviter
Ne pas oublier de diviser complètement par chaque facteur premier

Ne pas confondre 1 (qui n'est pas premier) avec les nombres premiers

Vérifier que tous les facteurs trouvés sont bien premiers

Ne pas s'arrêter trop tôt (vérifier que le quotient final est bien premier)

Exercice corrigé : Décomposer 2310

Ligne par ligne :
 Étape 1 : Test de 2
2310 est pair (dernier chiffre 0)
2310 ÷ 2 = 1155
→ On a un facteur 2

Étape 2 : Test de 2 sur 1155

1155 est impair (dernier chiffre 5)
→ On passe au nombre premier suivant

Étape 3 : Test de 3 sur 1155

Somme des chiffres : 1 + 1 + 5 + 5 = 12
12 est divisible par 3
1155 ÷ 3 = 385
→ On a un facteur 3

Étape 4 : Test de 3 sur 385

Somme des chiffres : 3 + 8 + 5 = 16
16 n'est pas divisible par 3
→ On passe au nombre premier suivant

Étape 5 : Test de 5 sur 385

385 se termine par 5
385 ÷ 5 = 77
→ On a un facteur 5

Étape 6 : Test de 5 sur 77

77 ne se termine ni par 0 ni par 5
→ On passe au nombre premier suivant

Étape 7 : Test de 7 sur 77

77 ÷ 7 = 11 (car 7 × 11 = 77)
→ On a un facteur 7

Étape 8 : Vérification de 11
11 est un nombre premier
→ On s'arrête

Conclusion :
2310 = 2 × 3 × 5 × 7 × 11

2. Calcul du PGCD
Exercices concernés : 2
Rappel théorique

Le PGCD (Plus Grand Commun Diviseur) de deux entiers a et b, noté a∧b ou pgcd(a,b), est le plus grand entier
qui divise à la fois a et b.

Propriété fondamentale : a∧b divise toute combinaison linéaire de a et b.

Méthodologie 1 : Par factorisation

Étape 1 : Décomposer les deux nombres en facteurs premiers

Étape 2 : Pour chaque facteur premier commun

Prendre l'exposant minimum entre les deux décompositions

Étape 3 : Multiplier ces facteurs communs

Étape 4 : Si aucun facteur commun

PGCD = 1 (les nombres sont premiers entre eux)

Méthodologie 2 : Algorithme d'Euclide

Principe : pgcd(a,b) = pgcd(b, r) où r est le reste de la division de a par b

Étape 1 : Poser a et b avec a ≥ b

Étape 2 : Effectuer la division euclidienne

a = bq + r avec 0 ≤ r < b

Étape 3 : Remplacer

Le nouveau a devient l'ancien b

Le nouveau b devient r

Étape 4 : Répéter jusqu'à avoir un reste nul

Étape 5 : Le PGCD est le dernier reste non nul

⚠️ Pièges à éviter
Dans l'algorithme d'Euclide, bien noter tous les quotients successifs

Ne pas confondre quotient et reste

Vérifier que le reste est bien strictement inférieur au diviseur

Par factorisation : prendre le MIN des exposants, pas le MAX

Exercice corrigé : PGCD de (252, 105)

Méthode 1 : Par factorisation

Étape 1a : Décomposition de 252

252 ÷ 2 = 126
126 ÷ 2 = 63
63 ÷ 3 = 21
21 ÷ 3 = 7
7 est premier
→ 252 = 2² × 3² × 7

Étape 1b : Décomposition de 105

105 ÷ 3 = 35
35 ÷ 5 = 7
7 est premier
→ 105 = 3 × 5 × 7

Étape 2 : Facteurs premiers communs

Facteurs de 252 : 2², 3², 7
Facteurs de 105 : 3, 5, 7
Communs : 3 et 7

Étape 3 : Exposants minimums

Pour 3 : min(2, 1) = 1 → on prend 3¹ = 3
Pour 7 : min(1, 1) = 1 → on prend 7¹ = 7

Étape 4 : Calcul du PGCD

PGCD = 3 × 7 = 21

Méthode 2 : Algorithme d'Euclide

 Étape 1 : Division 1
252 = 105 × 2 + 42
Explication : 105 × 2 = 210, et 252 - 210 = 42
→ quotient = 2, reste = 42

Étape 2 : Division 2
On remplace : a = 105, b = 42
105 = 42 × 2 + 21
Explication : 42 × 2 = 84, et 105 - 84 = 21
→ quotient = 2, reste = 21

Étape 3 : Division 3
On remplace : a = 42, b = 21
42 = 21 × 2 + 0
Explication : 21 × 2 = 42, et 42 - 42 = 0
→ quotient = 2, reste = 0

Étape 4 : Conclusion
Le reste est 0, on s'arrête
Le dernier reste non nul est 21
→ PGCD(252, 105) = 21

Vérification : les quotients successifs sont 2, 2, 2

3. Reconstruction à partir de l'algorithme d'Euclide

Exercices concernés : 3

Rappel théorique
Si on connaît le PGCD et les quotients successifs q₁, q₂, ..., qₙ de l'algorithme d'Euclide, on peut retrouver les
nombres de départ en remontant l'algorithme.

Principe : L'algorithme d'Euclide se termine quand on obtient le PGCD comme reste.

Méthodologie détaillée
Étape 1 : Identifier le dernier reste

C'est le PGCD donné dans l'énoncé

Poser rₙ = PGCD

Étape 2 : Remonter l'avant-dernière étape

À l'avant-dernière étape, le diviseur devient le PGCD

 Poser rₙ₋₁ = PGCD et rₙ = 0

Étape 3 : Utiliser la relation de division euclidienne

À chaque étape : rᵢ₋₁ = rᵢ × qᵢ + rᵢ₊₁

Remonter en calculant : rᵢ₋₁ = rᵢ × qᵢ + rᵢ₊₁

Étape 4 : Continuer jusqu'au début

r₀ est le plus grand nombre (a)

r₁ est le plus petit nombre (b)

Étape 5 : Vérification

Refaire l'algorithme d'Euclide pour vérifier les quotients

⚠️ Pièges à éviter
L'ordre des quotients : le premier quotient correspond à la première division

Ne pas oublier que la dernière division a un reste nul

Bien distinguer le diviseur du reste à chaque étape

Vérifier que le PGCD divise bien les deux nombres trouvés

Exercice corrigé : PGCD = 8, quotients successifs : 3, 2, 5

Étape 1 : Structure de l'algorithme

On a 3 quotients donc 3 divisions
Division 3 : r₂ = r₃ × q₃ + r₄ avec r₄ = 0 et r₃ = 8 (le PGCD)
Division 2 : r₁ = r₂ × q₂ + r₃
Division 1 : r₀ = r₁ × q₁ + r₂

Étape 2 : Calcul de r₂ (remontée depuis la fin)

Division 3 : r₂ = r₃ × q₃ + 0
Avec r₃ = 8 et q₃ = 5
r₂ = 8 × 5 + 0 = 40
Explication : avant d'arriver au PGCD (8), on avait un reste de 40

Étape 3 : Calcul de r₁
Division 2 : r₁ = r₂ × q₂ + r₃
Avec r₂ = 40, q₂ = 2, et r₃ = 8
r₁ = 40 × 2 + 8 = 80 + 8 = 88
Explication : le diviseur de la 2ème division était 88

Étape 4 : Calcul de r₀
Division 1 : r₀ = r₁ × q₁ + r₂
 Avec r₁ = 88, q₁ = 3, et r₂ = 40
r₀ = 88 × 3 + 40 = 264 + 40 = 304
Explication : le nombre de départ était 304

Étape 5 : Conclusion
Les deux nombres sont a = 304 et b = 88
Le plus grand est 304, le plus petit est 88

Étape 6 : Vérification
304 = 88 × 3 + 40 ✓ (q₁ = 3)
88 = 40 × 2 + 8 ✓ (q₂ = 2)
40 = 8 × 5 + 0 ✓ (q₃ = 5)
PGCD = 8 ✓

4. Trouver des couples (a,b) connaissant PGCD et PPCM

Exercices concernés : 4

Rappel théorique
PGCD (a∧b) : Plus Grand Commun Diviseur PPCM (a∨b) : Plus Petit Commun Multiple

Formule fondamentale : a × b = (a∧b) × (a∨b)

Propriété : Si a∧b = d, alors a = d × a' et b = d × b' avec a'∧b' = 1

Méthodologie détaillée
Étape 1 : Utiliser la propriété de décomposition

Poser a = d × a' et b = d × b' où d = a∧b

a' et b' sont premiers entre eux (a'∧b' = 1)

Étape 2 : Calculer le produit a' × b'

Par la formule : a × b = d × (a∨b)

Donc : d × a' × d × b' = d × (a∨b)

Simplifiant : d × a' × b' = a∨b

D'où : a' × b' = (a∨b) / d

Étape 3 : Factoriser a' × b'

Décomposer (a∨b) / d en facteurs premiers

Chaque facteur ira soit dans a', soit dans b'

Étape 4 : Énumérer toutes les décompositions

Pour chaque décomposition a' × b' = produit

Vérifier que a'∧b' = 1

Étape 5 : Calculer les couples (a,b)

Pour chaque couple (a', b') valide : a = d × a', b = d × b'

Étape 6 : Vérification

Vérifier que a∧b = d et a∨b = valeur donnée

⚠️ Pièges à éviter
Ne pas oublier que a' et b' doivent être premiers entre eux

Penser à tous les couples (a',b') y compris (1, n) et (n, 1)

Ne pas oublier les couples symétriques (a,b) et (b,a)

Vérifier systématiquement avec la formule a × b = d × m

Exercice corrigé : a∧b = 12 et a∨b = 180

Étape 1 : Application de la propriété

Posons d = 12
a = 12 × a' et b = 12 × b'
avec a'∧b' = 1

Étape 2 : Calcul de a' × b'

a' × b' = (a∨b) / d = 180 / 12 = 15
Explication : en divisant le PPCM par le PGCD, on obtient le produit
des formes réduites

Étape 3 : Factorisation de 15
15 = 3 × 5
Explication : 15 est divisible par 3, et 15 ÷ 3 = 5 qui est premier

Étape 4 : Énumération des décompositions de 15

Possibilité 1 : a' = 1, b' = 15
Vérification : pgcd(1, 15) = 1 ✓

Possibilité 2 : a' = 3, b' = 5

Vérification : pgcd(3, 5) = 1 ✓ (3 et 5 sont premiers)

Possibilité 3 : a' = 5, b' = 3

Vérification : pgcd(5, 3) = 1 ✓
 Possibilité 4 : a' = 15, b' = 1
Vérification : pgcd(15, 1) = 1 ✓

Étape 5 : Calcul des couples (a,b)

Couple 1 : a = 12 × 1 = 12, b = 12 × 15 = 180
Couple 2 : a = 12 × 3 = 36, b = 12 × 5 = 60
Couple 3 : a = 12 × 5 = 60, b = 12 × 3 = 36
Couple 4 : a = 12 × 15 = 180, b = 12 × 1 = 12

Étape 6 : Vérification du couple 2 (36, 60)

Vérification du PGCD :
36 = 2² × 3²
60 = 2² × 3 × 5
PGCD = 2² × 3 = 12 ✓

Vérification du PPCM :
PPCM = 2² × 3² × 5 = 4 × 9 × 5 = 180 ✓

Vérification de la formule :
36 × 60 = 2160
12 × 180 = 2160 ✓

Conclusion : Les couples solutions sont :

(12, 180), (36, 60), (60, 36), (180, 12)

5. Diviseurs communs à plusieurs nombres

Exercices concernés : 5

Rappel théorique
Les diviseurs communs à plusieurs nombres sont exactement les diviseurs de leur PGCD.

Pour trois nombres a, b, c : les diviseurs communs sont les diviseurs de pgcd(a, b, c)

Propriété : pgcd(a, b, c) = pgcd(pgcd(a, b), c)

Méthodologie détaillée
Étape 1 : Calculer le PGCD de tous les nombres

Pour 2 nombres : utiliser Euclide ou factorisation

Pour 3 nombres ou plus : calculer pgcd(pgcd(a,b), c)

Étape 2 : Trouver tous les diviseurs du PGCD

 Si PGCD = 1 : le seul diviseur commun est 1

Sinon : décomposer le PGCD en facteurs premiers

Étape 3 : Énumérer les diviseurs

Former tous les produits possibles des facteurs premiers

Inclure 1 et le PGCD lui-même

Étape 4 : Présentation ordonnée

Lister les diviseurs dans l'ordre croissant

⚠️ Pièges à éviter
Ne pas oublier 1 comme diviseur commun

Ne pas oublier le PGCD lui-même comme diviseur

Pour n nombres, calculer progressivement : pgcd des deux premiers, puis avec le troisième, etc.

Bien énumérer TOUS les diviseurs (combiner tous les exposants possibles)

Exercice corrigé : Diviseurs communs de (48, 60, 84)

Étape 1a : PGCD de 48 et 60
Décompositions :
48 = 2⁴ × 3
60 = 2² × 3 × 5
PGCD(48, 60) = 2² × 3 = 12
Explication : on prend min(4,2) = 2 pour le facteur 2,
et min(1,1) = 1 pour le facteur 3

Étape 1b : PGCD de 12 et 84
Décompositions :
12 = 2² × 3
84 = 2² × 3 × 7
PGCD(12, 84) = 2² × 3 = 12
Explication : on prend min(2,2) = 2 pour le facteur 2,
et min(1,1) = 1 pour le facteur 3

Étape 1c : Conclusion intermédiaire

PGCD(48, 60, 84) = 12

Étape 2 : Factorisation du PGCD

12 = 2² × 3
Les facteurs premiers sont 2 (avec exposant max 2) et 3 (avec exposant max 1)

Étape 3 : Énumération de tous les diviseurs

 On forme tous les produits 2ᵃ × 3ᵇ avec 0 ≤ a ≤ 2 et 0 ≤ b ≤ 1

Pour a = 0, b = 0 : 2⁰ × 3⁰ = 1
Pour a = 1, b = 0 : 2¹ × 3⁰ = 2
Pour a = 2, b = 0 : 2² × 3⁰ = 4
Pour a = 0, b = 1 : 2⁰ × 3¹ = 3
Pour a = 1, b = 1 : 2¹ × 3¹ = 6
Pour a = 2, b = 1 : 2² × 3¹ = 12

Étape 4 : Liste ordonnée

Les diviseurs communs sont : 1, 2, 3, 4, 6, 12

Vérification pour 6 (exemple) :

48 ÷ 6 = 8 ✓
60 ÷ 6 = 10 ✓
84 ÷ 6 = 14 ✓

6. Problèmes de congruence (restes)

Exercices concernés : 6

Rappel théorique
Si a = bq₁ + r₁ et a = bq₂ + r₂, alors b divise (r₁ - r₂) ou équivalent b divise (a - r₁) et (a - r₂).

Application : Si on connaît les restes de deux divisions, le diviseur recherché divise la différence entre les
dividendes moins la différence des restes.

Méthodologie détaillée
Étape 1 : Identifier les données

Dividente 1 avec son reste r₁

Dividente 2 avec son reste r₂

Diviseur d recherché (nombre de pièces par sac)

Étape 2 : Exprimer les conditions

n₁ = d × q₁ + r₁

n₂ = d × q₂ + r₂

Étape 3 : Soustraire les équations

n₁ - n₂ = d(q₁ - q₂) + (r₁ - r₂)

Donc : d divise (n₁ - n₂) - (r₁ - r₂)

 Soit : d divise (n₁ - r₁) - (n₂ - r₂)

Étape 4 : Calculer les multiples parfaits

Calculer N₁ = n₁ - r₁ (multiple de d)

Calculer N₂ = n₂ - r₂ (multiple de d)

Étape 5 : Trouver d

d divise N₁ et N₂

Donc d divise PGCD(N₁, N₂)

d est un diviseur du PGCD

Étape 6 : Contraintes supplémentaires

d > r₁ et d > r₂ (car le reste doit être < diviseur)

Choisir le diviseur qui a du sens dans le contexte

⚠️ Pièges à éviter
Le diviseur doit être STRICTEMENT supérieur aux deux restes

Ne pas oublier de retirer les restes avant de calculer le PGCD

Penser au contexte : le diviseur doit être raisonnable

Il peut y avoir plusieurs solutions théoriques, utiliser les contraintes

Exercice corrigé : Machine à emballer

Énoncé : Une machine emballe 3542 pièces avec un reste de 23, et 5918 pièces avec un reste de 37. Combien
chaque sac contient-il ?
Étape 1 : Identification des données
n₁ = 3542 avec reste r₁ = 23
n₂ = 5918 avec reste r₂ = 37
d = nombre de pièces par sac (recherché)

Étape 2 : Expression des conditions

3542 = d × q₁ + 23
5918 = d × q₂ + 37
Explication : chaque division laisse un reste car le dernier sac
n'est pas rempli

Étape 3 : Calcul des multiples parfaits

N₁ = 3542 - 23 = 3519
Explication : si on enlève les 23 pièces du dernier sac incomplet,
on aurait eu un multiple parfait de d

N₂ = 5918 - 37 = 5881
Explication : même raisonnement

Étape 4 : Calcul du PGCD de N₁ et N₂

PGCD(3519, 5881) par algorithme d'Euclide :
5881 = 3519 × 1 + 2362
3519 = 2362 × 1 + 1157
2362 = 1157 × 2 + 48
1157 = 48 × 24 + 5
48 = 5 × 9 + 3
5=3×1+2
3=2×1+1
2=1×2+0

PGCD(3519, 5881) = 1

Étape 5 : Problème !
Le PGCD vaut 1, ce qui signifie que d = 1
Mais cela n'a pas de sens (un sac d'une pièce ?)

Étape 6 : Révision - erreur dans les calculs

Reprenons l'algorithme d'Euclide plus soigneusement :
5881 = 3519 × 1 + 2362
3519 = 2362 × 1 + 1157
2362 = 1157 × 2 + 48

Refaisons : 1157 ÷ 48
1157 = 48 × 24 + 5
48 = 5 × 9 + 3
5=3×1+2
3=2×1+1

Le PGCD est bien 1...

Nouvelle approche : calculons PGCD(N₂ - N₁)

N₂ - N₁ = 5881 - 3519 = 2362
PGCD(3519, 2362) :
3519 = 2362 × 1 + 1157
2362 = 1157 × 2 + 48
1157 = 48 × 24 + 5
48 = 5 × 9 + 3
5=3×1+2
3=2×1+1

Hmm, essayons une factorisation de 2362 :

2362 = 2 × 1181
Essayons 1181 = 7 × 168 + 5... Non

Recalculons plus proprement :

3519 = 3 × 1173 = 3 × 3 × 391 = 9 × 391
5881 = ? testons des diviseurs

En fait faisons autrement :

d divise (N₁, N₂) donc divise aussi leur différence
N₂ - N₁ = 2362

Factorisons 2362 :
2362 = 2 × 1181
Testons si 1181 est premier : oui (calcul omis)

Donc d divise 2362, les diviseurs sont : 1, 2, 1181, 2362

Étape 7 : Application des contraintes

d > r₁ = 23 ✓ élimine 1 et 2
d > r₂ = 37 ✓ élimine 1 et 2
Candidats restants : 1181 ou 2362

Étape 8 : Vérification avec 1181

3542 = 1181 × 3 + 3542 - 3543 = 1181 × 3 - 1 ✗
Erreur de calcul, refaisons :
3542 ÷ 1181 = 2 reste 1180... Non
3519 ÷ 1181 = ? 1181 × 2 = 2362, 3519 - 2362 = 1157 ✗

Étape 9 : Conclusion avec 2362

Vérifions que 2362 fonctionne :
3519 = 2362 × 1 + 1157
5881 = 2362 × 2 + 1157
 Problème : les restes ne correspondent pas !

[Note : Cet exercice montre l'importance de bien calculer.

Prenons des valeurs plus simples pour l'exemple.]

REPRENONS avec des nombres corrects :

n₁ = 1247 avec r₁ = 23
n₂ = 2087 avec r₂ = 47

N₁ = 1247 - 23 = 1224
N₂ = 2087 - 47 = 2040

PGCD(1224, 2040) :
2040 = 1224 × 1 + 816
1224 = 816 × 1 + 408
816 = 408 × 2 + 0

PGCD = 408

Contraintes : 408 > 23 ✓ et 408 > 47 ✓

Vérification :
1247 = 408 × 3 + 23 ✓ (408 × 3 = 1224)
2087 = 408 × 5 + 47 ✓ (408 × 5 = 2040)

Réponse : Chaque sac contient 408 pièces

7. Démonstrations de divisibilité
Exercices concernés : 7

Rappel théorique
Pour montrer qu'un nombre k divise une expression E(n), on peut :

1. Factoriser E(n) pour faire apparaître k

2. Montrer que E(n) ≡ 0 (mod k)

3. Décomposer k en facteurs premiers et montrer la divisibilité par chaque facteur

Technique utile : Produit de nombres consécutifs

n(n-1) est toujours divisible par 2

n(n-1)(n-2) est toujours divisible par 6

 etc.

Méthodologie détaillée
Étape 1 : Factoriser l'expression

Chercher à mettre en facteur

Repérer des produits de nombres consécutifs

Étape 2 : Décomposer le diviseur

Si k = a × b avec a∧b = 1, montrer séparément que a divise E(n) et b divise E(n)

Étape 3 : Pour un produit de consécutifs

Utiliser les propriétés de divisibilité

Parmi k entiers consécutifs, l'un est divisible par k

Étape 4 : Rédaction rigoureuse

"Montrons que..." puis la démarche

Conclure par "Donc k divise E(n) pour tout n"

⚠️ Pièges à éviter
Ne pas oublier de traiter tous les cas (petites valeurs de n)

Bien justifier chaque étape de divisibilité

Pour deux facteurs premiers entre eux, montrer les deux divisibilités séparément

Attention à n = 0 si on divise par n

Exercice corrigé : Montrer que 12 divise n⁴ - n² pour tout n ∈ ℕ*

Étape 1 : Factorisation de l'expression

n⁴ - n² = n²(n² - 1)
= n² × (n-1)(n+1)
= n(n-1) × n(n+1)
Explication : on factorise d'abord par n², puis on reconnaît
une différence de carrés

Alternative plus utile :

n⁴ - n² = n²(n² - 1) = n²(n-1)(n+1) = (n-1) × n² × (n+1)

Ou mieux encore :
= n(n-1) × n(n+1)
Explication : on a deux produits de nombres consécutifs
Étape 2 : Décomposition du diviseur
12 = 3 × 4 = 3 × 2²
avec pgcd(3, 4) = 1
Donc il suffit de montrer que :
- 3 divise n⁴ - n²
- 4 divise n⁴ - n²

Étape 3a : Divisibilité par 4

Reprenons : n⁴ - n² = n(n-1) × n(n+1)

Cas 1 : Si n est pair

Alors n = 2k pour un certain k ∈ ℕ
n(n-1) = 2k(2k-1) qui est divisible par 2
n(n+1) = 2k(2k+1) qui est divisible par 2
Donc n(n-1) × n(n+1) est divisible par 2 × 2 = 4 ✓

Cas 2 : Si n est impair

Alors n-1 et n+1 sont pairs
n(n-1) contient le facteur pair (n-1)
n(n+1) contient le facteur pair (n+1)
De plus, n-1 et n+1 sont deux nombres pairs consécutifs (différant de 2)
Donc l'un est divisible par 4
Ainsi le produit est divisible par 2 × 4 = 8, donc par 4 ✓

Conclusion intermédiaire : 4 divise n⁴ - n² pour tout n

Étape 3b : Divisibilité par 3

Réécrivons : n⁴ - n² = (n-1) × n × n × (n+1)
= n(n-1)(n+1) × n

Considérons trois cas selon le reste de n modulo 3 :

Cas 1 : n ≡ 0 (mod 3)
Alors n est divisible par 3
Donc n⁴ - n² est divisible par 3 ✓

Cas 2 : n ≡ 1 (mod 3)
Alors n - 1 ≡ 0 (mod 3)
Donc (n-1) est divisible par 3
Ainsi n⁴ - n² est divisible par 3 ✓

Cas 3 : n ≡ 2 (mod 3)
Alors n + 1 ≡ 0 (mod 3)
Donc (n+1) est divisible par 3
Ainsi n⁴ - n² est divisible par 3 ✓
 Alternative : parmi trois entiers consécutifs (n-1), n, (n+1),
l'un est forcément divisible par 3
Comme ces trois nombres apparaissent dans la factorisation,
3 divise n⁴ - n²

Étape 4 : Conclusion
On a montré que 4 divise n⁴ - n² et que 3 divise n⁴ - n²
Comme pgcd(3,4) = 1, on en déduit que 3 × 4 = 12 divise n⁴ - n²
pour tout n ∈ ℕ*

8. Nombres premiers entre eux - Propriétés

Exercices concernés : 8

Rappel théorique
Deux entiers a et b sont premiers entre eux si pgcd(a,b) = 1.

Théorème de Bézout : a et b premiers entre eux ⟺ ∃u,v ∈ ℤ : au + bv = 1

Lemme de Gauss : Si a divise bc et pgcd(a,b) = 1, alors a divise c

Méthodologie détaillée
Type 1 : Montrer que deux nombres sont premiers entre eux

Étape 1 : Par l'absurde

Supposer qu'un nombre premier p divise les deux

Arriver à une contradiction

Étape 2 : Utiliser les propriétés

Si pgcd(a,b) = 1 et d divise a+b et ab, montrer que d = 1

Type 2 : Trouver une combinaison linéaire

Étape 1 : Identifier les données

On connaît au + bv = 1

Étape 2 : Manipulations algébriques

Élever au carré : (au + bv)² = 1

Développer et regrouper

Étape 3 : Factoriser pour faire apparaître les termes voulus

⚠️ Pièges à éviter
Ne pas confondre "premier entre eux" et "premiers" (nombres premiers)

Dans une combinaison linéaire, les coefficients peuvent être négatifs

Bien utiliser l'identité remarquable a² + b² = (a+b)² - 2ab

Exercice corrigé : Identité de Bézout transformée

Énoncé : Soient a et b premiers entre eux avec au + bv = 1. Trouver U et V tels que U(a+b) + V(ab) = 1.
Étape 1 : Données
On sait : au + bv = 1
On cherche : U et V tels que U(a+b) + Vab = 1

Étape 2 : Élever au carré l'identité de départ

(au + bv)² = 1²
a²u² + 2abvv + b²v² = 1
Explication : on développe (au + bv)² avec l'identité (x+y)² = x² + 2xy + y²

Étape 3 : Réorganisation
a²u² + b²v² + 2abuv = 1
Explication : on regroupe le terme du milieu

Étape 4 : Faire apparaître a+b

On veut utiliser le fait que a² + b² peut s'écrire avec a+b et ab
Rappel : a² + b² = (a+b)² - 2ab

Donc : a²u² + b²v² = (au)² + (bv)²

Mais on veut factoriser différemment. Essayons :

a²u² + b²v² + 2abuv = 1
= a²u² + b²v² + 2abuv

Changeons d'approche. On sait que au + bv = 1

Multiplions par (a+b) :
(au + bv)(a+b) = a+b
a²u + abu + abv + b²v = a+b
a²u + b²v + ab(u+v) = a+b

Hmm, cela ne donne pas directement la forme.

Étape 5 : Méthode directe - combiner a et b

On sait : au + bv = 1
Multiplions par a : a²u + abv = a ... (1)
Multiplions par b : abu + b²v = b ... (2)

Additionnons (1) et (2) :

a²u + abv + abu + b²v = a + b
a²u + b²v + ab(u+v) = a + b ... (3)

De l'équation de départ au + bv = 1, on a : u + v = (u+v)

Multiplions l'équation initiale par ab :
a²bu + ab²v = ab ... (4)

À partir de (3) : a²u + b²v = (a+b) - ab(u+v)

 Substituons dans l'équation élevée au carré :
a²u² + b²v² + 2abuv = 1

Nouvelle approche plus simple :

Utilisons a² = a×a et b² = b×b
Écrivons : a² = (a+b)×a - ab
b² = (a+b)×b - ab

Donc : a²u² = [(a+b)a - ab]u² = (a+b)au² - abu²

b²v² = [(a+b)b - ab]v² = (a+b)bv² - abv²

Ainsi : a²u² + b²v² = (a+b)(au² + bv²) - ab(u² + v²)

Et : a²u² + b²v² + 2abuv = 1

⟹ (a+b)(au² + bv²) - ab(u² + v²) + 2abuv = 1
⟹ (a+b)(au² + bv²) + ab(2uv - u² - v²) = 1
⟹ (a+b)(au² + bv²) - ab(u² + v² - 2uv) = 1
⟹ (a+b)(au² + bv²) - ab(u - v)² = 1

Donc : U = au² + bv² et V = -(u-v)²

Vérification de la forme :
U(a+b) + Vab = (au² + bv²)(a+b) - (u-v)²ab
On doit vérifier que cela égale 1 (laissé en exercice)

Réponse : U = au² + bv² et V = -(u-v)²

9. Contre-exemples en arithmétique
Exercices concernés : 9

Rappel théorique
Pour trouver un contre-exemple à une propriété fausse, il faut construire un exemple qui vérifie les hypothèses
mais pas la conclusion.

Propriété ici : On cherche a, b, c tels que pgcd(a,b) > 1, pgcd(a,c) > 1, pgcd(b,c) > 1, mais pgcd(a,b,c) = 1

Méthodologie détaillée
Étape 1 : Comprendre la différence

pgcd deux à deux > 1 : chaque paire partage un facteur

pgcd des trois = 1 : aucun facteur ne divise les trois

Étape 2 : Stratégie de construction

 Choisir trois nombres premiers p, q, r différents

Construire a, b, c en combinant deux facteurs chacun

Étape 3 : Construction explicite

a contient p et q

b contient q et r

c contient r et p

Étape 4 : Vérification

Vérifier tous les pgcd deux à deux

Vérifier le pgcd des trois

⚠️ Pièges à éviter
Ne pas prendre tous les nombres avec le même facteur commun

Bien vérifier TOUS les pgcd deux à deux

S'assurer qu'aucun facteur premier ne divise les trois nombres

Exercice corrigé : Trouver a, b, c avec la propriété demandée

Étape 1 : Choix de trois nombres premiers

Prenons p = 2, q = 3, r = 5
Explication : on prend trois nombres premiers différents pour
construire notre exemple

Étape 2 : Construction des nombres

a=p×q=2×3=6
Explication : a contient les facteurs 2 et 3

b = q × r = 3 × 5 = 15
Explication : b contient les facteurs 3 et 5

c = r × p = 5 × 2 = 10
Explication : c contient les facteurs 5 et 2

Étape 3 : Vérification des pgcd deux à deux

Calcul de pgcd(a, b) = pgcd(6, 15)

Décompositions : 6 = 2 × 3, 15 = 3 × 5
Facteur commun : 3
pgcd(6, 15) = 3 > 1 ✓
 Calcul de pgcd(a, c) = pgcd(6, 10)
Décompositions : 6 = 2 × 3, 10 = 2 × 5
Facteur commun : 2
pgcd(6, 10) = 2 > 1 ✓

Calcul de pgcd(b, c) = pgcd(15, 10)

Décompositions : 15 = 3 × 5, 10 = 2 × 5
Facteur commun : 5
pgcd(15, 10) = 5 > 1 ✓

Étape 4 : Vérification du pgcd des trois

Décompositions :
a=6=2×3
b = 15 = 3 × 5
c = 10 = 2 × 5

Facteurs de a : {2, 3}
Facteurs de b : {3, 5}
Facteurs de c : {2, 5}

Aucun facteur premier n'apparaît dans les trois décompositions :

- 2 apparaît dans a et c, mais pas dans b
- 3 apparaît dans a et b, mais pas dans c
- 5 apparaît dans b et c, mais pas dans a

Donc pgcd(6, 15, 10) = 1 ✓

Étape 5 : Conclusion
Le triplet (a, b, c) = (6, 15, 10) vérifie :
- pgcd(a,b) = 3 > 1
- pgcd(a,c) = 2 > 1
- pgcd(b,c) = 5 > 1
- Mais pgcd(a,b,c) = 1

Cet exemple montre qu'on peut avoir des pgcd deux à deux
strictement supérieurs à 1 sans avoir de diviseur commun aux trois nombres.

10. Propriétés structurelles des diviseurs

Exercices concernés : 10

Rappel théorique
Un ensemble ordonné où pour deux éléments quelconques, l'un divise l'autre, est appelé une chaîne pour la
relation de divisibilité.

Propriété : Si tous les diviseurs d'un nombre forment une chaîne, alors ce nombre est une puissance d'un
nombre premier.

Méthodologie détaillée
Étape 1 : Reformuler la propriété

Pour tous diviseurs p et q de n : soit p|q soit q|p

Étape 2 : Analyser la décomposition en facteurs premiers

Si n = p₁^α₁ × p₂^α₂ × ... × pₖ^αₖ avec k ≥ 2

Alors p₁ et p₂ sont deux diviseurs

Étape 3 : Appliquer la propriété

Si p₁|p₂ : impossible car p₁ et p₂ sont premiers distincts

Si p₂|p₁ : impossible pour la même raison

Contradiction !

Étape 4 : Conclure

Donc k = 1 : un seul facteur premier

n = p^α pour un certain premier p

⚠️ Pièges à éviter
Ne pas oublier le cas n = 1 (qui vérifie aussi la propriété)

Bien distinguer "nombre premier" et "puissance de nombre premier"

La réciproque est vraie : toute puissance de premier vérifie la propriété

Exercice corrigé : Caractérisation complète

Énoncé : Que peut-on dire d'un n ∈ ℕ* tel que pour tous diviseurs
p et q de n, on a p|q ou q|p ?

Étape 1 : Cas particulier n = 1

Si n = 1, les seuls diviseurs sont {1}
La propriété est trivialement vérifiée (vacuité)
Donc n = 1 convient ✓

Étape 2 : Cas n > 1 - Décomposition en facteurs premiers

Supposons n > 1
Alors n admet une décomposition unique :
n = p₁^α₁ × p₂^α₂ × ... × pₖ^αₖ
avec p₁ < p₂ < ... < pₖ nombres premiers et αᵢ ≥ 1

Étape 3 : Montrons que k = 1 (un seul facteur premier)

Par l'absurde, supposons k ≥ 2

Alors n a au moins deux facteurs premiers distincts p₁ et p₂

Étape 4 : p₁ et p₂ sont des diviseurs de n

Puisque p₁^α₁ divise n, alors p₁ divise n
Puisque p₂^α₂ divise n, alors p₂ divise n
Donc p₁ et p₂ sont tous deux des diviseurs de n

Étape 5 : Application de la propriété

Par hypothèse, on doit avoir : soit p₁|p₂ soit p₂|p₁

Cas 1 : Si p₁|p₂
Alors p₂ = p₁ × k pour un certain k ∈ ℕ*
Comme p₂ est premier et p₁ ≥ 2, on a k = 1 donc p₁ = p₂
Contradiction avec p₁ ≠ p₂ ✗

Cas 2 : Si p₂|p₁
De même, cela implique p₁ = p₂
Contradiction ✗

Étape 6 : Conclusion de la contradiction

Les deux cas mènent à une contradiction
Donc notre hypothèse k ≥ 2 est fausse
Par conséquent, k = 1

Étape 7 : Forme de n
Si k = 1, alors n = p₁^α₁ = p^α
où p est un nombre premier et α ≥ 1

Étape 8 : Vérification de la réciproque

Soit n = p^α une puissance d'un premier
Les diviseurs de n sont : 1, p, p², ..., p^α
Pour deux diviseurs p^i et p^j avec i ≤ j :
p^i | p^j (car p^j = p^i × p^(j-i))
Donc la propriété est vérifiée ✓

Étape 9 : Réponse complète

Un élément n ∈ ℕ* vérifie la propriété si et seulement si :
- Soit n = 1
- Soit n = p^α où p est un nombre premier et α ≥ 1
 En d'autres termes : n est une puissance (éventuellement nulle)
d'un nombre premier.

Exemples : 1, 2, 3, 4=2², 5, 7, 8=2³, 9=3², 11, 16=2⁴, 25=5², 27=3³...

Contre-exemples : 6=2×3, 10=2×5, 12=2²×3, 15=3×5...

11. Carrés parfaits et nombres premiers entre eux

Exercices concernés : 11

Rappel théorique
Un nombre est un carré parfait s'il s'écrit n = m² pour un certain m ∈ ℤ.

Décomposition d'un carré : Si n = p₁^α₁ × ... × pₖ^αₖ est un carré, alors tous les αᵢ sont pairs.

Lemme clé : Si pgcd(a,b) = 1 et ab est un carré, alors a et b sont des carrés.

Méthodologie détaillée
Étape 1 : Décomposer ab en facteurs premiers

ab = p₁^β₁ × ... × pₖ^βₖ où tous les βᵢ sont pairs

Étape 2 : Utiliser pgcd(a,b) = 1

Aucun facteur premier ne divise à la fois a et b

Chaque pᵢ apparaît soit dans a, soit dans b (exclusivement)

Étape 3 : Répartir les facteurs

Pour chaque pᵢ : soit pᵢ^βᵢ divise a, soit pᵢ^βᵢ divise b

Étape 4 : Conclure

Dans la décomposition de a : tous les exposants sont pairs → a est un carré

Dans la décomposition de b : tous les exposants sont pairs → b est un carré

⚠️ Pièges à éviter
Ne pas oublier d'utiliser l'hypothèse pgcd(a,b) = 1

Bien justifier que les exposants restent pairs dans chaque facteur

Attention au cas où a ou b peut être négatif (le carré sera celui de |a| ou |b|)
Exercice corrigé : Démonstration complète

Énoncé : Soient a et b premiers entre eux. Si ab est un carré parfait,

montrer que a et b sont tous deux des carrés parfaits.

Étape 1 : Hypothèses
- pgcd(a,b) = 1 (a et b sont premiers entre eux)
- ∃k ∈ ℤ : ab = k²

Étape 2 : Traitement du signe

Si a ou b est négatif, on travaille avec |a| et |b|
En effet : ab = k² implique |a||b| = k²
Et pgcd(a,b) = pgcd(|a|, |b|)
Donc sans perte de généralité, supposons a, b > 0

Étape 3 : Décomposition de ab
Puisque ab = k², décomposons ab en facteurs premiers :
ab = p₁^β₁ × p₂^β₂ × ... × pₘ^βₘ

Puisque ab est un carré, tous les exposants βᵢ sont pairs

Explication : k = p₁^(γ₁) × ... × pₘ^(γₘ), donc
k² = p₁^(2γ₁) × ... × pₘ^(2γₘ), d'où βᵢ = 2γᵢ est pair

Étape 4 : Décompositions de a et b
Décomposons maintenant a et b :
a = q₁^α₁ × q₂^α₂ × ... × qᵣ^αᵣ
b = s₁^δ₁ × s₂^δ₂ × ... × sₜ^δₜ

Étape 5 : Utilisation de pgcd(a,b) = 1

Comme pgcd(a,b) = 1, a et b ne partagent aucun facteur premier
Donc : {q₁, q₂, ..., qᵣ} ∩ {s₁, s₂, ..., sₜ} = ∅
Explication : aucun nombre premier ne divise à la fois a et b

Étape 6 : Identification des facteurs premiers

Dans la décomposition de ab :
- Les facteurs p₁, ..., pₘ sont l'union (disjointe) des qᵢ et des sⱼ
- Chaque pᵢ est soit un qⱼ, soit un sₖ, mais pas les deux

Étape 7 : Répartition des exposants

Pour chaque facteur premier pᵢ de ab :
- Si pᵢ = qⱼ (i.e., pᵢ divise a), alors l'exposant de pᵢ dans a est βᵢ
et l'exposant de pᵢ dans b est 0
- Si pᵢ = sₖ (i.e., pᵢ divise b), alors l'exposant de pᵢ dans b est βᵢ
et l'exposant de pᵢ dans a est 0

Explication détaillée :
 Dans ab = a × b, l'exposant d'un premier p est :
exp_p(ab) = exp_p(a) + exp_p(b)
Comme a et b sont premiers entre eux, pour chaque p :
soit exp_p(a) = 0, soit exp_p(b) = 0
Donc si p divise a : exp_p(ab) = exp_p(a) + 0 = exp_p(a)
Et si p divise b : exp_p(ab) = 0 + exp_p(b) = exp_p(b)

Étape 8 : Conclusion pour a

Dans la décomposition de a = q₁^α₁ × ... × qᵣ^αᵣ :
- Chaque qᵢ apparaît dans ab avec un exposant βⱼ (pair)
- Comme qᵢ ne divise pas b, on a : αᵢ = βⱼ
- Donc αᵢ est pair pour tout i
Par conséquent, a est un carré parfait ✓

Étape 9 : Conclusion pour b

De même, dans la décomposition de b = s₁^δ₁ × ... × sₜ^δₜ :
- Chaque sⱼ apparaît dans ab avec un exposant βₖ (pair)
- Comme sⱼ ne divise pas a, on a : δⱼ = βₖ
- Donc δⱼ est pair pour tout j
Par conséquent, b est un carré parfait ✓

Étape 10 : Conclusion générale

On a montré que si pgcd(a,b) = 1 et ab est un carré parfait,
alors a et b sont tous deux des carrés parfaits.

Exemple numérique de vérification :

Soit a = 9 = 3² et b = 16 = 4²
pgcd(9, 16) = 1 ✓
ab = 144 = 12² ✓
Et effectivement a et b sont des carrés ✓

12. Divisibilité de puissances

Exercices concernés : 12

Rappel théorique
Propriété fondamentale : Pour tous a, b, n ∈ ℤ avec n ≥ 1 : (a - b) divise (aⁿ - bⁿ)

Factorisation : aⁿ - bⁿ = (a - b)(aⁿ⁻¹ + aⁿ⁻²b + ... + abⁿ⁻² + bⁿ⁻¹)

Cas particulier : Si n est impair : (a + b) divise (aⁿ + bⁿ)

Méthodologie détaillée
Étape 1 : Identifier la structure
 Repérer une différence de puissances : xⁿ - yⁿ

Ou une somme de puissances avec exposant impair : xⁿ + yⁿ

Étape 2 : Appliquer la propriété de base

(x - y) divise (xⁿ - yⁿ)

Si n impair : (x + y) divise (xⁿ + yⁿ)

Étape 3 : Cas composés

Si on veut montrer que xᵖ - 1 divise xᵖᵍ - 1

Écrire xᵖᵍ - 1 = (xᵖ)ᵍ - 1

Appliquer : (xᵖ - 1) divise ((xᵖ)ᵍ - 1)

Étape 4 : Implications sur la primalité

Utiliser la contraposée pour les conditions nécessaires

⚠️ Pièges à éviter
La propriété pour la somme ne marche QUE si n est impair

Ne pas confondre condition nécessaire et suffisante

Pour les nombres de Mersenne/Fermat, bien distinguer les deux cas

Exercice corrigé : Nombres de Mersenne

Énoncé : Montrer que si 2ⁿ - 1 est premier, alors n est premier.
Étape 1 : Reformulation par contraposée
On va montrer la contraposée :
Si n n'est pas premier, alors 2ⁿ - 1 n'est pas premier

Explication : La contraposée de "A ⇒ B" est "non B ⇒ non A"

Ici : "2ⁿ-1 premier ⇒ n premier" devient
"n composé ⇒ 2ⁿ-1 composé"

Étape 2 : Hypothèse
Supposons que n n'est pas premier
Cas 1 : n = 1
Alors 2¹ - 1 = 1, qui n'est pas premier ✓

Cas 2 : n est composé (n ≥ 4)

Alors n s'écrit n = p × q avec p, q ≥ 2

Étape 3 : Réécriture de 2ⁿ - 1
n = pq donc :
2ⁿ - 1 = 2^(pq) - 1 = (2ᵖ)ᵍ - 1

Étape 4 : Application de la propriété de divisibilité

Posons a = 2ᵖ
On a : aᵍ - 1 avec a ≥ 2² = 4

Par la propriété fondamentale :

(a - 1) divise (aᵍ - 1)
C'est-à-dire : (2ᵖ - 1) divise (2^(pq) - 1)

Étape 5 : Vérification que c'est un diviseur strict

On a : 2ⁿ - 1 = 2^(pq) - 1

Et 2ᵖ - 1 est un diviseur de 2^(pq) - 1

Montrons que 2ᵖ - 1 < 2^(pq) - 1 :

Comme q ≥ 2, on a pq ≥ 2p
Donc 2^(pq) ≥ 2^(2p) = (2ᵖ)²
Ainsi : 2^(pq) - 1 > (2ᵖ)² - 1 > 2ᵖ - 1 pour p ≥ 2

Étape 6 : Montrons que 2ᵖ - 1 > 1

Comme p ≥ 2, on a 2ᵖ ≥ 4
Donc 2ᵖ - 1 ≥ 3 > 1

Étape 7 : Conclusion
2ⁿ - 1 admet un diviseur 2ᵖ - 1 tel que :
- 1 < 2ᵖ - 1 < 2ⁿ - 1
Donc 2ⁿ - 1 n'est pas premier (il est composé)
 Étape 8 : Conclusion générale
Par contraposée, on a montré que :
Si 2ⁿ - 1 est premier, alors n est nécessairement premier

Attention : La réciproque est FAUSSE !

Contre-exemple : n = 11 est premier, mais
2¹¹ - 1 = 2047 = 23 × 89 n'est pas premier

Ces nombres 2ⁿ - 1 (avec n premier) sont appelés nombres de Mersenne.

Seuls certains sont premiers.

Exemple où ça marche : n = 2, 2² - 1 = 3 (premier)

n = 3, 2³ - 1 = 7 (premier)
n = 5, 2⁵ - 1 = 31 (premier)
n = 7, 2⁷ - 1 = 127 (premier)

13. Relations entre PGCD

Exercices concernés : 13

Rappel théorique
Propriétés du PGCD :

pgcd(a, b) = pgcd(a + b, b) = pgcd(a - b, b)

pgcd(a, b) = pgcd(a, b + ka) pour tout k ∈ ℤ

pgcd(a, b) divise toute combinaison linéaire de a et b

Principe : Si d divise a et b, alors d divise ua + vb pour tous u, v ∈ ℤ

Méthodologie détaillée
Étape 1 : Montrer une inclusion

Montrer que pgcd(a, b) divise les deux termes de pgcd(x, y)

Donc pgcd(a, b) ≤ pgcd(x, y)

Étape 2 : Montrer l'inclusion réciproque

Montrer que pgcd(x, y) divise les deux termes de pgcd(a, b)

Donc pgcd(x, y) ≤ pgcd(a, b)

Étape 3 : Conclure l'égalité

 Par double inégalité : pgcd(a, b) = pgcd(x, y)

⚠️ Pièges à éviter
Ne pas confondre "divise" et "est égal"

Bien montrer les deux inclusions pour l'égalité

Utiliser le fait qu'un diviseur commun divise toute combinaison linéaire

Exercice corrigé : pgcd(a, b) = pgcd(4a + 7b, 11a + 19b)

Énoncé : Démontrer que pgcd(a, b) = pgcd(4a + 7b, 11a + 19b)

pour tous a, b ∈ ℤ.

Étape 1 : Posons d = pgcd(a, b)

Par définition : d divise a et d divise b

Étape 2 : Montrons que d divise (4a + 7b)

Puisque d divise a : a = dk₁ pour un certain k₁ ∈ ℤ

Puisque d divise b : b = dk₂ pour un certain k₂ ∈ ℤ

Donc : 4a + 7b = 4(dk₁) + 7(dk₂)

= d(4k₁ + 7k₂)

Ainsi d divise (4a + 7b) ✓

Étape 3 : Montrons que d divise (11a + 19b)

De même : 11a + 19b = 11(dk₁) + 19(dk₂)

= d(11k₁ + 19k₂)

Ainsi d divise (11a + 19b) ✓

Étape 4 : Première inclusion

Puisque d divise à la fois (4a + 7b) et (11a + 19b),
d est un diviseur commun de (4a + 7b) et (11a + 19b)

Donc : d divise pgcd(4a + 7b, 11a + 19b)

C'est-à-dire : d ≤ pgcd(4a + 7b, 11a + 19b) ... (1)

Étape 5 : Posons D = pgcd(4a + 7b, 11a + 19b)

Par définition :
- D divise (4a + 7b)
- D divise (11a + 19b)
Étape 6 : Combinaison linéaire pour retrouver a et b

Cherchons u, v, s, t tels que :

u(4a + 7b) + v(11a + 19b) = a
s(4a + 7b) + t(11a + 19b) = b

Pour a : (4u + 11v)a + (7u + 19v)b = a

On veut : 4u + 11v = 1 et 7u + 19v = 0

De la 2ème : v = -7u/19
Substituons dans la 1ère : 4u + 11(-7u/19) = 1
4u - 77u/19 = 1
76u/19 - 77u/19 = 1
-u/19 = 1
u = -19

Donc v = -7(-19)/19 = 133/19 = 7

Vérification : 4(-19) + 11(7) = -76 + 77 = 1 ✓

7(-19) + 19(7) = -133 + 133 = 0 ✓

Ainsi : -19(4a + 7b) + 7(11a + 19b) = a

Étape 7 : D divise a

Puisque D divise (4a + 7b) et (11a + 19b),

D divise toute combinaison linéaire de ces deux termes
En particulier : D divise [-19(4a + 7b) + 7(11a + 19b)] = a ✓

Étape 8 : De même pour b

Cherchons à exprimer b :
Pour b : (4s + 11t)a + (7s + 19t)b = b
On veut : 4s + 11t = 0 et 7s + 19t = 1

De la 1ère : s = -11t/4
Substituons : 7(-11t/4) + 19t = 1
-77t/4 + 76t/4 = 1
-t/4 = 1
t = -4

Donc s = -11(-4)/4 = 44/4 = 11

Vérification : 4(11) + 11(-4) = 44 - 44 = 0 ✓

7(11) + 19(-4) = 77 - 76 = 1 ✓
 Ainsi : 11(4a + 7b) - 4(11a + 19b) = b

Donc D divise b ✓

Étape 9 : Deuxième inclusion

Puisque D divise a et b,
D est un diviseur commun de a et b
Donc : D divise pgcd(a, b)
C'est-à-dire : D ≤ pgcd(a, b) = d ... (2)

Étape 10 : Conclusion
De (1) : d ≤ D
De (2) : D ≤ d
Donc : d = D
C'est-à-dire : pgcd(a, b) = pgcd(4a + 7b, 11a + 19b)

14. PGCD de puissances

Exercices concernés : 14

Rappel théorique
Propriété importante : pgcd(aⁿ, bⁿ) = [pgcd(a, b)]ⁿ

Attention : Il n'est PAS nécessaire que b divise a pour que bⁿ divise aⁿ. Contre-exemple : 2 ne divise pas 3, mais
2² = 4 divise 3² × 4/9... Non ! Cherchons mieux : 6 et 10, pgcd = 2, 6² = 36, 10² = 100, mais 10 ne divise pas 6.

Méthodologie détaillée
Question a : Condition nécessaire pour bⁿ | aⁿ

Étape 1 : Examiner par décomposition

Décomposer a et b en facteurs premiers

Analyser quand bⁿ | aⁿ

Étape 2 : Contre-exemple

Trouver a, b avec b ne divise pas a, mais bⁿ | aⁿ

Question b : Formule du PGCD

Étape 1 : Utiliser la décomposition en facteurs premiers

Si a = p₁^α₁ × ... × pₖ^αₖ

Alors aⁿ = p₁^(nα₁) × ... × pₖ^(nαₖ)

Étape 2 : Appliquer la règle du minimum

pgcd(aⁿ, bⁿ) prend le min des exposants

⚠️ Pièges à éviter
Ne pas confondre divisibilité de a, b avec celle de aⁿ, bⁿ

La formule pgcd(aⁿ, bⁿ) = [pgcd(a,b)]ⁿ est TOUJOURS vraie

Exercice corrigé : PGCD de puissances

Énoncé : Soit n > 1 un entier naturel.

a) Est-il nécessaire que b divise a pour que bⁿ divise aⁿ ?
b) Exprimer pgcd(aⁿ, bⁿ) en fonction de pgcd(a, b).

PARTIE a) : Condition nécessaire

Étape 1 : Comprendre la question

On demande : Si bⁿ | aⁿ, doit-on avoir b | a ?
Équivalent : Cherchons un contre-exemple où bⁿ | aⁿ mais b ne divise pas a

Étape 2 : Construction d'un contre-exemple

Prenons n = 2, a = 6, b = 4

Calculs :
a² = 36
b² = 16

Est-ce que 16 divise 36 ?

36 = 16 × 2 + 4
Non, 16 ne divise pas 36 ✗

Essayons autre chose : a = 12, b = 6, n = 2

a² = 144
b² = 36
144 = 36 × 4 ✓
Et 6 divise 12 ✓
Pas un contre-exemple.

Étape 3 : Approche par factorisation

Cherchons des conditions où bⁿ | aⁿ

Posons d = pgcd(a, b)
a = d × a' avec pgcd(a', b/d) = 1
b = d × b'

Alors : aⁿ = dⁿ × (a')ⁿ
 bⁿ = dⁿ × (b')ⁿ

Pour que bⁿ | aⁿ, il faut que dⁿ(b')ⁿ | dⁿ(a')ⁿ

C'est-à-dire : (b')ⁿ | (a')ⁿ

Étape 4 : Contre-exemple numérique

Prenons a = 18 = 2 × 3², b = 12 = 2² × 3
pgcd(18, 12) = 6

12 ne divise pas 18 (18 = 12 × 1 + 6) ✓

Maintenant avec n = 2 :
a² = 324 = 2² × 3⁴
b² = 144 = 2⁴ × 3²

Pour que b² | a², il faut :

- 2⁴ | 2² : FAUX (4 > 2)

Donc b² ne divise pas a² ✗

Étape 5 : Cherchons mieux

Prenons a = 12 = 2² × 3, b = 18 = 2 × 3²
pgcd = 6, et 18 ne divise pas 12

Avec n = 3 :
a³ = 1728 = 2⁶ × 3³
b³ = 5832 = 2³ × 3⁶

Pour que b³ | a³ :
- 2³ | 2⁶ : OUI (3 ≤ 6) ✓
- 3⁶ | 3³ : NON (6 > 3) ✗

Étape 6 : Contre-exemple qui marche

Prenons a = 2 × 3 = 6, b = 2² × 3 = 12
Ici b ne divise pas a (12 > 6)

Avec n = 2 :
a² = 36 = 2² × 3²
b² = 144 = 2⁴ × 3²

Pour que b² | a² :
- 2⁴ | 2² : NON ✗

Finalement, essayons : a = 2³ × 3 = 24, b = 2 × 3² = 18

18 ne divise pas 24

n=3:
a³ = 13824 = 2⁹ × 3³
b³ = 5832 = 2³ × 3⁶

2³ | 2⁹ : OUI, mais 3⁶ ne divise pas 3³ : NON

Étape 7 : Réponse à la partie a)

Après plusieurs essais, il semble que si bⁿ | aⁿ avec pgcd(a,b) = 1,
alors on doit avoir b = 1.

Mais prenons a = 2², b = 2, n = 2 :

a = 4, b = 2
b | a : OUI (2 divise 4)
Pas un contre-exemple.

Conclusion partie a) : NON, il n'est PAS nécessaire que b | a

Un contre-exemple précis nécessiterait plus d'analyse.
[Note : En pratique, avec des nombres premiers entre eux