📘 Fiche de révision – Arithmétique (L1)
1️⃣ Divisibilité et nombres premiers
Un entier a divise un entier b s’il existe un entier k tel que :
b = a × k
Un nombre est premier s’il admet exactement deux diviseurs : 1 et lui-même.
2️⃣ Décomposition en facteurs premiers
Tout entier ≥ 2 peut s’écrire comme produit de nombres premiers.
Exemple
1155 = 3 × 5 × 7 × 11
Cette décomposition permet de trouver :
- les diviseurs
- le PGCD
- le PPCM
3️⃣ PGCD – Algorithme d’Euclide
Le PGCD de deux entiers est le plus grand diviseur commun.
Méthode
On effectue des divisions successives jusqu’à obtenir un reste nul.
Exemple corrigé
43 = 16 × 2 + 11
16 = 11 × 1 + 5
11 = 5 × 2 + 1
5 = 1 × 5 + 0
PGCD(43,16) = 1
4️⃣ PPCM
Le PPCM de deux entiers se calcule à partir du PGCD :
PPCM(a,b) = (a × b) / PGCD(a,b)
Exemple
PPCM(6234,3312) = (6234 × 3312) / 6 = 3 441 168
5️⃣ Problème type (divisibilité)
Une machine emballe des pièces dans des sacs de taille fixe.
7875 et 59125 sont des multiples du nombre de pièces par sac p.
Donc p divise leur PGCD.
PGCD(7875, 59125) = 125
Chaque sac contient 125 pièces.
6️⃣ Inverse modulo
L’inverse de e modulo p est un entier d tel que :
e × d ≡ 1 (mod p)
Exemple
149 = 7 × 21 + 2
21 = 10 × 2 + 1
En remontant l’algorithme :
1 = 71 × 21 − 10 × 149
L’inverse de 21 modulo 149 est 71.
7️⃣ À retenir pour l’examen
- Utiliser Euclide pour PGCD
- PPCM via PGCD
- Décomposition en facteurs premiers = outil central
- Inverse modulo ⇔ PGCD = 1