Upload
sybille-lavigne
View
106
Download
4
Embed Size (px)
Citation preview
Fab
ien
ne B
US
SA
C
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…
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
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
.
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.
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
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.
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
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
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
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