Plus grand commun diviseur

Plan de la leçon A- PGCD 1- Diviseurs d’un nombre entier 2- PGCD et algorithmes de recherche 3- Nombres entiers premiers entre eux B- Fraction irréductible 1- Définition 2- Simplification de fraction Activités liées à la leçon : 1- Synthèse sur les nombres a) Activité 2 page 9 b) Irrationalité de 2 c) Devoir à la maison : fraction continu 2-Algorithmes d) Activité 4 page 11 e) utilisation du tableur pour trouver le PGCD de deux nombres entiers A. PGCD 1. Diviseurs d’un nombre entier Les nombres

N \ {0}. Il existe des entiers q, r ∈ Z tels que a = bq + r et 0 r<b De plus q et r sont uniques. Nous avons donc l’équivalence : r = 0 si et seulement si b divise a. Exemple 2 Pour calculer q et r on pose la division «classique». Si a = 6789 et b = 34 alors 6789 = 34 × 199 + 23 On a bien 0 23 < 34 (sinon c’est que l’on n’a pas été assez loin dans les calculs). 6789 34 338 306 329 306 23 34 dividende 199 diviseur quotient reste Démonstration Existence. On peut supposer a 0 pour simplifier

congruence. • Recherche des diviseurs communs : algorithme d’Euclide. • Notion d’éléments premiers entre eux : théorème de Bezout et ses conséquences. • Notion de Pgcd et de Ppcm. • Notion d’éléments premiers (ou irréductibles), décomposition en facteurs premiers. Sommaire I) Divisibilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1) Rappels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2) Diviseurs communs . . . . . . . . . . .

nous utilisons par exemple l'algorithme d'Euclide dans le but de calculer le Plus Grand Diviseur Commun (PGCD) parmi tous les diviseurs communs à deux nombres entiers positifs. II-sa vie 1) Al Khwarizmi est un grand savant perse qui a vécu durant le IX° siècle, au début du Moyen-âge. Il naît environ en 780 dans la région perse de Khwarizem (Ouzbékistan actuel) en Asie centrale, et meurt en 850. Ce grand mathématicien est à l'origine de nombreuses découvertes d'aujourd'hui tel que

ARITHMETIQUE I. Multiples et diviseurs On a 2 entier : a et b qui n’égale pas 0. On dit que b et diviseur de a. Donc : • b divise a • a est multiple de b • a est divisible par b Ex : • 2 divise 4 • 4 est multiple de 2 • 4 est divisible par 2 II. Plus Grand Diviseur Commun de 2 entiers Le PGDC de 2 nombres entiers a et b non nuls est le plus grand nombre entier qui divise à la fois a et b. Il est noté PGDC (a ; b). Un PGDC est toujours supérieur

Euclide s'est aussi intéressé à l'arithmétique dans le livre 7. Il a ainsi défini la division que l'on appelle division euclidienne et un algorithme pour calculer le plus grand commun diviseur de deux nombres, connu sous le nom d'algorithme d'Euclide. L'algorithme d'Euclide est un algorithme permettant de déterminer le plus grand commun diviseur (P.G.C.D.) de deux entiers dont on ne connaît pas la factorisation. Il est déjà décrit dans le livre VII des Éléments d'Euclide.

I. DIVISEUR D’UN ENTIER NATUREL a) Définition Si on a deux entiers naturels a et d non nuls, alors : d est un diviseur de a si et seulement si il existe un entier k tel que a=d ×k Ainsi, k est aussi diviseur de a. En clair : 4 est-il un diviseur de 12 ? 12 = 4×3, donc 4 est bien un diviseur de 12. b) Remarques Pour tout nombre entier naturel n on a : 1×n = n On en conclut que 1 est un diviseur de n’importe quel nombre entier naturel. Et tout nombre entier naturel est un diviseur de lui-même

ET PGCD I. DIVISEUR D’UN ENTIER NATUREL a) Définition Si on a deux entiers naturels a et d non nuls, alors : d est un diviseur de a si et seulement si il existe un entier k tel que a=d ×k Ainsi, k est aussi diviseur de a. En clair : 4 est-il un diviseur de 12 ? 12 = 4×3, donc 4 est bien un diviseur de 12. b) Remarques Pour tout nombre entier naturel n on a : 1×n = n On en conclut que 1 est un diviseur de n’importe quel nombre entier naturel. Et tout nombre entier naturel est un diviseur de lui-même

des diviseurs de a. D(a) est un ensemble fini non vide : il est non vide car il contient les nombres -1 et 1 ; il contient un nombre fini d’éléments car un diviseur b de a est un nombre qui vérifie 1 ≤ ≤ Exemple : D(12)={-12 ;-6 ; -4 ;-3 ;-2 ;-1 ; 1 ;2 ;3 ;4 ;6 ;12} D(30)={-30 ; -15 ;-10 ;-6 ;-5 ;-3 ;-2 ;-1 ;1 ;2 ;3 ;5 ;6 ;10 ;15 ;30} Notons D(12 ;30) l’ensemble des diviseurs communs à 12 et à 30 On a : D(12 ;30)= {-6;-3;-2;-1;1 ;2 ;3 ;6} D(12 ;30) est un ensemble fini ; il admet un plus grand élément

PROBLÈMES d) Problème 1 A B Q R 1. 945 = 882 + 63 et 882 = 63 × 14. 945 882 1 63 Donc PGCD (945 ; 882) = 63 car d doit diviser 945 et 882 et la plus grande valeur de d est le PGCD des deux nombres. 882 63 14 0 « Tant que », le reste R est nul. On obtient à l’affichage la valeur commune A. • Si A  B, le premier quotient est nul, le reste est A, donc non nul. À l’issue d’un premier passage dans la boucle, A et B sont échangés : on repart donc avec A 