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, la condition est nécessaire]

PARTIE b) : Formule du PGCD

Étape 1 : Décomposition en facteurs premiers Soit a = p₁^α₁ × p₂^α₂ × ... × pₖ^αₖ Soit b = p₁^β₁ × p₂^β₂ × ... × pₖ^βₖ (on
complète par des exposants 0 pour les facteurs manquants)

Étape 2 : PGCD de a et b Par définition : pgcd(a, b) = p₁^(min(α₁,β₁)) × p₂^(min(α₂,β₂)) × ... × pₖ^(min(αₖ,βₖ))

Posons δᵢ = min(αᵢ, βᵢ) pour tout i

Donc : pgcd(a, b) = p₁^δ₁ × p₂^δ₂ × ... × pₖ^δₖ

Étape 3 : Puissances de a et b aⁿ = (p₁^α₁ × ... × pₖ^αₖ)ⁿ = p₁^(nα₁) × ... × pₖ^(nαₖ) bⁿ = (p₁^β₁ × ... × pₖ^βₖ)ⁿ = p₁^(nβ₁) × ...
× pₖ^(nβₖ)

Étape 4 : PGCD des puissances pgcd(aⁿ, bⁿ) = p₁^(min(nα₁, nβ₁)) × ... × pₖ^(min(nαₖ, nβₖ))

Étape 5 : Simplification min(nαᵢ, nβᵢ) = n × min(αᵢ, βᵢ) = n × δᵢ

Explication : Si αᵢ ≤ βᵢ alors nαᵢ ≤ nβᵢ donc min(nαᵢ, nβᵢ) = nαᵢ = n×min(αᵢ, βᵢ) Si αᵢ ≥ βᵢ alors nαᵢ ≥ nβᵢ donc min(nαᵢ, nβᵢ)
= nβᵢ = n×min(αᵢ, βᵢ)

Étape 6 : Résultat final pgcd(aⁿ, bⁿ) = p₁^(nδ₁) × p₂^(nδ₂) × ... × pₖ^(nδₖ) = (p₁^δ₁ × p₂^δ₂ × ... × pₖ^δₖ)ⁿ = [pgcd(a, b)]ⁿ

Étape 7 : Vérification numérique Prenons a = 12 = 2² × 3, b = 18 = 2 × 3², n = 2

pgcd(12, 18) = 2¹ × 3¹ = 6

Méthode 1 (formule) : pgcd(a², b²) = [pgcd(a,b)]² = 6² = 36

Méthode 2 (direct) : a² = 144 = 2⁴ × 3² b² = 324 = 2² × 3⁴ pgcd(144, 324) = 2² × 3² = 4 × 9 = 36 ✓

Conclusion : pgcd(aⁿ, bⁿ) = [pgcd(a, b)]ⁿ

 ---

## 15. PGCD de produits

**Exercices concernés : 15**

### Rappel théorique

**Propriété :** Si pgcd(a, c) = 1 et pgcd(b, d) = 1, alors :
pgcd(ab, cd) = pgcd(a, d) × pgcd(b, c)

**Cas particulier du problème :** Si pgcd(a,c) = 1 et pgcd(b,d) = 1, que vaut pgcd(ab, cd) ?

### Méthodologie détaillée

**Étape 1 : Analyser les facteurs premiers**

- a et c n'ont aucun facteur premier commun
- b et d n'ont aucun facteur premier commun

**Étape 2 : Décomposer ab et cd**

- Les facteurs de ab sont ceux de a et ceux de b
- Les facteurs de cd sont ceux de c et ceux de d

**Étape 3 : Trouver les facteurs communs**

- Un facteur de ab peut venir de a ou de b
- Un facteur de cd peut venir de c ou de d
- Analyser toutes les combinaisons

**Étape 4 : Appliquer les hypothèses**

- pgcd(a,c) = 1 : facteurs de a ≠ facteurs de c
- pgcd(b,d) = 1 : facteurs de b ≠ facteurs de d

### ⚠️ Pièges à éviter

- Bien utiliser TOUTES les hypothèses
- Ne pas oublier de décomposer tous les cas possibles
- Vérifier avec un exemple numérique

### Exercice corrigé : PGCD avec hypothèses croisées

Énoncé : Calculer pgcd(ab, cd) sachant que pgcd(a,c) = 1 et pgcd(b,d) = 1

Étape 1 : Hypothèses

pgcd(a, c) = 1 : a et c sont premiers entre eux

pgcd(b, d) = 1 : b et d sont premiers entre eux
Étape 2 : Décomposition en facteurs premiers Soit p un nombre premier quelconque. Notons :

