[PDF] Chapitre 1 Arithmétique Partie 5 : PGCD

View - Download Chapitre 1 Arithmétique Partie 5 : PGCD

Previous PDF

Next PDF

TS Spé Lycée Beaussier Mathématiques 1

Chapitre 1

Arithmétique

Partie 5 : PGCD

Propriété/Définition : (PGCD)

On se donne deux entiers relatifs a et b non nuls. L"ensemble des diviseurs positifs communs à a et b admet un plus grand élément que l"on notera ();PGCD a b.

Démonstration :

Soit A l"ensemble des diviseurs positifs de a et B celui des diviseurs positifs de b.

On sait que A et B admettent un nombre fini d"éléments (c.f. propriété 1 de la partie divisibilité)

(P1) L"ensemble des diviseurs positifs communs à a et b est l"ensemble

C A B= ∩.

C est non vide et contient l"entier 1, il contient de plus un nombre fini d"éléments par (P1), par suite C contient un plus grand élément ce qui démontre notre propriété.

Exemple :

En prenant a = 27 et b = -30. L"ensemble des diviseurs positifs de a est {}1;3;9; 27A=, celui des diviseurs positifs de b est {}1; 2;3;5;6;10;15;30B=. L"ensemble des diviseurs positifs communs à a et b est {}1;3C A B= ∩ =, son plus grand

élément est 3, donc

()27; 30 3PGCD- =.

Propriétés 1 :

On se donne deux entiers relatifs a et b non nuls. Alors ()(); ;PGCD a b PGCD a b=.

Démonstration :

Comme a et

aainsi que b etbont même ensemble de diviseurs positifs, ils ont le même PGCD. Remarque : La propriété précédente nous permet de restreindre l"étude du PGCD de deux entiers relatifs à celle de leurs valeurs absolues.

En vertu de ceci, toutes les propriétés suivantes seront données pour a et b entiers naturels.

Propriétés 2 :

On se donne deux entiers naturels a et b non nuls. Alors : ()(); ;PGCD a b PGCD b a= ()1; 1PGCD a= ();PGCD a a a=

• Si b divise a alors

();PGCD a b b= TS Spé Lycée Beaussier Mathématiques 2

Démonstration : Le premier point découle du fait que 1 est un diviseur positif commun à a et b,

donc par définition();PGCD a best plus grand que celui-ci.

• Le deuxième point est évident.

• Comme l"ensemble des diviseurs positifs de 1 est {}1B=et puisque 1 est diviseur de a alors le seul diviseur commun à 1 et a est {}1ce qui démontre le troisième point. • Puisque tout diviseur positif de a est inférieur à a et puisque clairement a divise a, alors le plus grand diviseur commun à a et a est a ce qui montre le quatrième point. • L"ensemble A des diviseurs positifs de a admet a comme plus grand élément et comme • Si b divise a et comme clairement b divise b, b est diviseur commun à a et b. précédente

Exemple :

7 est un diviseur de 21 donc PGCD (7 ; 21) = 7

Avant de continuer nous aurons besoin du résultat suivant :

Théorème de Bachet / Bezout : (Admis)

Soient a et b deux entiers naturels non nuls.

Si ();d PGCD a b=alors il existe alors u et v entiers relatifs tels qued au bv= + ou autrement dit();PGCD a best combinaison entière de a et b.

Démonstration :

• Remarquons que

();PGCD a bdivise a et ();PGCD a bdivise b donc();PGCD a bdivise toute combinaison entière de a et b (voir la partie divisibilité, propriété 2)

• Posons

{}; ; avec 0H au bv a b au bv′ ′ ′ ′= + ? ? + ≥? ?l"ensemble des combinaisons entières

de a et b dont le résultat est positif.

Hest non vide, en effet quitte à prendre1et 0u v′ ′= =, on a 0au bv a′ ′+ = >car a est entier

naturel non nul. Ainsi Hest une partie de?non vide et contient des éléments strictement positifs, elle admet donc un plus petit élément strictement positif noté m qui est donc une combinaison entière de a et b, en ce sens posons

