[PDF] Théorème de Gauss Terminale S Spécialité - PGCD - THEOREME





Previous PDF Next PDF



PGCD Théorème de Bézout Théorème de Gauss

1.1 PGCD de deux nombres entiers naturels . Si la division euclidienne de a par b s'écrit a = bq + r avec 0 <r<b alors D (a ; b)= D (b ; r).



Propriété - Définition (voir démonstration 01)

plus grand commun diviseur de a et b on le note PGCD(a ; b). Démonstration 01. (retour au cours) a et b sont deux entiers naturels non nuls.



PGCD ET NOMBRES PREMIERS

Yvan Monka – Académie de Strasbourg – www.maths-et-tiques.fr. 1. PGCD ET NOMBRES PREMIERS. I. PGCD de deux entiers. 1) Définition et propriétés. Exemple :.



Théorème de Gauss Terminale S Spécialité - PGCD - THEOREME

Chapitre 04 PGCD - Théorème de Bézout - Théorème de Gauss PGCD(a b) = PGCD(b



Terminale S – Spécialité Principales démonstrations 1

Si a = bq + r alors PGCD(a ;b) = PGCD(b ;r). Démonstration. • Si d est un diviseur commun à a et b alors il divise aussi a et bq.



Vdouine – Terminale maths expertes – Arithmétique PGCD et

PGCD a b PGCD b r. = . Cette propriété est à la base de l'algorithme PGCD a b il suffit d'effectuer successivement la division euclidienne de a par.



Vdouine – Terminale S – Chapitre 1 spé – Arithmétique PGCD et

PGCD a b PGCD b r. = . Cette propriété est à la base de l'algorithme d'Euclide. Comment déterminer le PGCD ? Algorithme d'Euclide. Pour déterminer.



Chapitre 2 - Arithmétique des polynômes

Q2)=R2. R1. Si Q1 6= Q2 i.e. Q1. Q2 6= 0



( );q r ( ); ( ); ( );0 ( ) ( ) ( ) ( ) ( ) ( ); ( ); ( ) { } { }

??. ????? ??????? ?????? ??????? a?b. ???? ??? ???? ?? ? ???? a b. D. D. ?. ??????? ????? ???? ??????? a?b. ????? ?? ??. : ( );. PGCD a b.



Synthèse de cours PanaMaths ? Divisibilité et congruences

a b. b r. = La propriété fondamentale précédente conduit à un procédé itératif (algorithme) permettant de calculer le PGCD de deux entiers naturels non nuls 



[PDF] PGCD ET NOMBRES PREMIERS - maths et tiques

On appelle PGCD de a et b le plus grand commun diviseur de a et b et note PGCD(a;b) Remarque : On peut étendre cette définition à des entiers relatifs Ainsi 



[PDF] PGCD - THEOREME DE GAUSS

si r0 = 0 d'après la propriété fondamentale PGCD(a b) = PGCD(b r0) on remplace a par b et b par r0 a b r0 b r0 on effectue la division euclidienne de b 



[PDF] PGCD Théorème de Bézout Théorème de Gauss

Propriété 1 : Soient a et b deux entiers naturels non nuls Si b divise a alors D (a ; b) = D (b) On a donc PGCD (a ; b)= 



[PDF] Propriété - Définition (voir démonstration 01)

L'ensemble des diviseurs communs à a et à b possède un plus grand élément que l'on appelle le plus grand commun diviseur de a et b on le note PGCD(a ; b)



[PDF] Arithmétique des polynômes

2 2 Diviseurs communs - PGCD 2 2 1 pgcd de deux polynômes Proposition 2 8 Soit (AB) 6= (00) 2 (K[X])2 L'ensemble des degrés des diviseurs communs



[PDF] PGCD - PPCM Théorèmes de Bézout et de Gauss - Lycée dAdultes

15 juil 2016 · L'ensemble des diviseurs communs à a et b admet un plus grand élément D appelé plus grand commun diviseur On note : D = pgcd(a b)



[PDF] Arithmétique de & et corps Rinis - Page A Christian PAULY

PGCD (ab) = le + gd des diviseurs communs a etb Remarque: Tout diviseur commun a et too est aussi un diviseur du PGCD



[PDF] chapitre 1 : divisibilité et premiers

Quand on a pgcd(a b)=1 on dit que a est premier avec b ou que a et b sont premiers entre eux Quelques autre propriétés des pgcd : Propriétés 3 3



