"'O
0
c
:J
0
li)
..--t
0
N
@
.......
J::
O'l
·;::::
>o.
0
u
Chapitre l • Arithmétique
En pratique, on divise le nombre par son plus petit diviseur premier, et on
recommence jusqu'à ce que le quotient soit 1.
84 2
42 2
21
3
7 7
975 3
325 5
65 5
1 3 1 3
La décomposition d ' un nombre en produit de facteurs premiers permet d'obtenir
tous ses diviseurs. Par exemple, 84 = 2
2 x 3 x 7, un diviseur de 84 s'écrit donc :
2i x 3i x 7k avec 0::; i::; 2, 0 ::;j::; 1, 0::; k::; 1.
En utilisant l'algorithme suivant, on obtient les 12 diviseurs de 84 qui sont 1, 2, 3,
4, 6, 7, 12, 14, 21 , 28, 42 et 84.
Variables : i, j, k (entiers)
Début
Fin
Pour ide 0 à 2 Faire
Pour j de 0 à l Faire
Pour k de 0 à l Faire
1 Afficher 2; x 3j x 7k
Fin Pour
Fin Pour
Fin Pour
1.3.3 PGCD de deux entiers naturels non nuls
Étant donné deux entiers naturels non nuls a et b, il existe un diviseur commun à a et
à b qui est plus grand que tous les autres. Ce diviseur est appelé Plus Grand
Commun Diviseur et se note PGCD(a;b).
&
Deux entiers naturels non nuls sont premiers entre eux si et seulement si leur
PGCD est égal à l .
10
Exemples
Les diviseurs de 4S sont l, 3, S, 9, l Set 4S. Ceux del OS sont l , 3, S, 7, l S, 21,
3S et l OS . Les diviseurs communs à 4S et l OS sont l, 3, S, l S .
Le plus grand d'entre eux est l S donc l S est le PGCD de 4S et l OS.
On écrit PGCD(4S; l OS)= l S.
Les diviseurs del S sont l, 3, Set l S. Ceux de 44 sont l, 2, 4, 11, 22 et 44.
Le seul diviseur commun à l S et à 44 est l. Il est leur PGCD.
Donc PGCD(l S;44) = l.
l S et 44 sont premiers entre eux.