0m au bv= + >(*) avecuetventiers relatifs.

On en déduit par le premier point de notre démonstration que();PGCD a bdivise m et donc • Maintenant effectuons la division euclidienne de a par m, on obtient alors l"existence ()()()?avec 0 1 avec 0a au bv q r r m r qu a vq b r m r est donc une combinaison entière de a et b dont le résultat est positif et est strictement TS Spé Lycée Beaussier Mathématiques 3 plus petite que m donc0r H r? ? =par définition même de m. Par suite m divise a.

On montre de même que m divise b.

Finalement m est un diviseur commun à a et b et donc ();PGCD a b m≥ ce qui combiné avec (P1) et (*) donne(); avec et entiers relatifsPGCD a b m au bv u v= = + ce qu"on voulait montrer.

Remarque :

• Le théorème de Bachet / Bezout est un théorème d"existence, il ne donne aucune méthode

pratique permettant de déterminer les coefficients u et v. Celle-ci sera exposée dans la partie suivante (nombres premiers entre eux).

• La réciproque de ce théorème est fausse en général : ce n"est pas par ce qu"un entier naturel

d peut s"écrire sous la formed au bv= +avec u et v entiers relatifs que l"on peut en déduire que ();d PGCD a b=. Par exemple : ??()??()?12 5 8 7 4 da bu v= × + × - mais ()12 5;7PGCD≠. Nous aboutissons désormais au très important : Théorème fondamental : Ensemble des diviseurs communs de deux entiers (Admis)

Soient a et b deux entiers naturels non nuls.

L"ensemble des diviseurs commun à a et b est l"ensemble des diviseurs de ();PGCD a b

Démonstration :

On considère un diviseur d commun à a et b.

d divise toute combinaison entière de a et b (voir la partie divisibilité, propriété 2).

Par le théorème de Bachet/Bezout,

();PGCD a best combinaison entière de a et b donc d divise ();PGCD a b.

Maintenant si d est un diviseur de

();PGCD a b et comme();PGCD a bdivise a ainsi que b

alors d est un diviseur commun à a et b (voir le quatrième point de la propriété 3/ du cours

sur la divisibilité). CQFD. Propriété 3 : Théorème d"Euclide (Démonstration exigible)

Soient a et b deux entiers naturels non nuls.

Soient q et r le quotient et le reste de la division euclidienne de a par b

• Si r = 0 alors PGCD (a ; b) = b

• Si r ≠ 0 alors PGCD (a ; b) = PGCD (b ; r)

Démonstration :

• Si r = 0, alors b divise a et le résultat découle du dernier point de la propriété 2.

• Si r ≠ 0, on a par division euclidienne

a b q r= × +avec q et r entiers naturels. Comme PGCD (a ; b) divise a et b, il divise la combinaison entière r a b q= - ×. Il s"en suit que PGCD (a ; b) divise b et r et est donc un diviseur commun à b et r. (1). TS Spé Lycée Beaussier Mathématiques 4 De manière analogue, PGCD (b ; r) divise b et r et divise donc la combinaison entière b q r× +et donc divise a, il s"en suit que PGCD (b ; r) divise b et a et ainsi PGCD (b ; r) divise PGCD (a ; b) . On conclut que PGCD (a ; b) ≥ PGCD (b ; r) (2) d"où notre résultat en combinant (1) et (2)

Exemple :

Pour trouver le PGCD de 1533 et 306, on peut écrire la division euclidienne de 1533 par 306 :

1533 = 306

×5 + 3. On en déduit alors PGCD (1533 ; 306) = PGCD (306 ; 3) Il est immédiat que PGCD (306 ; 3) = 3 car 3 divise 306.

Donc PGCD (1533 ; 306) = 3

Propriété 4 : Détermination pratique du PGCD, Algorithme d"Euclide. (Admis)

Soient a et b deux entiers naturels non nuls.

On définit la suite

()nrd"entiers naturels de la façon suivante :

