Chapitre 5 : PGCD de deux nombres entiers - Fractions irréductibles

I)Diviseur d'un nombre entier

Si a et b sont deux nombres entiers. On dit que b est un diviseur de a (ou que b divise a) si a est dans la table de multiplication de b ou si le quotient de la division de a par b est un nombre entier.

Exemple
7 est un diviseur de 35 car 35 est dans la table de 7
432 est dans la table de 9 car
Par contre 354 n'est pas un multiples de 7 car n'est pas un nombre entier

Rappel des règles de divisibilité par 2, 3, 5 et 10

Par 2 :Un nombre entier est divisible par 2 lorsqu'il se termine par 0, 2, 4, 6 ou 8
Exemple 544 est divisible par 2 car il se termine par 4

par 3 : Un nombre entier est divisible par 3 lorsque la somme de ses chiffres est dans la table de 3
Exemple 252 est divisible par 3 car 2+5+2=9 et 9 est dans la table de 3

Par 5 : Un nombre entier est divisible par 5 lorsqu'il se termine par 0 ou 5.
Exemple 545 et 230 sont divisible par 5.

Par 9: Un nombre entier est divisible par 9 lorsque la somme de ses chiffres est dans la table de 9
Exemple 8271 est divisible par 9 car 8+2+7+1=18 et 18 est dans la table de 9.

Par 10 : Un nombre entier est divisible par 10 lorsqu'il se termine par 0.
Exemple 5210 est divisible par 10.

II)PGCD

Diviseurs communs

Définition : Un diviseur commun à a et b est un nombre qui divise a et qui divise b

Exemple :
2 est un diviseur commun à 12 et 42

PGCD(Plus Grand Commun Diviseur)

Le PGCD de deux nombres entiers a et b est le plus grand des diviseurs communs à ces deux nombres.
On note PGCD(a;b) pour le PGCD de a et b

Exemple
Diviseurs de 16 : 1,2, 4, 8, 16
Diviseurs de 24 : 1, 2, 3, 4, 6, 8, 12, 24
Diviseurs communs à 16 et 24 : 1, 2, 4, 8

Donc PGCD (16 ; 24)=8

Définition :

Si PGCD(a ; b)=1
Alors on dit que a et b sont premiers entre eux

Exemple :
9 et 20 sont premiers entre eux
Par contre 9 et 15 ne sont pas premiers entre eux car PGCD(9,15)=3

Recherche du PGCD :

A) Algorithmes des différences successives

Propriété (Admis)

Supposons a>b
pgcd(a ; b)=pgcd (a-b ; b)

Algorithme des différences successives

Pour calculer le pgcd de a et b (avec a>b). On procède comme suit

Calculer a-b=c
Si c=b Alors pgcd(a,b)=b
Si , on remplace a et b par c et b et on recommence à partir de 1)

Exemple :
On veut calculer le pgcd(36; 16)

Étapes	a	b	a-b
1	36	16	20	36-16=20
2	20	16	4	20-16=4
3	16	4	12	16-4=12	On prends a=16 et b=4 pour que a>b
4	12	4	8	12-4=8
5	8	4	4	8-4=4	Comme 8-4=4 Alors pgcd(36 ; 16)=4

B)Algorithme d'Euclide

Propriété : (Admis)

Si r est le reste de la division euclidienne de a par b (avec a>b)
Alors PGCD(a ; b)=PGCD(b ; r)

Algorithme d'Euclide

Pour calculer le pgcd de a et b (avec a>b). On procède comme suit
1)Diviser a par b ; obtenir le reste r
2)Si r=0 Alors pgcd(a,b)=b
3)Si , on remplace a et b par b et r et on recommence à partir de 1)