L’ALGORITHME D’EUCLIDE - maths et tiques

d’Euclide tableur tableur 3ème 2002-2003 LE NOMBRE 2 Activité : 2 et fraction irréductible Euclide (300 avant notre ère) s’est posé la question:

L’ALGORITHME D’EUCLIDE - maths et tiques

Calcul du PGCD de deux nombres par l’algorithme d’Euclide Remarque préliminaire : Dans toute l’activité, a et b sont deux entiers positifs tel que : a > b et b ne divise pas a 1ère partie : Sur feuille Pour calculer le PGCD de deux entiers a et b avec l'algorithme d'Euclide, on utilise la succession d'opérations schématisée ci-contre

3 me - Arithm tique - Le on

b) Déterminons le PGCD de 121 et 85 en appliquant l’algorithme d’Euclide : Dividende Diviseur Reste 121 85 36 85 36 13 36 13 10 13 10 3 10 3 1 3 1 0 Le PGCD est le diviseur de la division dont le reste est nul Donc : PGCD 121;85 1( )= Remarque : Cet algorithme se programme aisément sur tableur : A B C

Mathématiques – 3ème – DEVOIR MAISON pour préparer le contrôle du

Mathématiques – 3ème – DEVOIR MAISON pour préparer le contrôle du Connaître et utiliser un algorithme donnant le PGCD de deux entiers (algorithme des soustractions, algorithme d’Euclide) Utiliser le tableur pour calculer un PGCD Reprendre les questions a et b de l'exercice 1 et compléter les tableaux ci-dessous par les

L’ALGORITHME LE PLUS PERFORMANT

Comparer sur des exemples lequel de l’algorithme d’Euclide et de l’algorithme des soustractions mène par le moins d'opérations au PGCD de deux nombres 1ère partie : Programmation de l’algorithme d’Euclide Dans les colonnes A, B et C du tableur, programmer l’algorithme d’Euclide

Mathématiques – 3ème – DEVOIR MAISON pour préparer le contrôle du

Contrôle n°1 3ème

1°) Les bouquets sont identiques et il ne reste pas de fleurs donc le nombre de bouquet est un diviseur commun à 1 404 et 252 De plus Noémie veut faire le plus de bouquets possibles, donc le nombre de bouquets est le PGCD(1 404 ; 252) Déterminons ce nombre à l’aide de l’algorithme d’Euclide : dividende diviseur reste raisonnement

MATHÉMATIQUES

impossible, d’événement certain, d’événements contraires Arbres de probabilités Problèmes à épreuves successives Séquence 2 nombres 26 Diviseurs d’un entier Nombres premiers Notion de PGCD, de fractions irréductibles Algorithme par soustractions successives et algorithme d’Euclide Séquence 3

Nombres premiers - Free

diviseurs : 1 et lui même Les nombres premiers sont les nombres qui n'ont pas d'autres diviseurs 1- Définition Un nombre premier est un entier naturel qui a exactement deux diviseurs : 1 et lui même Exemples : •2, 3, 5, 7, 11 sont des nombres premiers •4 n'est pas un nombre premier car il a trois diviseurs : 1, 4 et 2

L'ALGORITHME D'EUCLIDE

Objectif :

Calcul du PGCD de deux nombres par l'algorithme d'Euclide.

Remarque préliminaire :

Dans toute l'activité, a et b sont deux entiers positifs tel que : a > b et b ne divise pas a. 1

ère

partie : Sur feuille

Pour calculer le PGCD de deux entiers a et b avec

l'algorithme d'Euclide, on utilise la succession d'opérations schématisée ci-contre.

Exemple : PGCD(36 ; 24)

a = 36 et b = 24

Le reste r de la division de 36 par 24 est 12

r = 12 en remplaçant : a = 24 et b = 12

Le reste r de la division de 24 par 12 est 0

r = 0 donc PGCD(36 ; 24) = 12 (le dernier reste non nul) Appliquer ce schéma pour trouver le PGCD de 38 et 14. 2

ème

partie : Avec le tableur

Ouvrir le fichier du tableur " Euclide » et réenregistrer-le en suivant les consignes du professeur.