0r b=et 1r est le reste de la division euclidienne de a par b

• Pour n ≥ 1 : si

0nr≠, on définit1nr+comme le reste de la division euclidienne de1nr-par nr

Alors il existe un entier

0n tel que00nr≠et010nr+=.

On a alors PGCD(a ; b) =

0nr

Démonstration :

• Si

10r=alors b divise a et ()0;PGCD a b b r= =d"après le dernier point de la propriété 2.

• Existence du rang

0n : si 0nr≠, comme1nr+est le reste de la division euclidienne de1nr-par nr,

alors naturels et par conséquent il existe un entier

0n tel que00nr≠et010nr+=.

• Par le théorème d"Euclide, tant que

0nr≠,

00 10 1 1 2

0 0 1

0 0 1 1 2

Car r b Car a b q r Car r r q r

a r q r par constructionet en utilisant lepar constructionthéorème d Euclideet en utilisant lethéorème d EuclidePGCD a b PGCD a r PGCD r r PGCD r r

()?()0 00 0 2 1

0 0 1 002 11

n n nn n nn n

Car r r q r

par constructionet en utilisant le théorème d EuclidePGCD r r PGCD r r

Maintenant :

010nr+=donc par construction, 0nrdivise01nr-et par suite()0 0 01;n n nPGCD r r r-=

d"après le dernier point de la propriété 2. On conclut que PGCD(a ; b) = 0nr. CQFD.

Remarque :

En effectuant ainsi des divisions euclidiennes successives : de a par b, puis du diviseur par le reste, ...

le dernier reste non nul est le PGCD de a et de b. C"est l"algorithme d"Euclide.

Suivant les nombres a et b, le nombre d"itérations à effectuer peut être plus ou moins grand.

TS Spé Lycée Beaussier Mathématiques 5

Aller dans le menu Programme

Sélectionner New

"A" :? → A "B" :? → B

1 → R

While R > 0

Int (A

÷B) → Q ?

A-B Q×→ R ?

"Q" : Q "R" : R

B → A

R → B

WhileEnd

"PGCD=" : A

Exemple :

Pour déterminer le PGCD de 410258 et de 126

écrivons les divisions euclidiennes successives :

Pour déterminer le PGCD de 15648 et de 657

écrivons les divisions euclidiennes successives :

410258 = 126 x 3256 + 2 15648 = 657 x 23 + 537

126 = 2 x 63 + 0 657 = 537 x 1 + 120

537 = 120 x 4 + 57

Donc PGCD(410258 ; 126) = 2 120 = 57 x 2 + 6

57 = 6 x 9 + 3

6 = 3 x 2 + 0

Donc PGCD(15648 ; 657) = 3

Programmation de l"algorithme d"Euclide avec une calculatrice Pour obtenir " Taper ► puis sélectionner " ? Taper Exe ? ou Taper Shift ►

IF Then

Else IfEnd while...

Taper Shift com ►►

Int

Taper OPTN ► num INT

Lbl goto Taper Shift JUMP puis sélectionner Lbl ou goto : Taper Shift ►►

Reste nul : arrêt de l"algorithme

PGCD ( 15648 ; 657)

PRGM PRGM PRGM PRGM PRGM

Casio Texas

: Input "A ? ", A : Input "B ? ", B : 1→ R : While R > 0 : int (A/B) → Q : A-B

×Q→ R

: Disp "Q", Q : Pause : Disp "R", R : Pause : B → A : R → B : End : Disp "PGCD =", A TS Spé Lycée Beaussier Mathématiques 6

Propriété 5 :

Soient a et b deux entiers naturels non nuls et k un entier relatif non nul

On a alors :

()(); ;PGCD ka kb k PGCD a b= ×

Démonstration :

Si k est un entier naturel non nul :

Par le théorème de Bachet/Bezout il existe deux entiers relatifs u et v tels que : ();PGCD a b au bv= + et en multipliant par k : ()()();k PGCD a b ka u kb v× = +.

Comme maintenant

