Fiche de cours Logimaths | Terminale maths expertes
Fiche de cours : PGCD et nombres premiers
Euclide, Bézout, Gauss : la boîte à outils de l'arithmétique
I. Le PGCD et l'algorithme d'Euclide
PGCD
Le PGCD de deux entiers naturels non nuls a et b est le plus grand entier qui divise à la fois a et b.
Propriété fondamentale : si a = bq + r, alors \text{PGCD}(a\,;\,b) = \text{PGCD}(b\,;\,r) : le PGCD « survit » à la division euclidienne.
Propriété fondamentale : si a = bq + r, alors \text{PGCD}(a\,;\,b) = \text{PGCD}(b\,;\,r) : le PGCD « survit » à la division euclidienne.
L'algorithme d'Euclide
On enchaîne les divisions euclidiennes jusqu'au reste nul : le PGCD est le dernier reste non nul.
Exemple pour PGCD(252 ; 105) :
Exemple pour PGCD(252 ; 105) :
- 252 = 105 × 2 + 42 ;
- 105 = 42 × 2 + 21 ;
- 42 = 21 × 2 + 0 : PGCD = 21.
🎮 Entraîne-toi : l'algorithme d'Euclide
Divise, garde le reste, recommence : le dernier reste non nul gagne.
II. Bézout et Gauss
Théorème de Bézout
a et b sont premiers entre eux (PGCD = 1) ⟺ il existe des entiers u et v tels que : au + bv = 1.
Exemple : 5 × 5 − 8 × 3 = 1 prouve que 5 et 8 sont premiers entre eux. Les coefficients u, v se trouvent en « remontant » l'algorithme d'Euclide.
Exemple : 5 × 5 − 8 × 3 = 1 prouve que 5 et 8 sont premiers entre eux. Les coefficients u, v se trouvent en « remontant » l'algorithme d'Euclide.
Théorème de Gauss
Si a divise le produit bc et si a est premier avec b, alors a divise c.
L'hypothèse « premier avec b » est indispensable : 6 divise 4 × 9 = 36 sans diviser ni 4 ni 9. Conséquence utile : si a et b, premiers entre eux, divisent tous deux n, alors ab divise n (divisible par 3 et par 8 ⟹ divisible par 24).
L'hypothèse « premier avec b » est indispensable : 6 divise 4 × 9 = 36 sans diviser ni 4 ni 9. Conséquence utile : si a et b, premiers entre eux, divisent tous deux n, alors ab divise n (divisible par 3 et par 8 ⟹ divisible par 24).
Résoudre une équation diophantienne ax + by = c
- L'équation a des solutions ⟺ PGCD(a ; b) divise c ;
- on trouve UNE solution particulière (Bézout ou tâtonnement) ;
- on obtient toutes les autres en raisonnant avec Gauss : pour {5x - 8y = 1}, à partir de (5 ; 3) : {x = 5 + 8k,\ y = 3 + 5k}, k entier.
🎮 Entraîne-toi : premiers entre eux ?
PGCD égal à 1 ou pas : Euclide express, ou un diviseur commun évident.
III. Les nombres premiers
Définition et critère de la racine
Un entier p ≥ 2 est premier s'il n'a que deux diviseurs positifs : 1 et lui-même (1 n'est PAS premier ; 2 est le seul premier pair).
Critère d'arrêt : si n n'a aucun diviseur premier \leq \sqrt{n}, alors n est premier. Pour tester 97 : essayer 2, 3, 5, 7 suffit (car \sqrt{97} < 10) : 97 est premier.
Critère d'arrêt : si n n'a aucun diviseur premier \leq \sqrt{n}, alors n est premier. Pour tester 97 : essayer 2, 3, 5, 7 suffit (car \sqrt{97} < 10) : 97 est premier.
▶ 🎓 Démonstration au programme (exigible) : il existe une infinité de nombres premiers (Euclide)
Par l'absurde : supposons qu'il n'y ait qu'un nombre fini de premiers p_1, p_2, \dots, p_r, et posons {N = p_1 p_2 \cdots p_r + 1}.
N ≥ 2 admet au moins un diviseur premier p (tout entier ≥ 2 en a un). Ce p est l'un des p_i, donc p divise le produit p_1 \cdots p_r ; comme il divise aussi N, il divise la différence N − produit = 1 : impossible pour un premier.
Contradiction : les nombres premiers sont en nombre infini. ∎
N ≥ 2 admet au moins un diviseur premier p (tout entier ≥ 2 en a un). Ce p est l'un des p_i, donc p divise le produit p_1 \cdots p_r ; comme il divise aussi N, il divise la différence N − produit = 1 : impossible pour un premier.
Contradiction : les nombres premiers sont en nombre infini. ∎
🎮 Entraîne-toi : premier ou pas ?
Teste les diviseurs premiers jusqu'à la racine carrée, pas au-delà.
IV. Décomposition en facteurs premiers et Fermat
Le théorème fondamental de l'arithmétique
Tout entier n ≥ 2 se décompose de façon unique (à l'ordre près) en produit de facteurs premiers : 360 = 2^3 \times 3^2 \times 5.
Applications : liste des diviseurs (et leur nombre : produit des « exposants + 1 », soit 4 × 3 × 2 = 24 diviseurs pour 360), PGCD par les facteurs communs, simplification de fractions et de racines.
Applications : liste des diviseurs (et leur nombre : produit des « exposants + 1 », soit 4 × 3 × 2 = 24 diviseurs pour 360), PGCD par les facteurs communs, simplification de fractions et de racines.
Le petit théorème de Fermat
Si p est premier et a non divisible par p : a^{p-1} \equiv 1 \;[p].
Version pour tous les entiers a : {a^p \equiv a \;[p]}.
Exemple : \begin{aligned}2^{100} &= (2^{10})^{10} \\ &\equiv 1 \;[11]\end{aligned} car 2^{10} \equiv 1 \;[11] (Fermat avec p = 11). C'est l'un des moteurs du chiffrement RSA.
Version pour tous les entiers a : {a^p \equiv a \;[p]}.
Exemple : \begin{aligned}2^{100} &= (2^{10})^{10} \\ &\equiv 1 \;[11]\end{aligned} car 2^{10} \equiv 1 \;[11] (Fermat avec p = 11). C'est l'un des moteurs du chiffrement RSA.
👆 ▶ À toi : décompose 168 en facteurs premiers et donne son nombre de diviseurs. Vérifie
168 = 2^3 \times 3 \times 7 : (3 + 1)(1 + 1)(1 + 1) = 16 diviseurs.
🎮 Entraîne-toi : la décomposition
Divise par 2 tant que possible, puis par 3, puis par 5 : compte les exposants.