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.
Remarques
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 esiste 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\times15 et 45 = 3\times15 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 :
au+bv = 1.
Remarque
Les valeurs de u et de v peuvent être obtenues à l’aide de l’algorithme d’Euclide (fiche méthode à venir…)
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 :
au+bv = d.
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.
Exemples
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\times10 = 60.
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és
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 premier 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 :
n=p_{1}^{a_{1}}p_{2}^{a_{2}}\cdots p_{k}^{a_{k}}
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 :
n=p_{1}^{b_{1}}p_{2}^{b_{2}}\cdots p_{k}^{b_{k}}
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).