RECHERCHE DU PGCD DE DEUX NOMBRES ALGORITHME D'EUCLIDE Rouen

 Objectifs
- Découvrir l'algorithme d'Euclide.
- Programmer l'algorithme d'Euclide à l'aide d'un tableur en utilisant la propriété suivante : 

Si r est le reste de la division euclidienne de a par b alors PGCD(a ; b) = PGCD(b ; r).

  Description de l'activité
L'activité débute par une présentation de l'algorithme d'Euclide :

Pour calculer le PGCD de deux entiers naturels non nuls a et b (a > b) avec l'algorithme d'Euclide, on utilise la séquence ordonnée d'opérations schématisées ci-contre et décrites ci-dessous : (1) Diviser a par b ; obtenir le reste r. (2) Si r = 0, alors l'algorithme se termine : PGCD(a ; b) = b. (3) Si r ¹ 0, remplacer a par b, b par r et recommencer à partir de (1).

L'activité propose ensuite de programmer cet algorithme à l'aide d'un tableur. Des aides pour établir la feuille de calcul sous Works ou Excel  sont proposées aux élèves.

Cette activité peut servir à valider la compétence 3 du Brevet informatique et internet scolaire - niveau 2 : organiser des traitements numériques à l'aide d'un tableur car l'élève doit être capable de créer une feuille de calcul simple qui réponde à un problème donné en utilisant à bon escient les formules, et d'en vérifier la validité. 

Fiche professeur : algeucl.doc