11
Fabienne BUSSAC

Fabienne BUSSAC. 1. DIVISEURS : RAPPELS DIVISEURS : RAPPELS 2. PGCD DE DEUX NOMBRES PGCD DE DEUX NOMBRES 3.CALCUL DU PGCD PAR SOUSTRACTIONS SUCCESSIVESCALCUL

Embed Size (px)

Citation preview

Page 1: Fabienne BUSSAC. 1. DIVISEURS : RAPPELS DIVISEURS : RAPPELS 2. PGCD DE DEUX NOMBRES PGCD DE DEUX NOMBRES 3.CALCUL DU PGCD PAR SOUSTRACTIONS SUCCESSIVESCALCUL

Fab

ien

ne B

US

SA

C

Page 2: Fabienne BUSSAC. 1. DIVISEURS : RAPPELS DIVISEURS : RAPPELS 2. PGCD DE DEUX NOMBRES PGCD DE DEUX NOMBRES 3.CALCUL DU PGCD PAR SOUSTRACTIONS SUCCESSIVESCALCUL

Fab

ien

ne B

US

SA

C

1. DIVISEURS : RAPPELS

2. PGCD DE DEUX NOMBRES

3. CALCUL DU PGCD PAR SOUSTRACTIONS SUCCESSIVES

4. CALCUL DU PGCD PAR ALGORITHME D’EUCLIDE

Cliquer sur le titre de paragraphe pour un accès direct…

Page 3: Fabienne BUSSAC. 1. DIVISEURS : RAPPELS DIVISEURS : RAPPELS 2. PGCD DE DEUX NOMBRES PGCD DE DEUX NOMBRES 3.CALCUL DU PGCD PAR SOUSTRACTIONS SUCCESSIVESCALCUL

Fab

ien

ne B

US

SA

C1. DIVISEURS : RAPPELS

Soit a et d deux nombres entiers positifs (d 0).

le reste de la division euclidienne de a par d est zéro,

alors on dit que :

le quotient a

dest un nombre entier,

il existe un entier n tel que a = d × n

d est un diviseur de a.

a est divisible par d.

a est un multiple de d.

Si

Page 4: Fabienne BUSSAC. 1. DIVISEURS : RAPPELS DIVISEURS : RAPPELS 2. PGCD DE DEUX NOMBRES PGCD DE DEUX NOMBRES 3.CALCUL DU PGCD PAR SOUSTRACTIONS SUCCESSIVESCALCUL

Fab

ien

ne B

US

SA

CExemple :

42

7= 6 ou 42 = 7 × 6

On peut donc dire que

7 est un diviseur de 42.

42 est divisible par 7.

42 est un multiple de 7.

4 n’est pas un diviseur de 26 car le quotient 4

26

n’est pas un entier

5,64

26

.

Page 5: Fabienne BUSSAC. 1. DIVISEURS : RAPPELS DIVISEURS : RAPPELS 2. PGCD DE DEUX NOMBRES PGCD DE DEUX NOMBRES 3.CALCUL DU PGCD PAR SOUSTRACTIONS SUCCESSIVESCALCUL

Fab

ien

ne B

US

SA

CTout nombre entier, supérieur ou égal à 2, admet au moins deux diviseurs :

Propriété :

Définition :

Exemples :

2, 3, 5, 7, 11, 13, 17, 19… sont des nombres premiers.

9 n’est pas un nombre premier : il a trois diviseurs 1 ; 3 et 9.

1 n’est pas un nombre premier : il a un seul diviseur 1.

1 et lui-même.

Page 6: Fabienne BUSSAC. 1. DIVISEURS : RAPPELS DIVISEURS : RAPPELS 2. PGCD DE DEUX NOMBRES PGCD DE DEUX NOMBRES 3.CALCUL DU PGCD PAR SOUSTRACTIONS SUCCESSIVESCALCUL

Fab

ien

ne B

US

SA

C2. PGCD DE DEUX NOMBRES

Si deux entiers positifs a et b sont divisibles par un même entier d, alors on dit que d est un diviseur commun de a et b.

Exemple :

15 = 5 × 3 et 40 = 5 8,

donc 5 est un diviseur commun de 15 et 40.