[PDF] Chapitre 2 Larithmétique des entiers

L'algorithme d'Euclide permettant de calculer le pgcd de deux entiers repose sur cette division et sur le lemme suivant : Lemme 2 11 Soit (a b) ? Z × Z? ; si 



[PDF] Terminale S – Chapitre 1 spé – Arithmétique PGCD et congruences

PGCD a b PGCD b r = Cette propriété est à la base de l'algorithme d'Euclide Comment déterminer le PGCD ? Algorithme d'Euclide Pour déterminer

  • Comment calculer le PGCD AB ?

    La recherche du PGCD par la méthode des divisions euclidiennes est la conséquence du lemme d'Euclide. Lemme d'Euclide : soit un couple d'entiers naturels non nuls (a,b), si des entiers naturels q et r, avec r ? 0, sont tels que a = bq + r , alors : PGCD(a,b) = PGCD(b,r).

  • Comment calculer le PGCD formule ?

    Le PGCD de deux entiers est leur plus grand diviseur commun. Le principe adopté est l'algorithme d'Euclide que l'on peut formellement décrire ainsi : La division entière se définit par A= (B * Q) + R avec A, B, Q, R entiers naturels.

  • Comment calculer le PGCD et le PGCD ?

    Méthode 2 : le tableau des diviseurs premiers
    Cette méthode consiste à diviser simultanément les nombres étudiés par des diviseurs premiers. Le PGCD sera alors le produit de ces diviseurs premiers. Cette méthode est plus rapide et efficace lorsque l'on cherche le PGCD entre deux grands nombres.
  • Pour déterminer le PGCD de deux polynômes on applique l'algorithme d'Euclide, utilisant les divisions euclidiennes successives des polynômes et les résultats suivants : dans la division euclidienne de F par G , si F = G Q + R , alors P G C D ( F , G ) = P G C D ( G , R ) = P G C D ( G , ? R ) où ? est un scalaire non

Chapitre 04 PGCD - Théorème de Bézout - Théorème de Gauss Terminale S Spécialité

PGCD - THEOREME DE BEZOUT - THEOREME DE GAUSS

I- PGCD - Algorithme d"Euclide

1.PGCDExemple

Ecrire sous forme de fraction irréductible la fraction42140. 42

140=2×3×72×7×10=310.

3 et 10 sont premiers entre eux donc la fraction

3

10est irréductible.

On a simplifié par 2×7 = 14, 14 est le PGCD de 42 et de 140, on note PGCD(42;140) = 14. Soient deux entiers naturels non nulsaetb. Ils ont toujours un nombre fini de diviseurs positifs communs. Parmi ces diviseurs, il en existe donc un plus grand que tous les autres.

Définition

Soientaetbdeux entiers naturels non nuls. Le plus grand des diviseurs positifs communs àaet àbest appelé " plus grand commun diviseur » ou PGCD de aetb, on le note PGCD(a;b). On remarque que PGCD(a;b) = PGCD(|a|;|b|), on s"intéressera donc dans la suite au

PGCD de deux entiers naturels.

Propriété

Soitaetbdeux entiers naturels non nuls.

Sibdivisea, alors PGCD(a;b) =b.

Démonstration

Les diviseurs communs àaet àbsont les diviseurs deb.

En effet, siddiviseaetb, c"est un diviseur deb.

Réciproquement siddiviseb, alors, commebdivisea,ddiviseb.

2.Algorithme d"EuclidePropriété fondamentale

Soientaetbdeux entiers non nuls.

Sia=bq+roùqetrsont deux entiers non nuls, alors PGCD(a,b) = PGCD(b,r).

Démonstration

On va montrer queaetbont les mêmes diviseurs communs quebetr. •Soitdun diviseur deaetb, alorsddivisea-bq=r, c"est donc un diviseur commun

àbet àr.

•Réciproquement, soitd?un diviseur commun àbet àr, alorsd?divisebq+r=a, c"est donc un diviseur commun àaet àb.

Donc PGCD(a,b) = PGCD(b,r).

Calcul du PGCD par l"algorithme d"Euclide

Soientaetbdeux entiers naturels non nuls avecb < a. 1

Chapitre 04 PGCD - Théorème de Bézout - Théorème de Gauss Terminale S Spécialité

