Fiche de mathématiques
> >

Diviseurs et PGCD, exercice 2

Partager :
Fiche relue en 2016

DES ALGORITHMES, ENCORE DES ALGORITHMES



1. Déterminez le PGCD de 770 et 198 par l'algorithme par soustractions

2. Déterminez le PGCD de 7830 et 12818 par l'algorithme d'Euclide





1. Déterminez le PGCD de 770 et 198 par l'algorithme par soustractions

L'algorithme par soustractions repose sur la propriété suivante :

« a et b étant deux nombres entiers positifs tels que a>b, on a PGCD (a ; b) = PGCD(b ; a-b) »

Nous allons donc appliquer cette propriété pas à pas et présenter les résultats dans un tableau.

a
b
a-b
770 198 572
572 198 374
374 198 176
198 176 22
176 22 154
154 22 132
132 22 110
110 22 88
88 22 66
66 22 44
44 22 22
22 22 0

De la propriété appliquée 12 fois successivement, on déduit que :
PGCD(770 ; 198) = PGCD (22 ; 22) = 22

Le PGCD (770 ; 198) est la dernière différence non nulle obtenue par l'algorithme par soustractions.

2. Déterminez le PGCD de 7830 et 12818 par l'algorithme d'Euclide
L'algorithme par divisions encore appelé algorithme d'Euclide repose sur la propriété suivante :

« a et b étant deux nombres entiers positifs tels que a> b, on a PGCD (a ; b) = PGCD(b ; reste de a : b) »

Nous allons donc appliquer cette propriété pas à pas et présenter les résultats dans un tableau.
On effectue successivement les divisions euclidiennes et on note les restes successifs.
a
b
Reste de a:b
12818 7830 4988
7830 4988 2842
4988 2842 2146
2842 2146 696
2146 696 58
696 58 0

De la propriété ci-dessus appliquée 6 fois successivement on déduit que :
PGCD (12818 ; 7830) = PGCD(696 ; 58) = 58

Remarque : 696 = 58 \times 12 + 0

Le PGCD(1281 ; 7830) est le dernier reste non nul obtenu dans l'algorithme d'Euclide donc PGCD(7830 ; 1281) = 58
Publié le
ceci n'est qu'un extrait
Pour visualiser la totalité des cours vous devez vous inscrire / connecter (GRATUIT)
Inscription Gratuite se connecter


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1229 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !