PGCD et nombres premiers
1. PGCD
Définition
Soient et deux entiers naturels tels que ou .
Le PGCD de et de est le plus grand diviseur commun à et à .
Exemple
On cherche le PGCD de 60 et de 45.
Les diviseurs de 60 sont : 1; 2; 3; 4; 5; 6; 10; 12; 15; 20; 30 et 60.
Les diviseurs de 45 sont : 1; 3; 5; 9; 15 et 45.
Les diviseurs communs à 60 et 45 sont : 1; 3; 5 et 15.
Donc le PGCD de 60 et 45 est 15.
Remarques
Si divise , PGCD() . En effet, divise alors et , et est le plus grand diviseur de .
En particulier, PGCD() et PGCD(0 ; )
On prolonge la notion de PGCD à des entiers relatifs et par PGCD()=PGCD().
Théorème
Soient et deux entiers naturels non nuls et le reste de la division euclidienne de par .
Alors : PGCD() = PGCD().
Exemple
Le reste de la division euclidienne de 60 par 45 est 15. donc PGCD(60 ; 45) = PGCD(45 ; 15).
Si l'on réitère le processus, le reste de la division euclidienne de 45 par 15 est 0 donc PGCD(45 ; 15) = PGCD(15 ; 0) = 15.
Algorithme d'Euclide
On effectue la division euclidienne de par et on note le reste de cette division.
Puis si , on effectue la division euclidienne de par et on note le reste de cette division.
Puis si , on effectue la division euclidienne de par , et ainsi de suite...
La suite , , , ... est strictement décroissante, et pour un certain rang on aura .
Par conséquent :
PGCD( ; ) = PGCD( ; ) = PGCD( ; ) = ...
= PGCD( ; ) = PGCD( ; 0) =
Le PGCD de et est donc le dernier reste non nul dans cette suite.
Exemple
On cherche à déterminer le PGCD de 2691 et de 1404.
le reste de la division euclidienne de 2691 par 1404 est 1287,
le reste de la division euclidienne de 1404 par 1287 est 117,
le reste de la division euclidienne de 1287 par 117 est 0.
Par conséquent PGCD(2691 ; 1404) = 117.
Propriété
Soient et deux entiers naturels non nuls.
L'ensemble des diviseurs communs à et à est l'ensemble des diviseurs de leur PGCD.
Définition
On dit que deux entiers naturels non nuls sont premiers entre eux si leur PGCD est égal à 1.
Remarque
On peut généraliser cette notion à plus de deux entiers de deux façons différentes.
Si , et sont trois entiers non nuls :
on dit que , et sont premiers entre eux dans leur ensemble lorsque le seul diviseur commun à , et est 1 ;
on dit que , et sont premiers entre eux deux à deux lorsque PGCD( ; ) = 1, PGCD( ; ) = 1 et PGCD( ; ) = 1.
Par exemple 4 , 6 et 9 sont premiers entre eux dans leur ensemble (pas de diviseur commun à ces trois nombres autre que 1) mais ne sont pas premiers entre eux deux à deux puisque PGCD(4 ; 6) = 2 et PGCD(6 ; 9) = 3.
Propriété
Soient et deux entiers naturels non nuls.
est le PGCD de et de si et seulement si il esiste deux entiers et premiers entre eux tels que et .
Exemple
Le PGCD de 60 et de 45 est 15. On a :
60 = 4×15 et 45 = 3×15 et 4 et 3 sont premiers entre eux.
Théorème (de Bézout)
Deux entiers naturels et non nuls sont premiers entre eux si et seulement si il existe deux entiers relatifs et tels que :
.
Remarque
Les valeurs de et de peuvent être obtenues à l'aide de l'algorithme d'Euclide (fiche méthode à venir...)
Exemple
Pour tout entier naturel , et sont premiers entre eux.
En effet . Donc d'après le théorème de Bézout (avec et ), et sont premiers entre eux.
Propriété
Soient et deux entiers naturels non nuls et leur PGCD.
Alors, il existe deux entiers relatifs et tels que :
.
Remarque
Attention, la réciproque est fausse.
Si on peut seulement en déduire que le PGCD de et de divise (d'après une propriété du chapitre précédent). Par exemple mais le PGCD de 3 et de 2 est 1 (ils sont premiers entre eux) et non 2.
Théorème (de Gauss)
Soient , et trois entiers naturels non nuls.
Si divise le produit
et si est premier avec ,
alors, divise .
Exemple
On cherche tous les couples d'entiers naturels tels que .
L'égalité signifie que divise . Comme et sont premiers entre eux, d'après le théorème de Gauss divise . Donc il existe un entier naturel tel que . On a alors soit .
Réciproquement, on vérifie aisément que tout couple de la forme (où ) est solution de l'équation proposée.
Propriété
Si et divisent et sont premiers entre eux, alors le produit divise .
Exemples
D'après cette propriété :
est divisible par 6 si et seulement si il est divisible par 2 et par 3 (car 2 et 3 sont premiers entre eux).
est divisible par 15 si et seulement si il est divisible par 3 et par 5 (car 3 et 5 sont premiers entre eux).
Remarque
L'hypothèse « et sont premiers entre eux » est essentielle. Par exemple 90 est divisible par 6 et par 10 mais n'est pas divisible par 6×10 = 60.
2. Nombres premiers
Définition
Un entier naturel est premier s'il admet exactement deux diviseurs (dans ) : 1 et lui-même.
Remarque
1 n'est pas un nombre premier (il possède un seul diviseur).
Propriétés
Tout entier naturel admet au moins un diviseur premier.
Tout entier naturel non premier admet au moins un diviseur premier inférieur ou égal à .
Remarque
La seconde propriété est souvent utilisée pour démontrer (par l'absurde) qu'un entier naturel est premier. Il suffit, en effet, de montrer que n'est divisible par aucun nombre premier inférieur ou égal à . On peut donc arrêter la recherche de diviseurs premiers dès que .
Exemple
41 est-il premier ?
41 n'est pas divisible par 2 (dernier chiffre impair),
41 n'est pas divisible par 3 (somme des chiffres 4+1=5),
41 n'est pas divisible par 5 (dernier chiffre différent de 0 et de 5),
7²=49 > 41 (donc ) : inutile de chercher plus loin...
Conclusion : 41 est un nombre premier.
Propriété
Il existe une infinité de nombres premiers.
Démonstration
On raisonne par l'absurde en supposant que l'ensemble des nombres premiers n'est pas infini. Il existe alors un plus grand nombre premier .
On pose (produit de tous les nombres premiers).
Comme tout entier naturel supérieur à 1 admet au moins un diviseur premier, admet un diviseur premier .
Or divise aussi le nombre puisque est le produit de tous les nombres premiers.
divise et , donc il divise leur différence 1, ce qui est impossible.
Propriété
Si est un nombre premier et un entier naturel non nul non divisible par , alors et sont premier entre eux.
Propriété
Soient et deux entiers naturels non nuls.
Si un nombre premier divise le produit , alors divise ou .
Remarque
Cette propriété résulte immédiatement de la propriété précédente et du théorème de Gauss.
Théorème (théorème fondamental de l'arithmétique)
Tout entier naturel se décompose en produit de nombres premiers.
Cette décomposition peut s'écrire :
où les sont des nombres premiers distincts et les des entiers naturels non nuls.
Cette décomposition est unique à l'ordre près des facteurs.
Exemple
Cherchons la décomposition de 60 en facteurs premiers.
60 est divisible par 2 et le quotient de cette division est 30.
30 est divisible par 2 et le quotient est 15.
15 est divisible par 3 et le quotient est 5.
Enfin, 5 est premier.
Donc .
Propriété
Soit un entier naturel supérieur à 1 dont la décomposition en facteurs premiers s'écrit .
Alors, les diviseurs de sont les entiers de la forme :
avec pour tout .
Exemple
admet comme diviseurs les nombres de la forme avec , et .
Il y a trois valeurs possibles pour et deux valeurs possibles pour et pour . Au total, possède donc diviseurs (en comptant et lui-même).