Nombres premiers, PGCD & PPCM

1

Divisibilité

📖 Théorème — Division euclidienne de a par b

Pour tous entiers a ∈ ℤ et b ∈ ℕ*, il existe un unique couple d'entiers (q, r) tels que :

a = b \times q + r avec 0 \leq r < b

a = dividende

b = diviseur

q = quotient

r = reste (0 ≤ r < b)

Exemple : Division de 17 par 5 : 17 = 5 × 3 + 2 (q = 3, r = 2)

📖 Définition — Divisibilité

On dit que b divise a (noté b | a) lorsque le reste de la division euclidienne de a par b est nul, c'est-à-dire lorsque :

a = b \times q (r = 0)

• b est un diviseur de a | a est un multiple de b

3 | 12 car 12 = 3 × 4 + 0 ✓

5 ∤ 17 car 17 = 5 × 3 + 2, reste ≠ 0 ✗

Diviseurs de 12 : 1, 2, 3, 4, 6, 12

📖 Remarque — Définition algébrique équivalente

On dit que a divise b (noté a | b) s'il existe un entier k tel que b = a × k.

a | b ⟺ b = a \times k pour un certain k \in ℤ

Cette définition est équivalente : si r = 0 dans la division euclidienne, alors b = a × q, et on pose k = q.

📌 Propriétés fondamentales

1️⃣

1 divise tous les entiers | Tout entier est divisible par 1 et par lui-même

0️⃣

0 est divisible par tous les entiers non nuls (car 0 = a × 0)

🔗

Transitivité : si a | b et b | c, alors a | c

📌 Critères de divisibilité — À connaître !

2

Le chiffre des unités est 0, 2, 4, 6 ou 8 (chiffre pair)

148 ✓ | 375 ✗

3

La somme des chiffres est divisible par 3

1 + 2 + 6 = 9 → 126 ÷ 3 ✓
2 + 5 = 7 → 25 ÷ 3 ✗

4

Les deux derniers chiffres forment un nombre divisible par 4

1 24 ÷ 4 = 6 ✓
18 ÷ 4 → reste 2 ✗

5

Le chiffre des unités est 0 ou 5

345 ✓ | 1 230 ✓
137 ✗

6

Divisible par 2 ET par 3 simultanément

126 → pair ✓, 1+2+6=9 ✓ → ÷ 6 ✓
124 → 1+2+4=7 ✗

9

La somme des chiffres est divisible par 9

2 + 8 + 8 = 18 → 288 ÷ 9 ✓
1 + 2 + 5 = 8 ✗

10

Le chiffre des unités est 0

480 ✓ | 135 ✗

25

Les deux derniers chiffres forment 00, 25, 50 ou 75

4 75 ✓ | 3 50 ✓
1 23 ✗

🎮 Vérificateur de divisibilité

Nombre =

2

Nombres premiers

📖 Définition

Un nombre entier naturel est premier s'il possède exactement deux diviseurs distincts : 1 et lui-même.

✅ Premiers

2 (div: 1,2) 3 (div: 1,3) 5 (div: 1,5) 7 (div: 1,7) 11 (div: 1,11)

❌ Composés

4 = 2×2 6 = 2×3 9 = 3×3 15 = 3×5

⚠️ Cas particuliers

1 n'est pas premier (1 seul diviseur)
0 n'est pas premier

📌 Méthode — Tester si n est premier

Tester uniquement les diviseurs de 2 jusqu'à √n. Si aucun ne divise n → n est premier.

29 est premier ?

√29 ≈ 5,4 → tester 2, 3, 4, 5
Aucun ne divise 29 → Premier ✓

51 est premier ?

51 ÷ 3 = 17 → 51 = 3 × 17
Non premier ✗

📊 Nombres premiers jusqu'à 100 (25 nombres)

Cliquer sur un nombre pour voir s'il est premier. ■ Premier □ Composé

🧠 À retenir : 2 est le seul nombre premier pair | Il existe une infinité de nombres premiers | 1 n'est pas premier

3

Décomposition en facteurs premiers

📌 Théorème fondamental de l'arithmétique

Tout entier naturel ≥ 2 peut s'écrire de manière unique (à l'ordre près) comme un produit de nombres premiers.

🔧 Méthode — Arbre de décomposition

①

Diviser le nombre par le plus petit nombre premier qui le divise (en général 2)

②

Répéter avec le quotient obtenu

③

Arrêter quand le quotient est 1

④

Écrire le produit de tous les facteurs utilisés, avec des puissances

✏️ Décomposition de 360 et 84

360	\|	2
180	\|	2
90	\|	2
45	\|	3
15	\|	3
5	\|	5
1

360 = 2³ × 3² × 5

84	\|	2
42	\|	2
21	\|	3
7	\|	7
1

84 = 2² × 3 × 7