exp_p(a) = exposant de p dans a (peut être 0)

exp_p(b) = exposant de p dans b
exp_p(c) = exposant de p dans c
exp_p(d) = exposant de p dans d

Étape 3 : Conséquences des hypothèses De pgcd(a,c) = 1 : Pour tout premier p : exp_p(a) = 0 OU exp_p(c) = 0
Explication : p ne peut pas diviser à la fois a et c

De pgcd(b,d) = 1 : Pour tout premier p : exp_p(b) = 0 OU exp_p(d) = 0

Étape 4 : Exposants dans ab et cd exp_p(ab) = exp_p(a) + exp_p(b) exp_p(cd) = exp_p(c) + exp_p(d)

Étape 5 : Calcul de pgcd(ab, cd) exp_p(pgcd(ab, cd)) = min(exp_p(ab), exp_p(cd)) = min(exp_p(a) + exp_p(b), exp_p(c)
+ exp_p(d))

Étape 6 : Analyse par cas Pour un premier p donné, analysons tous les cas possibles :

Cas 1 : exp_p(a) > 0 et exp_p(c) > 0 Impossible car pgcd(a,c) = 1 ✗

Cas 2 : exp_p(b) > 0 et exp_p(d) > 0 Impossible car pgcd(b,d) = 1 ✗

Cas 3 : exp_p(a) > 0, exp_p(c) = 0, exp_p(b) > 0, exp_p(d) = 0 exp_p(ab) = exp_p(a) + exp_p(b) exp_p(cd) = 0 + 0 = 0
min = 0

Cas 4 : exp_p(a) > 0, exp_p(c) = 0, exp_p(b) = 0, exp_p(d) > 0 exp_p(ab) = exp_p(a) + 0 = exp_p(a) exp_p(cd) = 0 +
exp_p(d) = exp_p(d) min = min(exp_p(a), exp_p(d))

Cas 5 : exp_p(a) = 0, exp_p(c) > 0, exp_p(b) > 0, exp_p(d) = 0 exp_p(ab) = 0 + exp_p(b) = exp_p(b) exp_p(cd) =
exp_p(c) + 0 = exp_p(c) min = min(exp_p(b), exp_p(c))

Cas 6 : exp_p(a) = 0, exp_p(c) > 0, exp_p(b) = 0, exp_p(d) > 0 exp_p(ab) = 0 + 0 = 0 exp_p(cd) = exp_p(c) + exp_p(d)
min = 0

Cas 7 : exp_p(a) > 0, exp_p(c) = 0, exp_p(b) = 0, exp_p(d) = 0 exp_p(ab) = exp_p(a) exp_p(cd) = 0 min = 0

Cas 8 : exp_p(a) = 0, exp_p(c) = 0, exp_p(b) > 0, exp_p(d) = 0 exp_p(ab) = exp_p(b) exp_p(cd) = 0 min = 0

Cas 9 : exp_p(a) = 0, exp_p(c) > 0, exp_p(b) = 0, exp_p(d) = 0 exp_p(ab) = 0 exp_p(cd) = exp_p(c) min = 0

Cas 10 : exp_p(a) = 0, exp_p(c) = 0, exp_p(b) = 0, exp_p(d) > 0 exp_p(ab) = 0 exp_p(cd) = exp_p(d) min = 0

Cas 11 : Tous nuls min = 0

Étape 7 : Synthèse Les seuls cas non triviaux sont les cas 4 et 5 :

Cas 4 : contribution de min(exp_p(a), exp_p(d))

Cas 5 : contribution de min(exp_p(b), exp_p(c))

Étape 8 : Conclusion exp_p(pgcd(ab, cd)) = min(exp_p(a), exp_p(d)) + min(exp_p(b), exp_p(c)) = exp_p(pgcd(a,d)) +

exp_p(pgcd(b,c)) = exp_p(pgcd(a,d) × pgcd(b,c))

Donc : pgcd(ab, cd) = pgcd(a,d) × pgcd(b,c)

Étape 9 : Vérification numérique Prenons a = 6 = 2×3, b = 5, c = 7, d = 10 = 2×5

Vérifications des hypothèses : pgcd(6, 7) = 1 ✓ (a et c premiers entre eux) pgcd(5, 10) = 5 ≠ 1 ✗

Reprenons : a = 6 = 2×3, b = 5, c = 7, d = 4 = 2²
pgcd(6, 7) = 1 ✓ pgcd(5, 4) = 1 ✓

