Cours, Chapitre de Mathématiques de niveau Terminale

Tpautrel

Description

Pgcd
Cours, Chapitre en Mathématiques (2011) pour Terminale S

Sujets

• Ressource
• ressources pédagogiques
• École
• Lycée
• exercices
• Cours
• Devoir scolaire
• Devoir surveillé
• Annales

Informations

• Publié par: ressources-de-terminale
• Nombre de lectures: 446
• Langue: Français

Extrait

Ch3: Le PGCD

1. PGCD 1.1. Diviseurs communs à deux entiers naturels: Deux entiers naturels non nuls ont toujours un nombre fini de diviseurs et donc de diviseurs communs (dont 1 et -1). Il existe donc un diviseur commun à ces deux nombres plus grand que les autres. Définition: a b et désignedeux entiers naturels non nuls. PGCDa , b Le plus grand diviseur commun àaet àbest appelé PGCD de a et de b et est noté. PGCDa , b=b Conséquence:bdivisea.équivaut à dire que En effet, tout diviseur debdiviseaetbest le plus grand diviseur deb. 1.2.Le lemme d'Euclide:

Lemme:aetbdésignent deux entiers naturels non nuls. r≠0a=b qr PGCDba ,=PGCDb , r Si des entiers naturelsqetr., alorssont tels que, avec

Remarques: Un lemme est une proposition dont la démonstration est préliminaire à celle d'un théorème. ✔ Cette relation peut être la relation de la division euclidienne, mais pas forcément. ✔

Démonstration:  d∈ℕ uavb Soit d un diviseur commun à a et à b,. Alors d divise toute combinaison linéaire, u , v∈ ℤ²a×1b×−q donc d diviseen posant u =1 et v = - q. D'où d divise aussi r. => (2)Tout diviseur commun à a et à b est également un diviseur commun à b et à r. En particulier, le PGCD(a;b) est un diviseur commun à b et à r.  d '∈ℕubvr Soit d' un diviseur commun à b et à r,. Alors d' divise toute combinaison linéaire, u , v∈ ℤ² bqr donc d' diviseavec u = q et v = 1. D'où d' divise aussi a. => (1) tout diviseur commun à b et à r est également un diviseur commun à a et à b. En particulier, le PGCD(b,r) est aussi un diviseur commun à a et à b. Il vient de (1) et de (2) que l'ensembledes diviseurs communs à a et à b est égal à l'ensemble des diviseurs commun à b et à r. Les deux ensembles ont le même plus grand élément. Les deux ensembles ont le même plus grand élément. Il vient que PGCD(a,b) = PGCD(b,r).

1.3.Calcul du PGCD:

✔ Avec excel: Si a est en cellule A1, b en cellule A2, la formule à saisir dans la cellule A3 pour calculer le PGCD de a et de b est =PGCD(A1;A2) Avec Xcas: choisir menu Maths, Entier, puis gcd. ✔ ✔ A la main: utiliser la décomposition en produit de facteurs premiers. Par l'algorithme d'Euclide: ✔ a et b désignent deux entiers naturels non nuls avec a > b. Pour déterminer PGCD(a,b) on utilise l'algorithme d'Euclide qui découle du lemme du même nom: L'idée: OpérationReste Commentaire r0rbPGCDa ,b=PCGDb , r On remplace (a,b)On divise a par b 0 0 et 0 r0 0 ≠r r 0rrPGCDb , r=PGCDr ;r par des couples de Si ,on divise b par 1 0 0 1 et 0 01 nombres de plus en ... plus petits qui ont ... r PGCD r ;=r le même ensemble r≠0 n− n−1 r n n Si n , on divise 1 par r 0 de diviseurs n communs.

Après un nombre fini de divisions, on trouve un reste nul, car les restes sont des nombres positifs qui vont en ...r 0rr − rb r décroissant strictement n n1 10 . Ci dessus, on note n le dernier reste non nul. PGCDa ; b=PGCr Donc =PGCDb , r=...D n− ; r=r . 0 1n n

Propriété:Lorsque b ne divise pas a, le PGCD des entiers naturels non nuls a et b est égal au dernier reste non nul obtenu par l'algorithme d'Euclide.

Conséquence:de PGCD(a,b).Les diviseurs communs à deux entiers naturels non nuls a et b, sont les diviseurs r En effet, d'après l'algorithme d'Euclide, les diviseurs communs à a et b sont les diviseurs communs à b et à 1 ,à r rr − r rr r − r 1 et 2 ... à n1 et n , c'est-à-dire les diviseurs de n (car n divise n1 ). Or n est le PGCD(a,b).

Exercice 1:Calculer le PGCD de 1 636 et de 1 128 avec l'algorithme d'Euclide. Étapes ab resteségalités 1 1636 1128 5081636=1128X1+508 2 1128508 1121128=2X508+112 3 4 5 6 52 84 52=6X8+4 7 8 4 08=4X2 Exercice 2:Si on divise 4 373 et 826 par un même entier naturel non nul n, on obtient respectivement 8 et 7 pour restes. Quel est ce nombre?

2. Propriétédu PGCD et notion d'entiers premiers entre eux: 2.1. Propriété du PGCD:

Si on multiplie deux entiers naturels a et b par un même entier naturel k non nul, leur PGCD est multiplié par k, PGCD(ka, kb) = k PGCD(a,b). c'est-à-dire PGCD12000,32000=... Exemple:

Démonstration: ● a=bqr ,0rb ak=bkqk r0k rk b => .Cette égalité traduit donc la division 0 00 00, 0 ka kb euclidienne depar . ● b=r qr ,0rrkb=k rq,k r0k rk r => . 0 11 1001 10 1 ... × ● PGCDr − rk ,×k=k rPGCDk a , k b=k r=k PGCDa , b On obtient n1n n . Il vient que n .

Conséquence: a b1 PGCD,=PGCDa , b Si k est un entier naturel non nul,diviseur communà a et à b, alors k kk a b a b a=k×b=k×k PGCD,=PGCDa ,b En effet, il suffit d'écrireet .. k k k k 2.2.Extension du PGCD aux entiers relatifs: ∣a∣ ∣b∣ Soient deux entiers relatifs a et b no n nuls. Le PGCD de a et de b est égal au PGCD deet de. PGCDa ,b=PGCD∣a∣,∣b∣ . Remarques: ● PGCDka , kb=∣k∣PGCDa , b Pour tout entier relatif k non nul,

● PGCDa ,b Les diviseurs communs à a et à b sont encore les diviseurs de, même avec des entiers relatifs. 2.3.Nombres premiers entre eux:

PGCDba ,=1 Définition:dire que deux entiers relatifs non nuls a et b sont premiers entre eux signifie que. Exemple: 35 et 27 sont premiers entre eux.

Propriété: a et b désignent deux entiers relatifs non nuls. d=PGCDa ,b a ' ab '='d a Si ,alors il existe des entiers relatifset premiersentre eux tels queet b='d b .

Démonstration: d=PGCDa ,b Soit alorsd divise a et b. Donc il existe un couple (a',b') d'entiers relatifs non nuls tels que a=d a'b=d b' d=PGCDa ,b=PGCDda ' , db '=d PGCDa ',b ' et .Or .En simplifiant par d( qui PGCDa ' , b '=1 vaut au minimum 1), on obtient. Les entiers a' et b' sont bien premiers entre eux.

Exercice 3:m et n désignent deux entiers naturels non nuls. Quel est le PGCD de mn et de (2m+1)n?

Exercice 4:Déterminer tous les couples (a,b) d'entiers naturels tels que ab = 1452 et PGCD(a,b) = 11.