•On effectue la division euclidienne deaparb,a=b×q0+r0avecr0< b. sir0= 0 ,b/a, donc PGCD(a,b) =b. •sir0?= 0, d"après la propriété fondamentale, PGCD(a,b) = PGCD(b,r0). on remplaceaparbetbparr0, abr0 br0 on effectue la division euclidienne debparr0:b=r0×q1+r1avecr1< r0. sir1= 0,r0/bdonc PGCD(a,b) = PGCD(b,r0) =r0.

•sir1?= 0, PGCD(b,r0) = PGCD(r0,r1)

on remplacebparr0etr0parr1, abr0 br0r1 r0r1 on effectue la division euclidienne der0parr1:r0=r1×q2+r2avecr2< r1. sir2= 0,r1/r0donc PGCD(a,b) = PGCD(b,r0) = PGCD(r0,r1) =r1. •sir2?= 0, PGCD(a,b) = PGCD(b,r0) = PGCD(r0,r1) = PGCD(r1,r2)

On réitère le procédé, on obtient une suite de restesr0,r1,r2,···d"entiers naturels

tels quer0> r1> r2>···, cette suite est nécessairement finie, c"est à dire qu"au bout d"un certain nombre d"étapes, on va nécessairement obtenirun reste nul.

Soitrnle dernier reste non nul.

Alors PGCD(a,b) = PGCD(b,r0) = PGCD(r0,r1) = PGCD(r1,r2) =···= PGCD(rn-1,rn) = r ncar on arn-1=qn+1rn, doncrndivisern-1. abr0 br0r1 r0r1r2 rn-1rn0

Propriété

Lorsquebne divise pasa, le PGCD des entiers naturels non nulsaetbest le dernier reste non nul dans l"algorithme d"Euclide.

Exemple

Calculer le PGCD de 1636 et 1128 avec l"algorithme d"Euclide. abreste

16361128508

1128508112

50811260

1126052

60528
5284
840

PGCD(1636 , 1128) = 4

2

Chapitre 04 PGCD - Théorème de Bézout - Théorème de Gauss Terminale S Spécialité

Programmation sur la calculatriceTICasio

Entrer les valeurs deaetbPrompt A,B "A="←??→A←?"B="←??→B←? Tant queb?= 0 (début de la boucle) While B?= 0 While B?= 0

Partie entière dea

b→qInt(A/B)→Q Intg(A÷B)→Q←? a-bq→rA-B*Q→R A-B×Q→R←? b→aB→A B→A←? r→bR→B R→B←?

Fin de la boucle End WhileEnd

Afficher la valeur deaDisp A A?

(c"est le dernier reste non nul, c"est à dire le PGCD deaetb)

3.Propriétés du PGCD

Propriété 1

Soitaetbdeux entiers naturels non nuls. Les diviseurs communs àaet

àbsont les diviseurs du PGCD deaet deb.

Démonstration

Dans l"algorithme d"Euclide, les diviseurs communs deaetbsont les diviseurs com- muns debetr0, der0etr1,···, dern-1errn= PGCD(a,b). Commern/rn-1, ce sont les diviseurs dern= PGCD(a,b).

Propriété 2

Soientaetbdeux entiers naturels non nuls.

Pour tout entier naturelknon nul, PGCD(ka,kb) =kPGCD(a,b).

Démonstration

Dans l"algorithme d"Euclide, il suffit de multiplier chaque ligne park.

Exemple

Déterminer PGCD(100;70).

PGCD(100;70) = 10PGCD(10;7).

On cherche PGCD(10;7) par l"algorithme d"Euclide :

10 = 7 + 3

7 = 2×3 + 1

On a donc PGCD(10;7) = 1 et PGCD(100;70) = 10.

4.Entiers premiers entre euxDéfinition

Deux entiers naturelsaetbsont dits premiers entre eux si PGCD(a,b) = 1.

Exemple

Montrer que, pour tout entier naturelnnon nul,net 2n+ 1 sont premiers entre eux. Soitdun diviseur commun ànet 2n+ 1, alorsddivise 2n+ 1-2n= 1 , doncd= 1, net 2n+ 1 sont donc premiers entre eux. Ou bien, d"après la propriété fondamentale : PGCD(2n+ 1,n) = PGCD(n,1) = 1.

Propriété

Soientaetbdeux entiers naturels non nuls.

PGCD(a,b) =dsi et seulement sia=da?etb=db?aveca?etb?entiers naturels premiers entre eux.

Démonstration

•Si PGCD(a,b) =d,a=da?etb=db?, aveca?etb?entiers naturels. PGCD(da?,db?) =d=dPGCD(a?,b?), donc PGCD(a?,b?) = 1. 3

