"'O
0
c
:J
0
:<:;
li)
.,,
..--t
c::
:l
0
~
N
"
@
~
.......
0
J::
:;
O'l
"'
·;::::
c::
0
>c::
o.
c::
0
.9
u
ü
:l
.,,
2
o.
~
"
:;
0
11
.,,
0
c:
:l
0
QJ
1.4 • Congruences
Propriété 1.4
Soit a et b deux entiers naturels supérieurs ou égaux à 2 dont on connaît les
décompositions en produits de facteurs premiers :
- s'ils n'ont pas de facteur commun, alors leur PGCD est 1 ;
- sinon, leur PGCD est le produit des facteurs communs aux deux décompositions, chaque facteur étant affecté du plus petit exposant avec lequel il figure
dans les deux décompositions.
Exemples
Soit a= 4 950 = 2 x 3 2 x 5 2 x 11 et b = 4 875 = 3 x 5 3 x 1 3.
Les facteurs communs aux deux décompositions sont 3 et 5.
3 figure avec les exposants 2 et 1, on garde le plus petit, c'est-à-dire 1.
5 figure avec les exposants 2 et 3, on garde le plus petit, c'est-à-dire 2.
Donc PGCD (4 950;4 875) = 3 X 5 2 = 75.
Soit a= 2 4 x 3 x 5 2 x 7 x 19 et b = 2 3 x 3 2 x 7 2 x 1 7. Les facteurs communs aux
deux décompositions sont 2, 3 et 7. Les plus petits exposants sont 3 pour le
facteur 2, 1 pour le facteur 3 et 1 pour le facteur 7.
Donc PGCD (a;b) = 2 3 x 3 x 7.
Propriété 1.5
Soit a et b deux entiers naturels non nuls tels que a > b.
Soit r le reste de la division euclidienne de a par b.
Alors PGCD(a ;b) = PGCD(b;r)
Cette propriété (1.5) permet d'avoir une autre méthode pour chercher un PGCD.
On applique plusieurs fois la propriété jusqu'à obtenir un reste nul. Le PGCD est
alors le dernier diviseur essayé.
Son avantage est qu'elle est algorithmique, donc programmable. Elle est connue
sous le nom d'algorithme d'Euclide.
Exemple
PGCD(420;182) = PGCD(l 82;56) car 56 est le reste de la division euclidienne de
420 par 182.
PGCD(l 82;56) = PGCD(56; 14) car 14 est le reste de la division euclidienne de 182
par 56.
Le reste de la division euclidienne de 56 par 14 est 0, donc 14 est le PGCD de 420
et 182.
1.4 CONGRUENCES
Soit n un entier naturel non nul. On dit que deux entiers naturels a et b sont congrus
modulo n si et seulement si a et b ont le même reste dans la division euclidienne
par n. On écrit alors a = b [ n] ou b = a [ n] .
1 1
0
c
:J
0
:<:;
li)
.,,
..--t
c::
:l
0
~
N
"
@
~
.......
0
J::
:;
O'l
"'
·;::::
c::
0
>c::
o.
c::
0
.9
u
ü
:l
.,,
2
o.
~
"
:;
0
11
.,,
0
c:
:l
0
QJ
1.4 • Congruences
Propriété 1.4
Soit a et b deux entiers naturels supérieurs ou égaux à 2 dont on connaît les
décompositions en produits de facteurs premiers :
- s'ils n'ont pas de facteur commun, alors leur PGCD est 1 ;
- sinon, leur PGCD est le produit des facteurs communs aux deux décompositions, chaque facteur étant affecté du plus petit exposant avec lequel il figure
dans les deux décompositions.
Exemples
Soit a= 4 950 = 2 x 3 2 x 5 2 x 11 et b = 4 875 = 3 x 5 3 x 1 3.
Les facteurs communs aux deux décompositions sont 3 et 5.
3 figure avec les exposants 2 et 1, on garde le plus petit, c'est-à-dire 1.
5 figure avec les exposants 2 et 3, on garde le plus petit, c'est-à-dire 2.
Donc PGCD (4 950;4 875) = 3 X 5 2 = 75.
Soit a= 2 4 x 3 x 5 2 x 7 x 19 et b = 2 3 x 3 2 x 7 2 x 1 7. Les facteurs communs aux
deux décompositions sont 2, 3 et 7. Les plus petits exposants sont 3 pour le
facteur 2, 1 pour le facteur 3 et 1 pour le facteur 7.
Donc PGCD (a;b) = 2 3 x 3 x 7.
Propriété 1.5
Soit a et b deux entiers naturels non nuls tels que a > b.
Soit r le reste de la division euclidienne de a par b.
Alors PGCD(a ;b) = PGCD(b;r)
Cette propriété (1.5) permet d'avoir une autre méthode pour chercher un PGCD.
On applique plusieurs fois la propriété jusqu'à obtenir un reste nul. Le PGCD est
alors le dernier diviseur essayé.
Son avantage est qu'elle est algorithmique, donc programmable. Elle est connue
sous le nom d'algorithme d'Euclide.
Exemple
PGCD(420;182) = PGCD(l 82;56) car 56 est le reste de la division euclidienne de
420 par 182.
PGCD(l 82;56) = PGCD(56; 14) car 14 est le reste de la division euclidienne de 182
par 56.
Le reste de la division euclidienne de 56 par 14 est 0, donc 14 est le PGCD de 420
et 182.
1.4 CONGRUENCES
Soit n un entier naturel non nul. On dit que deux entiers naturels a et b sont congrus
modulo n si et seulement si a et b ont le même reste dans la division euclidienne
par n. On écrit alors a = b [ n] ou b = a [ n] .
1 1