PGCD a b = Démonstration : Comme a et a ainsi que b et b ont même ensemble de PGCD ka kb divise la combinaison entière( ) ( ) ka u kb v + , alors
Previous PDF | Next PDF |
[PDF] PGCD ET NOMBRES PREMIERS - maths et tiques
Démonstration : a divise bc donc il existe un entier k tel que bc = ka a et b sont premiers entre eux donc il existe deux entiers relatifs u et v tels que : au + bv = 1
[PDF] PGCD - lycée Beaussier
PGCD a b = Démonstration : Comme a et a ainsi que b et b ont même ensemble de PGCD ka kb divise la combinaison entière( ) ( ) ka u kb v + , alors
[PDF] PGCD - Free
Soit m = PPCM(a; b) Si c est un multiple commun de a et b alors m divise c Propriété 6 Soient a , b et k trois entiers naturels non nuls Alors PPCM(ka; kb) = k ×
[PDF] pgcd, ppcm 1 Plus grand commun diviseur (pgcd) Remarque Soit a
pgcd(a, ka) = a (k ∈ * ) : en effet, d est un diviseur commun à a et à ka si et seulement si d est un diviseur de a Donc l'ensemble des diviseurs communs à a et à
[PDF] PGCD et PPCM de deux entiers : - Blog Ac Versailles
Remarque : le PGCD de deux entiers naturels est un entier au moins égal à 1 Comme d divise a et b, kd divise ka et kb, donc kd divise leur PGCD d , donc kd
[PDF] Bezout, Gauss, pgcd
ment appelé plus grand commun diviseur (le 〈〈 pgcd〉〉 ) de a et b et noté pgcd(a entre eux si, quels que soient i, j ∈ [1,k], tels que i = j les entiers ai et
[PDF] 1 PGCD
Tout diviseur commun à a et b divise PGCD(a;b) 3 Soit k entier naturel , PGCD( ka; kb) = kPGCD(a; b) 4 Deux entiers a et b sont premiers entre eux si et
[PDF] pgcd et ppcm (g)
Exercice g 3 Soient a, b ∈ N strictement positifs Soit k > 0 un entier Montrez que pgcd(ka, kb) = k pgcd
[PDF] Terminale S Spécialité Cours : PGCD - Théorème de Bézout
Propriétés : Soit a, b et k des entiers relatifs non nuls • Si b divise a, alors PGCD( a ;b) = b • PGCD(ka ;kb)
[PDF] PGCD - PPCM Théorèmes de Bézout et de Gauss - Lycée dAdultes
15 juil 2016 · Pour tout entier naturel k non nul, on a : pgcd(ka, kb) = k pgcd(a, b) 1 2 Nombres premiers entre eux Définition 2 : On dit que a et b sont
[PDF] correspondance notes lettres
[PDF] conversion notes québec france
[PDF] équivalence note américaine française université
[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] PGCD - lycée Beaussier [PDF] PGCD - lycée Beaussier](https://pdfprof.com/Listes/17/16495-175_pgcd.pdf.pdf.jpg)
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"ensembleC 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 2Dé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édenteExemple :
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 posons0m 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 bDé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 balors 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) =
0nrDé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 entier0n tel que00nr≠et010nr+=.
Par le théorème d"Euclide, tant que
0nr≠,
00 10 1 1 2
0 0 10 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 10 0 1 002 11
n n nn n nn nCar r r q r
par constructionet en utilisant le théorème d EuclidePGCD r r PGCD r rMaintenant :
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 5Aller dans le menu Programme
Sélectionner New
"A" :? → A "B" :? → B1 → R
While R > 0
Int (A
÷B) → Q ?
A-B Q×→ R ?
"Q" : Q "R" : RB → A
R → B
WhileEnd
"PGCD=" : AExemple :
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 ►►
IntTaper 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 PRGMCasio 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 6Propriété 5 :
Soient a et b deux entiers naturels non nuls et k un entier relatif non nulOn 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 diviseEnsuite,
();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.