L'objectif est dans cette partie de créer une feuille de calcul donnant le PGCD de deux nombres. Le tableau présentera les divisions successives effectuées dans l'algorithme d'Euclide.

Dans les cellules B1 et E1, se trouvent les nombres dont on cherche le PGCD. On retrouve ces nombres dans

les cellules A4 et B4.

1) a) Compléter la cellule C4 par une formule permettant de calculer le reste de la division du nombre inscrit dans

la cellule A4 par le nombre inscrit dans la cellule B4.

b) Appliquer l'algorithme d'Euclide pour compléter les cellules A5 et B5 par les formules qui conviennent.

c) La cellule C5 doit afficher le reste de la division du nombre inscrit dans la cellule A5 par le nombre inscrit

dans la cellule B5. Entrer la formule dans la cellule C5. d) Finir de compléter le tableau jusqu'à obtention du PGCD des deux nombres.

On pourra copier les formules vers le bas.

Dans quelle cellule retrouve-t-on le PGCD de 38 et 14 calculé dans la 1

ère

partie ? Expliquer.

2) En remplaçant dans les cellules B1 et E1, trouver le PGCD de 93 et 66 puis de 85 et 65.

Que peut signifier ici le message " #VALEUR ! » dans la cellule C7 ?

3) À l'aide du tableur, trouver les PGCD des couples de nombres suivants :

a) 19 110 et 61 710 b) 452 356 et 726 858 c) 217 309 365 et 30 107 000 Pourrait-on calculer le PGCD des nombres de la question c) à la main :-( ? 3

ème

partie : Prolongement

Entrer dans la cellule E5 la formule =SI(C5=0;C4;" ") et copier cette formule dans les cellules directement en

dessous de la cellule E5. Pouvez-vous expliquer ce que signifie cette formule ?

PGCD(a ; b) Trouver le reste r de la division de a par b r = 0 PGCD(a ; b) est égal au dernier reste non nul Remplacer : a par b b par r oui non

T1 T2 T3 Yvan Monka - Académie de Strasbourg - www.maths-et-tiques.fr

AIDES TABLEUR

T1 Dans la cellule C4, entrer la formule =MOD(A4;B4). T2 - Dans la cellule A5, entrer la formule suivante =B4 - Dans la cellule B5, entrer =C4 T3

Pour copier rapidement des formules :

- Sélectionner les cellules à copier. - Cliquer sans lâcher l e petit carré noir en bas à droite des cellules sélectionnées et faire glisser le curseur de façon à recouvrir les autres cellules dans lesquelles les formules doivent être copiées.

Hors du cadre de la classe, aucune reproduction, même partielle, autres que celles prévues à l'article L 122-5 du code de la propriété intellectuelle, ne peut être faite de ce site sans l'autorisation expresse de l'auteur. www.maths-et-tiques.fr/index.php/mentions-legales

quotesdbs_dbs46.pdfusesText_46

[PDF] L’ALGORITHME D’EUCLIDE - maths et tiques

RECHERCHE DE PGCD - Sésamath

L’ALGORITHME D’EUCLIDE - maths et tiques

3 me - Arithm tique - Le on

Mathématiques – 3ème – DEVOIR MAISON pour préparer le contrôle du

L’ALGORITHME LE PLUS PERFORMANT

Mathématiques – 3ème – DEVOIR MAISON pour préparer le contrôle du

Contrôle n°1 3ème

MATHÉMATIQUES

Nombres premiers - Free

L'ALGORITHME D'EUCLIDE

Objectif :

Remarque préliminaire :

ère

Pour calculer le PGCD de deux entiers a et b avec

Exemple : PGCD(36 ; 24)

Le reste r de la division de 36 par 24 est 12

Le reste r de la division de 24 par 12 est 0

ème

1) a) Compléter la cellule C4 par une formule permettant de calculer le reste de la division du nombre inscrit dans

On pourra copier les formules vers le bas.

ère

2) En remplaçant dans les cellules B1 et E1, trouver le PGCD de 93 et 66 puis de 85 et 65.

3) À l'aide du tableur, trouver les PGCD des couples de nombres suivants :

ème

AIDES TABLEUR

Pour copier rapidement des formules :