Calcul de ab et cd : ab = 6 × 5 = 30 = 2×3×5 cd = 7 × 4 = 28 = 2²×7

pgcd(30, 28) = 2

Avec la formule : pgcd(a,d) = pgcd(6, 4) = 2 pgcd(b,c) = pgcd(5, 7) = 1 pgcd(a,d) × pgcd(b,c) = 2 × 1 = 2 ✓

Réponse : pgcd(ab, cd) = pgcd(a,d) × pgcd(b,c)

---

## 16. Formules avec PGCD et PPCM

**Exercices concernés : 16**

### Rappel théorique

**Notation :**
- a ∧ b = pgcd(a,b)
- a ∨ b = ppcm(a,b)

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

**Propriétés de distributivité :**

- a(b ∨ c) = ab ∨ ac
- (a ∨ b) ∧ (a ∨ c) = a ∨ (b ∧ c)
- (a ∧ b) ∨ (a ∧ c) = a ∧ (b ∨ c)

### Méthodologie détaillée

**Méthode 1 : Par décomposition en facteurs premiers**

**Étape 1 : Décomposer tous les nombres**

**Étape 2 : Appliquer les règles**

- PGCD : min des exposants
- PPCM : max des exposants

**Étape 3 : Vérifier que les deux membres ont les mêmes exposants**

**Méthode 2 : Par propriétés algébriques**

**Étape 1 : Utiliser les propriétés connues**

- Distributivité
- Associativité

**Étape 2 : Manipulations algébriques**

### ⚠️ Pièges à éviter

- PGCD utilise MIN, PPCM utilise MAX
- Bien vérifier pour CHAQUE facteur premier
- Ne pas confondre les opérations × et ∨
 ### Exercice corrigé : Démontrer (a∨b) ∧ (a∨c) = a ∨ (b∧c)

Énoncé : Pour a, b, c entiers naturels non nuls, démontrer que : (a ∨ b) ∧ (a ∨ c) = a ∨ (b ∧ c)

Méthode par décomposition en facteurs premiers :

Étape 1 : Décomposition générale Soit p un nombre premier quelconque Notons α = exp_p(a), β = exp_p(b), γ =
exp_p(c)

Étape 2 : Calcul du membre de gauche

Calcul de (a ∨ b) : exp_p(a ∨ b) = max(α, β)

Calcul de (a ∨ c) : exp_p(a ∨ c) = max(α, γ)

Calcul de (a ∨ b) ∧ (a ∨ c) : exp_p[(a ∨ b) ∧ (a ∨ c)] = min(max(α, β), max(α, γ))

Étape 3 : Calcul du membre de droite

Calcul de (b ∧ c) : exp_p(b ∧ c) = min(β, γ)

Calcul de a ∨ (b ∧ c) : exp_p[a ∨ (b ∧ c)] = max(α, min(β, γ))

Étape 4 : Montrons l'égalité Il faut montrer : min(max(α, β), max(α, γ)) = max(α, min(β, γ))

Analysons par cas selon les valeurs relatives de α, β, γ

Cas 1 : α ≥ β et α ≥ γ Membre gauche : min(max(α,β), max(α,γ)) = min(α, α) = α Membre droit : max(α, min(β,γ)) = α
Égalité vérifiée ✓

Cas 2 : β ≥ α et β ≥ γ (donc max(α,β) = β) Sous-cas 2a : γ ≥ α (donc max(α,γ) = γ) Membre gauche : min(β, γ) Membre
droit : max(α, min(β,γ)) Comme α ≤ γ ≤ β ou α ≤ β ≤ γ : Si β ≤ γ : min(β,γ) = β, et max(α, β) = β ✓ Si γ < β : min(β,γ) =
γ, et comme α ≤ γ : max(α,γ) = γ ✓

Sous-cas 2b : γ < α < β Membre gauche : min(β, α) = α (car max(α,γ) = α) Membre droit : max(α, min(β,γ)) = max(α, γ)
=α✓

Cas 3 : γ ≥ α et γ ≥ β (symétrique au cas 2) Par symétrie des rôles de β et γ, le résultat est vrai ✓

Étape 5 : Vérification complète par analyse de cas Pour tout triplet (α, β, γ), on peut vérifier : min(max(α,β), max(α,γ)) =
max(α, min(β,γ))

Ceci est une identité connue en théorie des treillis.

Étape 6 : Conclusion Puisque l'égalité des exposants est vraie pour tout nombre premier p, les deux membres ont la
même décomposition en facteurs premiers. Donc : (a ∨ b) ∧ (a ∨ c) = a ∨ (b ∧ c)