225	\|	3
75	\|	3
25	\|	5
5	\|	5
1

225 = 3² × 5²

📌 Compter les diviseurs d'un nombre

Si n = p₁^α₁ × p₂^α₂ × … × pₖ^αₖ, alors le nombre de diviseurs de n est :

(α₁ + 1) \times (α₂ + 1) \times \dots \times (αₖ + 1)

60 = 2² × 3 × 5 → nombre de diviseurs : (2+1)×(1+1)×(1+1) = 12 diviseurs

🎮 Décomposer un nombre en facteurs premiers

n =

4

PGCD

📖 Plus Grand Commun Diviseur

Le PGCD(a, b) est le plus grand entier qui divise à la fois a et b.

Diviseurs de 12 : 1, 2, 3, 4, 6, 12 Diviseurs de 18 : 1, 2, 3, 6, 9, 18 Diviseurs communs : 1, 2, 3, 6 \to PGCD(12, 18) = 6

Si PGCD(a, b) = 1 → a et b sont premiers entre eux

PGCD — Facteurs communs

Plus petit exposant

72 = 2³ × 3²
108 = 2² × 3³
PGCD = 2² × 3² = 36

Prendre le MIN des exposants pour chaque facteur commun

PPCM — Tous les facteurs

Plus grand exposant

72 = 2³ × 3²
108 = 2² × 3³
PPCM = 2³ × 3³ = 216

Prendre le MAX des exposants pour chaque facteur

✏️ Méthode 3 — Algorithme d'Euclide : PGCD(84, 36)

1

84 = 36 × 2 + 12 (reste 12)

2

36 = 12 × 3 + 0 (reste 0)

✓

Le dernier reste non nul est 12 → PGCD(84, 36) = 12

📌 Propriétés du PGCD

↔️

PGCD(a, b) = PGCD(b, a) (commutatif)

0️⃣

PGCD(a, 0) = a | PGCD(a, 1) = 1

÷

Si a | b, alors PGCD(a, b) = a

🔗

Relation fondamentale : PGCD(a,b) × PPCM(a,b) = a × b

5

PPCM

📖 Plus Petit Commun Multiple

Le PPCM(a, b) est le plus petit entier non nul qui est à la fois multiple de a et de b.

Multiples de 4 : 4, 8, 12, 16, 20, 24 \dots Multiples de 6 : 6, 12, 18, 24, 30\dots \to PPCM(4, 6) = 12

📌 Formule rapide

PPCM(a, b) = a \times b / PGCD(a, b)

PPCM(24, 36) = 24 × 36 / PGCD(24, 36) = 864 / 12 = 72

📌 Propriétés du PPCM

↔️

PPCM(a, b) = PPCM(b, a)

1️⃣

PPCM(a, 1) = a

÷

Si a | b, alors PPCM(a, b) = b

🔗

PPCM ≥ a et PPCM ≥ b toujours

📊 Tableau des applications pratiques

Problème	Outil à utiliser
Partage en lots identiques (maximum)	PGCD → nombre de lots
Simplification de fractions	PGCD → diviser num. et dén.
Carrelage, pavage (plus petite surface)	PPCM → côté du carré
Synchronisation, rendez-vous (prochaine coïncidence)	PPCM → moment de rencontre
Preuves sur les entiers	Premiers entre eux : PGCD = 1

6

Simulateur & Applications

🎮 Calculateur PGCD / PPCM

a =

b =

🍫Exercice — Partage de chocolats et bonbons

48 chocolats et 72 bonbons. Sachets identiques au maximum.

1

48 = 2⁴ × 3 | 72 = 2³ × 3²

2

PGCD(48, 72) = 2³ × 3 = 24 sachets

3

48/24 = 2 chocolats et 72/24 = 3 bonbons par sachet

🚌Exercice — Synchronisation de bus (12 min et 18 min)

Deux bus partent ensemble. Quand se retrouveront-ils ?

1

12 = 2² × 3 | 18 = 2 × 3²

2

PPCM = 2² × 3² = 36 minutes

🌹Exercice — Bouquets (56 roses, 84 œillets)

1

56 = 2³ × 7 | 84 = 2² × 3 × 7

2

PGCD(56, 84) = 2² × 7 = 28 bouquets

3

56/28 = 2 roses et 84/28 = 3 œillets par bouquet

🧠 Aide-mémoire final

🔢

Nombre premier : exactement 2 diviseurs (1 et lui-même). 2 est le seul premier pair. 1 n'est pas premier.

📐

PGCD : facteurs communs avec le plus petit exposant | PGCD = 1 → premiers entre eux

📏

PPCM : tous les facteurs avec le plus grand exposant | PPCM = a×b / PGCD

🔗

Relation : PGCD(a,b) × PPCM(a,b) = a × b (toujours vérifier !)