Chapitre 04 PGCD - Théorème de Bézout - Théorème de Gauss Terminale S Spécialité

•Sia=da?etb=db?aveca?etb?entiers naturels premiers entre eux, alors

PGCD(a,b) =dPGCD(a?,b?) =d.

Exemple

Déterminer tous les couples d"entiers naturels (a,b) tels que : ?ab= 1452

PGCD(a,b) = 11.

a= 11a?etb= 11b?, aveca?etb?premiers entre eux. ab= 1425?11a?×11b?= 1452?a?b?= 12. Ensemble des diviseurs positifs de 12 :{1;2;3;4;6;12}

•a?= 1,b?= 12, alorsa= 11,b= 132

•a?= 3,b?= 4, alorsa= 33,b= 44

•a?= 4,b?= 3, alorsa= 44,b= 33

•a?= 12,b?= 1, alorsa= 132,b= 11

sont les seuls couples solutions.

S={(11;132),(33;44),(44;33),(132;11)}.

II- Identité de Bézout - Théorème de Bézout

1.Identité de BézoutPropriété

aetbdésignent deux entiers naturels non nuls. Soitd= PGCD(a,b). Il existe deux entiers relatifsuetvtels queau+bv=d.

Démonstration

SoitEl"ensemble des entiers naturels non nuls qui s"écrivent sous la formeau+bv, où uetvsont deux entiers relatifs. En"est pas vide, il contienta=a×1 +b×0 etb=a×0 +b×1. Soitcle plus petit élément deE(cs"écrit sous la formeau0+bv0,u0etv0étant deux entiers relatifs) etdle PGCD deaet deb. On va montrer quec=d, et pour celà, montrer d"abord qued/cpuis quec/d.

•d/aetd/bdoncddivisec=au0+bv0.

•Pour montrer quecdivised, on montre qu"il diviseaetb. On effectue la division euclidienne deaparc:a=cq+roùqetrsont des entiers avec 0?r < c. On a alorsr=a-cq=a-(au0+bv0)q=a(1-u0q)+b(v0q), donc nécessairement r= 0 (sir >0 alorsr?Eetr < cest contradictoire), par conséquentc/a.

On montre de même quec/b.

On a montré qued=c=au0+bv0.

Exemple

En utilisant l"algorithme d"Euclide, déterminer deux entiers relatifsuetvtels que au+bv= PGCD(a,b) poura= 145 etb= 55.

145=55×2+35

55
=35×1+20 35
=20×1+15 20 =15×1+5

15=5×3

4

Chapitre 04 PGCD - Théorème de Bézout - Théorème de Gauss Terminale S Spécialité

donc PGCD(145,55) =5. Pour déterminer les coefficients de Bézout, on remonte l"algorithme d"Euclide :

5=20-15×1

20-(35-20×1)×1

20×2-35

= (55-35×1)×2-35 =55×2-35×3

55×2-(145-55×2)×3

145×(-3)+55×8

on a donc bien

5=au+bvavecu=-3 etv= 8.

Remarque

: Les coefficients ne sont pas uniques.

On a également 5 = 145×8 + 55×(-21).

2.Théorème de BézoutThéorème

Soientaetbdeux entiers naturels non nuls.

aetbsont premiers entre eux si et seulement si il existe deux entiers relatifsuetv tels queau+bv= 1.

Démonstration

•Siaetbsont premiers entre eux, alors PGCD(a,b) = 1. D"après la propriété précédente, il existe deux entiers relatifsuetvtels queau+ bv= 1 . •RéciproquementSi il existe deux entiers relatifsuetvtels queau+bv= 1, sidest un diviseur positif deaet deb, alorsddiviseau+bv, soitddivise 1, par conséquentd= 1. aetbont 1 pour unique diviseur commun, ils sont donc premiers entre eux.

Exemple

netn+ 1 sont premiers entre eux, en effet (n+ 1)×1 +n×(-1) = 1.

III- Théorème de Gauss

Théorème

Soienta,betctrois entiers naturels non nuls.

Siadivisebcet siaest premier avecb, alorsadivisec.

Démonstration

Siaest premier avecb, alors, d"après le théorème de Bézout, il existe deux entiers relatifs

uetvtels queau+bv= 1.quotesdbs_dbs27.pdfusesText_33
[PDF] pgcd(ka kb)=k pgcd(a b)

[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