Maths-cours

COURS & EXERCICES DE MATHÉMATIQUES

Close

PGCD et nombres premiers

1. PGCD

Définition

Soient aa et bb deux entiers naturels tels que a0a\neq 0 ou b0b\neq 0.

Le PGCD de aa et de bb est le plus grand diviseur commun à aa et à bb.

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 bb divise aa, PGCD(a;ba ; b) =b= b. En effet, bb divise alors aa et bb, et bb est le plus grand diviseur de bb.

    En particulier, PGCD(a;1a ; 1) =1= 1 et PGCD(0 ; bb) =b= b

  • On prolonge la notion de PGCD à des entiers relatifs aa et bb par PGCD(a;ba ; b)=PGCD(a;b|a| ; |b|).

Théorème

Soient aa et bb deux entiers naturels non nuls et rr le reste de la division euclidienne de aa par bb.

Alors : PGCD(a;ba ; b) = PGCD(b;rb ; 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 aa par bb et on note r1r_{1} le reste de cette division.

  • Puis si r10r_{1}\neq 0, on effectue la division euclidienne de bb par r1r_{1} et on note r2r_{2} le reste de cette division.

  • Puis si r20r_{2}\neq 0, on effectue la division euclidienne de r1r_{1} par r2r_{2}, et ainsi de suite...

La suite r0=br_{0}=b, r1r_{1}, r2r_{2}, ... est strictement décroissante, et pour un certain rang nn on aura rn=0r_{n}=0.

Par conséquent :

PGCD(aa ; bb) = PGCD(bb ; r0r_{0}) = PGCD(r0r_{0} ; r1r_{1}) = ...

= PGCD(rn1r_{n - 1} ; rnr_{n}) = PGCD(rn1r_{n - 1} ; 0) = rn1r_{n - 1}

Le PGCD de aa et bb 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 aa et bb deux entiers naturels non nuls.

L'ensemble des diviseurs communs à aa et à bb 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 aa, bb et cc sont trois entiers non nuls :

  • on dit que aa, bb et cc sont premiers entre eux dans leur ensemble lorsque le seul diviseur commun à aa, bb et cc est 1 ;

  • on dit que aa, bb et cc sont premiers entre eux deux à deux lorsque PGCD(aa ; bb) = 1, PGCD(bb ; cc) = 1 et PGCD(aa ; cc) = 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 aa et bb deux entiers naturels non nuls.

dd est le PGCD de aa et de bb si et seulement si il esiste deux entiers aa^{\prime} et bb^{\prime} premiers entre eux tels que a=ada=a^{\prime}d et b=bdb=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 aa et bb non nuls sont premiers entre eux si et seulement si il existe deux entiers relatifs uu et vv tels que :

au+bv=1au+bv = 1.

Remarque

Les valeurs de uu et de vv peuvent être obtenues à l'aide de l'algorithme d'Euclide (fiche méthode à venir...)

Exemple

Pour tout entier naturel nn, 2n+12n+1 et nn sont premiers entre eux.

En effet 1×(2n+1)2×n=11\times \left(2n+1\right) - 2\times n=1. Donc d'après le théorème de Bézout (avec u=1u=1 et v=2v= - 2), nn et 2n+12n+1 sont premiers entre eux.

Propriété

Soient aa et bb deux entiers naturels non nuls et dd leur PGCD.

Alors, il existe deux entiers relatifs uu et vv tels que :

au+bv=dau+bv = d.

Remarque

Attention, la réciproque est fausse.

Si au+bv=dau+bv = d on peut seulement en déduire que le PGCD de aa et de bb divise dd (d'après une propriété du chapitre précédent). Par exemple 3×4+2×(5)=23\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 aa, bb et cc trois entiers naturels non nuls.

  • Si aa divise le produit bcbc

  • et si aa est premier avec bb,

alors, aa divise cc.

Exemple

On cherche tous les couples d'entiers naturels (m;n)\left(m ; n\right) tels que 5m=3n5m=3n.

L'égalité 5m=3n5m=3n signifie que 55 divise 3n3n. Comme 55 et 33 sont premiers entre eux, d'après le théorème de Gauss 55 divise nn. Donc il existe un entier naturel kk tel que n=5kn=5k. On a alors 5m=3n=15k5m=3n=15k soit m=3km=3k.

Réciproquement, on vérifie aisément que tout couple de la forme (3k;5k)\left(3k ; 5k\right) (où kNk \in \mathbb{N}) est solution de l'équation proposée.

Propriété

Si aa et bb divisent cc et sont premiers entre eux, alors le produit abab divise cc.

Exemples

D'après cette propriété :

  • nn est divisible par 6 si et seulement si il est divisible par 2 et par 3 (car 2 et 3 sont premiers entre eux).

  • nn 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 « aa et bb 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 N\mathbb{N}) : 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 n>1n > 1 admet au moins un diviseur premier.

  • Tout entier naturel n>1n > 1 non premier admet au moins un diviseur premier inférieur ou égal à n\sqrt{n}.

Remarque

La seconde propriété est souvent utilisée pour démontrer (par l'absurde) qu'un entier naturel nn est premier. Il suffit, en effet, de montrer que nn n'est divisible par aucun nombre premier pp inférieur ou égal à n\sqrt{n}. On peut donc arrêter la recherche de diviseurs premiers pp dès que p2>np^{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>417 > \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 pp.

On pose N=2×3×5××pN=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+1N+1 admet un diviseur premier dd.

Or dd divise aussi le nombre NN puisque NN est le produit de tous les nombres premiers.

dd divise N+1N+1 et NN, donc il divise leur différence 1, ce qui est impossible.

Propriété

Si pp est un nombre premier et aa un entier naturel non nul non divisible par pp, alors pp et aa sont premier entre eux.

Propriété

Soient aa et bb deux entiers naturels non nuls.

Si un nombre premier pp divise le produit abab, alors pp divise aa ou bb.

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>1n > 1 se décompose en produit de nombres premiers.

Cette décomposition peut s'écrire :

n=p1a1p2a2pkakn=p_{1}^{a_{1}}p_{2}^{a_{2}}\cdots p_{k}^{a_{k}}

où les pip_{i} sont des nombres premiers distincts et les aia_{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=22×3×560=2^{2}\times 3\times 5.

Propriété

Soit nn un entier naturel supérieur à 1 dont la décomposition en facteurs premiers s'écrit n=p1a1p2a2pkakn=p_{1}^{a_{1}}p_{2}^{a_{2}}\cdots p_{k}^{a_{k}}.

Alors, les diviseurs de nn sont les entiers de la forme :

n=p1b1p2b2pkbkn=p_{1}^{b_{1}}p_{2}^{b_{2}}\cdots p_{k}^{b_{k}}

avec 0biai0 \leqslant b_{i} \leqslant a_{i} pour tout 0ik0 \leqslant i \leqslant k.

Exemple

60=22×3×560=2^{2}\times 3\times 5 admet comme diviseurs les nombres de la forme 2b1×3b2×5b32^{b_{1}}\times 3^{b_{2}}\times 5^{b_{3}} avec 0b120 \leqslant b_{1} \leqslant 2, 0b210 \leqslant b_{2} \leqslant 1 et 0b310 \leqslant b_{3} \leqslant 1.

Il y a trois valeurs possibles pour b1b_{1} et deux valeurs possibles pour b2b_{2} et pour b3b_{3}. Au total, 6060 possède donc 3×2×2=123\times 2\times 2=12 diviseurs (en comptant 11 et lui-même).