PGCD et nombres premiers
Créez un compte gratuit pour suivre votre avancement et reprendre où vous avez laissé.
Créer un compteObjectifs du chapitre
1. PGCD
Définition
Soient $ a $ et $ b $ deux entiers naturels tels que $ a\neq 0 $ ou $ b\neq 0 $.
Le PGCD de $ a $ et de $ b $ est le plus grand diviseur commun à $ a $ et à $ b $.
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.
Remarque
- Si $ b $ divise $ a $, PGCD($ a ; b $) $ = b $. En effet, $ b $ divise alors $ a $ et $ b $, et $ b $ est le plus grand diviseur de $ b $.
En particulier, PGCD($ a ; 1 $) $ = 1 $ et PGCD(0 ; $ b $) $ = b $ - On prolonge la notion de PGCD à des entiers relatifs $ a $ et $ b $ par PGCD($ a ; b $)=PGCD($ |a| ; |b| $).
Théorème
Soient $ a $ et $ b $ deux entiers naturels non nuls et $ r $ le reste de la division euclidienne de $ a $ par $ b $.
Alors : PGCD($ a ; b $) = PGCD($ b ; r $).
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 $ a $ par $ b $ et on note $ r_{1} $ le reste de cette division.
- Puis si $ r_{1}\neq 0 $, on effectue la division euclidienne de $ b $ par $ r_{1} $ et on note $ r_{2} $ le reste de cette division.
- Puis si $ r_{2}\neq 0 $, on effectue la division euclidienne de $ r_{1} $ par $ r_{2} $, et ainsi de suite...
La suite $ r_{0}=b $, $ r_{1} $, $ r_{2} $, ... est strictement décroissante, et pour un certain rang $ n $ on aura $ r_{n}=0 $.
Par conséquent :
PGCD($ a $ ; $ b $) = PGCD($ b $ ; $ r_{0} $) = PGCD($ r_{0} $ ; $ r_{1} $) = ...
$ $= PGCD($ r_{n - 1} $ ; $ r_{n} $) = PGCD($ r_{n - 1} $ ; 0) = $ r_{n - 1} $
Le PGCD de $ a $ et $ b $ 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 $ a $ et $ b $ deux entiers naturels non nuls.
L'ensemble des diviseurs communs à $ a $ et à $ b $ 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 $ a $, $ b $ et $ c $ sont trois entiers non nuls :
- on dit que $ a $, $ b $ et $ c $ sont premiers entre eux dans leur ensemble lorsque le seul diviseur commun à $ a $, $ b $ et $ c $ est 1 ;
- on dit que $ a $, $ b $ et $ c $ sont premiers entre eux deux à deux lorsque PGCD($ a $ ; $ b $) = 1, PGCD($ b $ ; $ c $) = 1 et PGCD($ a $ ; $ c $) = 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 $ a $ et $ b $ deux entiers naturels non nuls.
$ d $ est le PGCD de $ a $ et de $ b $ si et seulement si il existe deux entiers $ a^{\prime} $ et $ b^{\prime} $ premiers entre eux tels que $ a=a^{\prime}d $ et $ b=b^{\prime}d $.
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 $ a $ et $ b $ non nuls sont premiers entre eux si et seulement si il existe deux entiers relatifs $ u $ et $ v $ tels que :
Remarque
Les valeurs de $ u $ et de $ v $ peuvent être obtenues à l'aide de l'algorithme d'Euclide étendu (voir la fiche méthode dédiée).
Exemple
Pour tout entier naturel $ n $, $ 2n+1 $ et $ n $ sont premiers entre eux.
En effet $ 1\times \left(2n+1\right) - 2\times n=1 $. Donc d'après le théorème de Bézout (avec $ u=1 $ et $ v= - 2 $), $ n $ et $ 2n+1 $ sont premiers entre eux.
Propriété
Soient $ a $ et $ b $ deux entiers naturels non nuls et $ d $ leur PGCD.
Alors, il existe deux entiers relatifs $ u $ et $ v $ tels que :
Remarque
Attention, la réciproque est fausse.
Si $ au+bv = d $ on peut seulement en déduire que le PGCD de $ a $ et de $ b $ divise $ d $ (d'après une propriété du chapitre précédent). Par exemple $ 3\times 4+2\times \left( - 5\right)=2 $ mais le PGCD de 3 et de 2 est 1 (ils sont premiers entre eux) et non 2.
Théorème (de Gauss)
Soient $ a $, $ b $ et $ c $ trois entiers naturels non nuls.
- Si $ a $ divise le produit $ bc $
- et si $ a $ est premier avec $ b $,
alors, $ a $ divise $ c $.
Exemple
On cherche tous les couples d'entiers naturels $ \left(m ; n\right) $ tels que $ 5m=3n $.
L'égalité $ 5m=3n $ signifie que $ 5 $ divise $ 3n $. Comme $ 5 $ et $ 3 $ sont premiers entre eux, d'après le théorème de Gauss $ 5 $ divise $ n $. Donc il existe un entier naturel $ k $ tel que $ n=5k $. On a alors $ 5m=3n=15k $ soit $ m=3k $.
Réciproquement, on vérifie aisément que tout couple de la forme $ \left(3k ; 5k\right) $ (où $ k \in \mathbb{N} $) est solution de l'équation proposée.
Propriété
Si $ a $ et $ b $ divisent $ c $ et sont premiers entre eux, alors le produit $ ab $ divise $ c $.
Exemple
D'après cette propriété :
- $ n $ est divisible par 6 si et seulement si il est divisible par 2 et par 3 (car 2 et 3 sont premiers entre eux).
- $ n $ 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 « $ a $ et $ b $ 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 $ \mathbb{N} $) : 1 et lui-même.
Remarque
1 n'est pas un nombre premier (il possède un seul diviseur).
Propriété
- Tout entier naturel $ n > 1 $ admet au moins un diviseur premier.
- Tout entier naturel $ n > 1 $ non premier admet au moins un diviseur premier inférieur ou égal à $ \sqrt{n} $.
Remarque
La seconde propriété est souvent utilisée pour démontrer (par l'absurde) qu'un entier naturel $ n $ est premier. Il suffit, en effet, de montrer que $ n $ n'est divisible par aucun nombre premier $ p $ inférieur ou égal à $ \sqrt{n} $. On peut donc arrêter la recherche de diviseurs premiers $ p $ dès que $ p^{2} > n $.
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 $ 7 > \sqrt{41} $) : 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 $ p $.
On pose $ N=2\times 3\times 5\times \cdots \times p $ (produit de tous les nombres premiers).
Comme tout entier naturel supérieur à 1 admet au moins un diviseur premier, $ N+1 $ admet un diviseur premier $ d $.
Or $ d $ divise aussi le nombre $ N $ puisque $ N $ est le produit de tous les nombres premiers.
$ d $ divise $ N+1 $ et $ N $, donc il divise leur différence 1, ce qui est impossible.
Propriété
Si $ p $ est un nombre premier et $ a $ un entier naturel non nul non divisible par $ p $, alors $ p $ et $ a $ sont premiers entre eux.
Propriété
Soient $ a $ et $ b $ deux entiers naturels non nuls.
Si un nombre premier $ p $ divise le produit $ ab $, alors $ p $ divise $ a $ ou $ b $.
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 $ n > 1 $ se décompose en produit de nombres premiers.
Cette décomposition peut s'écrire :
où les $ p_{i} $ sont des nombres premiers distincts et les $ a_{i} $ 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 $ 60=2^{2}\times 3\times 5 $.
Propriété
Soit $ n $ un entier naturel supérieur à 1 dont la décomposition en facteurs premiers s'écrit $ n=p_{1}^{a_{1}}p_{2}^{a_{2}}\cdots p_{k}^{a_{k}} $.
Alors, les diviseurs de $ n $ sont les entiers de la forme :
avec $ 0 \leqslant b_{i} \leqslant a_{i} $ pour tout $ 0 \leqslant i \leqslant k $.
Exemple
$ 60=2^{2}\times 3\times 5 $ admet comme diviseurs les nombres de la forme $ 2^{b_{1}}\times 3^{b_{2}}\times 5^{b_{3}} $ avec $ 0 \leqslant b_{1} \leqslant 2 $, $ 0 \leqslant b_{2} \leqslant 1 $ et $ 0 \leqslant b_{3} \leqslant 1 $.
Il y a trois valeurs possibles pour $ b_{1} $ et deux valeurs possibles pour $ b_{2} $ et pour $ b_{3} $. Au total, $ 60 $ possède donc $ 3\times 2\times 2=12 $ diviseurs (en comptant $ 1 $ et lui-même).
3. Petit théorème de Fermat
Petit théorème de Fermat
Soit $ p $ un nombre premier.
- Pour tout entier $ a $ non divisible par $ p $ : $ a^{p - 1}\equiv 1 \pmod p $.
- Pour tout entier $ a $ : $ a^{p}\equiv a \pmod p $.
Démonstration
On démontre la première forme. Soit $ p $ un nombre premier et $ a $ un entier non divisible par $ p $.
On considère les $ p - 1 $ multiples $ a $, $ 2a $, $ 3a $, ..., $ \left(p - 1\right)a $ et on étudie leurs restes modulo $ p $.
Aucun de ces multiples n'est divisible par $ p $ : si $ p $ divisait $ ka $ (avec $ 1 \leqslant k \leqslant p - 1 $), comme $ p $ est premier il diviserait $ k $ ou $ a $, ce qui est impossible puisque $ 1 \leqslant k \leqslant p - 1 $ et que $ a $ n'est pas divisible par $ p $. Leurs restes modulo $ p $ sont donc tous compris entre $ 1 $ et $ p - 1 $.
De plus ces restes sont deux à deux distincts. En effet, si $ ia\equiv ja \pmod p $ avec $ 1 \leqslant i \leqslant j \leqslant p - 1 $, alors $ p $ divise $ \left(j - i\right)a $ ; comme $ p $ est premier avec $ a $, le théorème de Gauss donne que $ p $ divise $ j - i $, donc $ i=j $ (car $ 0 \leqslant j - i \leqslant p - 2 $).
Les $ p - 1 $ restes sont donc $ p - 1 $ entiers distincts de $ \left\{1 ; 2 ; \dots ; p - 1\right\} $ : ce sont exactement les entiers $ 1, 2, \dots, p - 1 $ dans un certain ordre. En multipliant toutes ces congruences, on obtient :
soit $ \left(p - 1\right)!\times a^{p - 1}\equiv \left(p - 1\right)! \pmod p $.
Or $ \left(p - 1\right)! $ est un produit de facteurs tous compris entre $ 1 $ et $ p - 1 $, donc premier avec $ p $. D'après le théorème de Gauss, on peut « simplifier » par $ \left(p - 1\right)! $ et il reste :
Enfin, en multipliant cette congruence par $ a $, on obtient $ a^{p}\equiv a \pmod p $ ; cette seconde forme reste d'ailleurs valable lorsque $ p $ divise $ a $, car les deux membres sont alors congrus à $ 0 $ modulo $ p $.
Exemple
On cherche le reste de la division euclidienne de $ 3^{100} $ par $ 7 $.
Le nombre $ 7 $ est premier et ne divise pas $ 3 $. D'après le petit théorème de Fermat :
On écrit alors $ 100 $ comme multiple de $ 6 $ augmenté d'un reste : $ 100=6\times 16+4 $. Ainsi :
Comme $ 3^{4}=81=7\times 11+4 $, on a $ 3^{4}\equiv 4 \pmod 7 $. Le reste cherché est donc $ \mathbf{4} $.
Remarque
La réciproque du petit théorème de Fermat est fausse : il existe des entiers $ n $ non premiers vérifiant $ a^{n - 1}\equiv 1 \pmod n $ pour certaines bases $ a $ (ces entiers sont appelés pseudo-premiers). Le théorème ne fournit donc pas, à lui seul, un test de primalité ; en revanche il est très utile pour calculer rapidement des restes de puissances modulo un nombre premier.
Les questions essentielles
1. Comment calculer le PGCD de deux entiers ?
L'algorithme d'Euclide enchaîne des divisions euclidiennes successives jusqu'à obtenir un reste nul. Le PGCD est alors le dernier reste non nul.
Voir la fiche méthode : Calcul du PGCD - Algorithme d'Euclide
2. Comment trouver les coefficients de Bézout u et v tels que au+bv=PGCD(a,b) ?
L'algorithme d'Euclide étendu suit les divisions euclidiennes en exprimant chaque reste comme combinaison linéaire de $ a $ et $ b $. Le dernier reste non nul donne directement les coefficients $ u $ et $ v $.
Voir la fiche méthode : Algorithme d'Euclide étendu
3. Comment décomposer un entier en produit de facteurs premiers ?
On teste la divisibilité par les nombres premiers dans l'ordre croissant ($ 2 $, $ 3 $, $ 5 $, $ 7 $...) en divisant le nombre à chaque facteur trouvé, jusqu'à obtenir $ 1 $. La décomposition s'écrit ensuite avec des exposants.
Voir la fiche méthode : Décomposer un entier en produit de facteurs premiers
4. Comment démontrer qu'un entier est premier ?
Il suffit de vérifier qu'il n'admet aucun diviseur premier inférieur ou égal à $ \sqrt{n} $. On limite ainsi la recherche à un petit nombre de tests.
Voir la fiche méthode : Démontrer qu'un entier est premier
5. Comment résoudre une équation diophantienne ax+by=c ?
L'équation a des solutions entières si et seulement si le PGCD de $ a $ et $ b $ divise $ c $. On trouve alors une solution particulière puis on utilise le théorème de Gauss pour décrire toutes les solutions.
Voir la fiche méthode : Résoudre une équation diophantienne ax+by=c
6. Comment trouver tous les nombres premiers jusqu'à un entier donné ?
Le crible d'Ératosthène consiste à lister les entiers puis à éliminer, de proche en proche, les multiples de chaque nombre premier rencontré. Les nombres non barrés sont les nombres premiers.
Voir la fiche méthode : Appliquer le crible d'Eratosthene