();PGCD ka kbdivise la combinaison entière()()ka u kb v+, alors();PGCD ka kb divise

Ensuite,

();PGCD a bdivise a et b donc();k PGCD a b×est un diviseur commun à ka et kb (voir le cinquième point de la propriété 3 de la partie divisibilité)

Par définition du PGCD on obtient

résultat annoncé.

Si k est un entier relatif non nul :

Comme

()()()Propriété1; ; ;PGCD ka kb PGCD ka kb PGCD k a k b= =, on obtient le résultat en utilisant ce

qui vient d"être précédemment démontré puisque kest entier naturel non nul.

EXERCICES SUR LE PGCD

Exercice 1

Déterminer a/ PGCD(23452; 3) b/ PGCD(8415 ; 5) c/ PGCD(3216 ; 6)

Exercice 2

Démontrer que le PGCD de deux entiers naturels non nuls et consécutifs est égal à 1.

Exercice 3

En utilisant l"algorithme d"Euclide déterminer : a/ PGCD (567 ; 1040) b/ PGCD (2376 ; 13475)

Exercice 4

Trouver le PGCD de 492480 et 165888.

En déduire l"écriture de la fraction

492480

165888

sous la forme d"une fraction irréductible.

Exercice 5

Soit n un entier naturel. Déterminer suivant les valeurs de n ()3 4; 1PGCD n n+ +

Exercice 6

Soit n un entier naturel, on note :

2 8 et 3 15a n b n= + = +. On pose();PGCD a bδ=.

1/ Démontrer que pour tout entier naturel n,

δdivise 6.

TS Spé Lycée Beaussier Mathématiques 7

2/ Déterminer l"ensemble des entiers naturels pour lesquels6δ=.

Exercice 7

Soit n un entier naturel. Déterminer suivant les valeurs de n : ()25 7; 1PGCD n n n+ + +.

Exercice 8

Déterminer l"ensemble des diviseurs communs à 656 et 312

Exercice 9

Soient a et b deux entiers naturels non nuls tels que b < a

Démontrer que PGCD (a ; b) = PGCD (a - b ; b)

En utilisant cette propriété, déterminer PGCD (3587 ; 2743).

Exercice 10

Soit p un entier naturel. On sait que 17085 ≡ 12 (p) et 5399 ≡ 2 (p). Déterminer p.

Exercice 11

On dispose d"une plaque rectangulaire dont les dimensions sont 735 mm sur 504 mm On veut découper dans cette plaque des carrés de coté x mm ( x??), sans qu"il y ait de perte de matière. Déterminer les valeurs de x pour lesquelles on peut réaliser un tel découpage. Quelle est la valeur de x maximale et quel est dans ce cas le nombre de carrés découpés.

Exercice 12

1/ Déterminer le PGCD d des nombres a = 4420 et b = 2772.

2/ Déterminer les restes de la division par 5 des entiers : 12

d, 12a, 12b.

Exercice 13

Déterminer tous les couples (a ; b) d"entiers naturels non nuls tels que

PGCD (a ; b) = 14 et a

× b = 2940

Exercice 14

Déterminer tous les couples (a ; b) d"entiers naturels non nuls tels que

PGCD(a ; b) = 56 et a + b = 224.

Exercice 15

Déterminer tous les couples d"entiers naturels non nuls (x ; y) tels que 2 25 ; 8 x y

PGCD x y?

quotesdbs_dbs28.pdfusesText_34

[PDF] conversion notes erasmus

[PDF] correspondance notes lettres

[PDF] conversion notes québec france

[PDF] note sur 20 en gpa

[PDF] tableau de conversion de notes european credit transfer system

[PDF] tableau de conversion des notes

[PDF] b2i adultes ressources

[PDF] b2i adultes greta

[PDF] b2i adultes exercices

[PDF] compétences b2i cm2

[PDF] compétences tice cycle 3 2016

[PDF] compétences tice cycle 2

[PDF] tice programmes 2016

[PDF] b2i nouveaux programmes 2016

[PDF] programmation informatique cycle 3 2016