est un diviseur commun à tous les nombres.

Remarque :

1

Page 7: Fabienne BUSSAC. 1. DIVISEURS : RAPPELS DIVISEURS : RAPPELS 2. PGCD DE DEUX NOMBRES PGCD DE DEUX NOMBRES 3.CALCUL DU PGCD PAR SOUSTRACTIONS SUCCESSIVESCALCUL

Fab

ien

ne B

US

SA

Ca et b sont deux nombres entiers positifs.

Parmi leurs diviseurs communs, l’un d’entre eux est plus grand que les autres.

Page 8: Fabienne BUSSAC. 1. DIVISEURS : RAPPELS DIVISEURS : RAPPELS 2. PGCD DE DEUX NOMBRES PGCD DE DEUX NOMBRES 3.CALCUL DU PGCD PAR SOUSTRACTIONS SUCCESSIVESCALCUL

Fab

ien

ne B

US

SA

CExemple :

La liste des diviseurs de 24 est :

1 242 123 84 6; ; ; ;; ; ;

La liste des diviseurs de 36 est :

1 362 183 124 9; ; ; ;; ; ;;6

Les diviseurs communs de 24 et 36 sont : 1 ; 2; 3; 4; 6 et 12.

Le plus grand d’entre eux est 12, c’est le plus grand diviseur commun de 24 et 36.

On note PGCD (24 ; 36) = 12.

24 = 1 × 24

24 = 2 × 12

24 = 3 × 8

24 = 4 × 624 = 5 ×…

36 = 1 × 3636 = 2 × 1836 = 3 × 1236 = 4 × 936 = 5 ×…36 = 6 × 6

Page 9: Fabienne BUSSAC. 1. DIVISEURS : RAPPELS DIVISEURS : RAPPELS 2. PGCD DE DEUX NOMBRES PGCD DE DEUX NOMBRES 3.CALCUL DU PGCD PAR SOUSTRACTIONS SUCCESSIVESCALCUL

Fab

ien

ne B

US

SA

CDéterminer le PGCD de 413 et 295.

413 – 118295295 = 118

– = 177118 177

– = 59

PGCD (413 ; 295) = PGCD (295 ; 118)PGCD (295 ; 118) = PGCD (177 ; 118)PGCD (177 ; 118) = PGCD (118 ; 59)

PGCD (413 ; 295) = 59

3. CALCUL DU PGCD PAR SOUSTRACTIONS SUCCESSIVES

– = 59 PGCD (118 ; 59) = PGCD (59 ; 59)

118 59

Page 10: Fabienne BUSSAC. 1. DIVISEURS : RAPPELS DIVISEURS : RAPPELS 2. PGCD DE DEUX NOMBRES PGCD DE DEUX NOMBRES 3.CALCUL DU PGCD PAR SOUSTRACTIONS SUCCESSIVESCALCUL

Fab

ien

ne B

US

SA

CCalculer le PGCD de 494 et 143.

4. CALCUL DU PGCD PAR ALGORITHME D’EUCLIDE

On effectue la division euclidienne de 494 par 143 : 4 9 4 1 4 3

36 5

On peut écrire : dividende = quotient × diviseur + reste, soit :

494 = 3 × 143 + 65On recommence le même travail avec le diviseur 143 et le reste de la division 65 :

1 4 3 6 5

21 3143 = 2 × 65 + 13

On recommence le même travail avec le diviseur 65 et le reste de la division 13 :

6 5 1 3

5065 = 5 × 13 + 0

Le PGCD cherché est le dernier reste différent de 0.

Ici, PGCD(494 ; 143) = 13

Page 11: Fabienne BUSSAC. 1. DIVISEURS : RAPPELS DIVISEURS : RAPPELS 2. PGCD DE DEUX NOMBRES PGCD DE DEUX NOMBRES 3.CALCUL DU PGCD PAR SOUSTRACTIONS SUCCESSIVESCALCUL

Fab

ien

ne B

US

SA

CExemple : calculer le PGCD de 108 et 846 avec l’algorithme d’Euclide

846 = 108× +7 90108 90

108 = × +1 189090 18

90 = 18× +5 0

Le dernier reste différent de 0 est 18 donc :

PGCD(108 ; 846) = 18