Étape 7 : Vérification numérique Prenons a = 12 = 2²×3, b = 18 = 2×3², c = 20 = 2²×5

Calcul membre gauche : a ∨ b = ppcm(12, 18) = 2²×3² = 36 a ∨ c = ppcm(12, 20) = 2²×3×5 = 60 (a∨b) ∧ (a∨c) =
pgcd(36, 60)

36 = 2²×3² 60 = 2²×3×5 pgcd = 2²×3 = 12

Calcul membre droit : b ∧ c = pgcd(18, 20) 18 = 2×3² 20 = 2²×5 pgcd(18, 20) = 2

a ∨ (b∧c) = ppcm(12, 2) 12 = 2²×3 2 = 2 ppcm = 2²×3 = 12 ✓

Les deux membres valent 12, l'égalité est vérifiée !

---

## ANNEXE : Rappels théoriques généraux

### Divisibilité
- a divise b (noté a|b) si ∃k ∈ ℤ : b = ak
- Si a|b et b|c alors a|c (transitivité)
- Si a|b et a|c alors a|(ub + vc) pour tous u,v ∈ ℤ

### PGCD
- pgcd(a,b) est le plus grand diviseur commun à a et b
- pgcd(a,b) = pgcd(b, a mod b) (algorithme d'Euclide)
- Théorème de Bézout : ∃u,v ∈ ℤ : au + bv = pgcd(a,b)

### PPCM
- ppcm(a,b) est le plus petit multiple commun à a et b
- a × b = pgcd(a,b) × ppcm(a,b)

### Nombres premiers entre eux

- a et b premiers entre eux ⟺ pgcd(a,b) = 1
- Lemme de Gauss : Si a|bc et pgcd(a,b)=1 alors a|c

### Factorisation
- Tout entier n ≥ 2 s'écrit uniquement : n = p₁^α₁ × ... × pₖ^αₖ
- pgcd : prendre le min des exposants
- ppcm : prendre le max des exposants

### Congruences
- a ≡ b (mod n) si n|(a-b)
- Si a ≡ b (mod n) et c ≡ d (mod n) alors :
- a + c ≡ b + d (mod n)
- a × c ≡ b × d (mod n)

---

## Conseils généraux de résolution

1. **Toujours commencer par écrire ce qu'on cherche clairement**

2. **Identifier le type d'exercice** (calcul, démonstration, contre-exemple...)
3. **Lister les hypothèses et les utiliser toutes**
4. **Pour les démonstrations :**
- Partir des définitions
- Utiliser les propriétés connues
 - Rédiger de manière rigoureuse
5. **Vérifier avec des exemples numériques**
6. **Relire pour vérifier la cohérence**

---

**Bon courage pour vos révisions !**

*Guide créé à partir de la feuille de TD d'arithmétique - Université de Poitiers*# Méthodologie Complète - TD

d'Arithmétique
## Université de Poitiers - L2 Informatique

---

## Table des matières

1. [Décomposition en facteurs premiers](#1-décomposition-en-facteurs-premiers)
2. [Calcul du PGCD](#2-calcul-du-pgcd)
3. [Reconstruction à partir de l'algorithme d'Euclide](#3-reconstruction-à-partir-de-lalgorithme-deuclide)
4. [Trouver des couples (a,b) connaissant PGCD et PPCM](#4-trouver-des-couples-ab-connaissant-pgcd-et-ppcm)
5. [Diviseurs communs à plusieurs nombres](#5-diviseurs-communs-à-plusieurs-nombres)
6. [Problèmes de congruence (restes)](#6-problèmes-de-congruence-restes)
7. [Démonstrations de divisibilité](#7-démonstrations-de-divisibilité)
8. [Nombres premiers entre eux - Propriétés](#8-nombres-premiers-entre-eux---propriétés)
9. [Contre-exemples en arithmétique](#9-contre-exemples-en-arithmétique)
10. [Propriétés structurelles des diviseurs](#10-propriétés-structurelles-des-diviseurs)
11. [Carrés parfaits et nombres premiers entre eux](#11-carrés-parfaits-et-nombres-premiers-entre-eux)
12. [Divisibilité de puissances](#12-divisibilité-de-puissances)
13. [Relations entre PGCD](#13-relations-entre-pgcd)
14. [PGCD de puissances](#14-pgcd-de-puissances)
15. [PGCD de produits](#15-pgcd-de-produits)
16. [Formules avec PGCD et PPCM](#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