[PDF] [PDF] Arithmétique Dans le cours entier sera

View - Download [PDF] Arithmétique

Previous PDF

Next PDF

Maths discr`etes, 2006-2007Universit´e Paris-Sud

Arithm´etique

1 Les ensemblesNetZ

N={0,1,2,3,...}est l"ensemble des entiers naturels. Z={...,-2,-1,0,1,2,3,...}est l"ensemble des entiers relatifs. N ?=N\ {0}(entiers strictement positifs) etZ?=Z\ {0}(entiers relatifs non nuls). Dans le cours, entier sera synonyme d"entier relatif.

Par exemple, sin >0 alorsn≥1.

Propri´et´e 1.Toute partie non vide deNadmet un plus petit ´el´ement.

2 Divisibilit´e dansZ

a) Diviseurs et multiples

D´efinition.Soitaetbdeux entiers. On dit queadivisebs"il existe un entierktel queb=ka. On notea|b.

On dit ´egalement queaest undiviseurdebou quebest unmultipledea.

Exemples.

•3 divise 6 car 6 = 2×3.-3 divise ´egalement 6 car 6 = (-2)×(-3).

De fa¸con g´en´erale, sib|aalors (-b)|a.

•Pour toutn?Z,n+ 1 divisen2-1 carn2-1 = (n-1)(n+ 1).

Diviseurs particuliers.

•Tout entieradivise 0 car 0 = 0.a, mais 0 ne divise aucun entierb?= 0. •Tout entiernadmet 1,-1,net-ncomme diviseurs carn= 1×n= (-1)×(-n). •Les seuls diviseurs de 1 sont 1 et-1. b) Propri´et´es

Soita,b,cdes entiers relatifs.

diviseurs. Preuve. On suppose dans un premier temps queaetbsont positifs.adivisebdonc il existe un entierktel queb=ka. Commeb?= 0, on aa?= 0etk?= 0. Comme il s"agit d"entiers naturels,a≥1etk≥1. On a qui est un ensemble fini. autrement dita? {-|b|,...,-1,1,2,...,|b|}qui est un ensemble fini.? Propri´et´e 3.Siadivisebetbdiviseaalorsa=boua=-b. Preuve.adivisebdonc il existek?Ztel queb=ka.bdiviseadonc il existek??Ztel quea=k?b. On a

alorsa=kk?a. Sia?= 0alorskk?= 1, ce qui implique queketk?sont tous les deux ´egaux `a1ou `a-1, et par

cons´equenta=boua=-b. Sia= 0, alorsb=ka= 0.? Propri´et´e 4.Siadivisebetbdivisecalorsadivisec. Preuve. Par hypoth`ese, il existe des entiersk,k?tels queb=kaetc=k?b. On a alorsc=kk?a, donca|c.? Propri´et´e 5.Siadivisebetc, alors, pour tous entiersnetm,adivisenb+mc. Preuve. Par hypoth`ese, il existe des entiersketk" tels queb=kaetc=k?a. Doncnb+mc= (nk+mk?)aest un multiple dea.? 1 Cons´equences : siadivisebetc, alorsadivisenb(on prendm= 0),adivise (b+c) (on prendn=m= 1),a divise (b-c) (on prendn= 1,m=-1). La propri´et´e 5 se g´en´eralise sans difficult´e `a 3 termes ou plus.

Exemples.

•Pour toutn?Z, 3 divise 3n-6 car 3|3 et 3|6.

•Montrons que pour toutn?N, 9 diviseun= 4n+ 6n-1. On montre le r´esultat par r´ecurrence1surn.

- Initialisation :u0= 0 est divisible par 9. - On suppose que 9 diviseun. On ´ecrit u n+1= 4·4n+ 6(n+ 1)-1 = 4(un-6n+ 1) + 6(n+ 1)-1 = 4un-18n+ 9.

9 diviseun(hypoth`ese de r´ecurrence), et 9 divise 18 et 9, donc 9 diviseun+1= 4un+ 18n-9.

- Conclusion : 9 diviseunpour toutn?N.

3 Nombres premiers

a) Reconnaˆıtre un nombre premier D´efinition.On dit qu"un entier naturelnestpremiers"il a exactement 2 diviseurs positifs : 1 etn. Remarque.1 n"est pas premier, il a un seul diviseur positif, qui est 1.

0 n"est pas premier, il a une infinit´e de diviseurs.

Exemple.2,3,5,7 sont des nombres premiers.

Lemme 6.Soitnun entier,n≥2. Son plus petit diviseur positif diff´erent de 1 est un nombre premier.

En particulier, tout entiern≥2 a au moins un diviseur premier.

Preuve. L"ensemble des diviseurs positifs dendiff´erents de1est non vide car il contientn. Donc il admet

(propri´et´e 2). De plus,d|n(propri´et´e 4 avecd|petp|n), doncd≥ppar choix dep. Doncd=p. On en d´eduit

quepa un unique diviseur positif diff´erent de1, doncpest un nombre premier.? n, alorsnest un nombre premier.

Preuve. Soitn≥2. On suppose quenn"est pas premier. Soitple plus petit diviseur positif dendiff´erent de1.

Par le lemme 6,pest premier. On ´ecritn=pq, avecq?N?. Siq= 1alorsn=pest premier, ce qui est exclu,

doncq≥2. Commeqest un diviseur positif dendiff´erent de1,q≥ppar choix dep. Doncn=pq≥p2,

n. n. Par contrapos´ee n, alorsnest premier.?

Application.On consid`eren= 29. On a⎷

29?5,4. Les nombres premiers inf´erieurs `a⎷29 sont 2,3,5. Aucun

ne divise 29, donc 29 est premier. b) Ensemble des nombres premiers Th´eor`eme 8. Il existe une infinit´e de nombres premiers.

Preuve. Faisons une preuve par l"absurde

3. Supposons qu"il n"y a qu"un nombre fini de nombres premiers,notons-

lesp1,...,pn. On poseN=p1p2···pn+ 1.N >1doncNa au moins un diviseur premierp(lemme 6), etp

est n´ecessairement ´egal `apipour un certaini? {1,...,n}. Doncpdivisep1p2···pn. Orpdivise ´egalementN,

doncpdiviseN-p1p2···pn= 1(propri´et´e 5). C"est impossible. Conclusion : il existe une infinit´e de nombres

premiers.?

1Un raisonnement par r´ecurrence comporte toujours 3 ´etapes :

- Initialisation : on v´erifie la propri´et´e pourn=n0.

- Passage den`an+ 1 : on suppose que la propri´et´e est vraie au rangn≥n0, on en d´eduit qu"elle est vraie au rangn+ 1.

- Conclusion : la propri´et´e est vraie pour toutn?N,n≥n0. 2

Raisonnement par contrapos´ee : on veut montrer que si la propri´et´ePest vraie, alors la propri´et´eQest vraie aussi; il est

´equivalent de montrer que si la propri´et´eQest fausse, alors la propri´et´ePest fausse aussi.

3Raisonnement par l"absurde : on suppose que la propri´et´ePest fausse, on en d´eduit un r´esultat impossible, on conclut que la

propri´et´ePest vraie. 2

c) D´ecomposition en produit de facteurs premiersTh´eor`eme 9. Tout entiern≥2 peut s"´ecrire de fa¸con unique

n=p1p2···pr,

Remarque.

•Sir= 1, le produit est r´eduit `a un facteur :n=p1.

•Si lespine sont pas ordonn´es, la d´ecomposition n"est pas unique. Par exemple, 6 = 2×3 = 3×2.

Preuve.

Existence de la d´ecomposition.

Montrons par r´ecurrence surnque tout entiern≥2peut s"´ecriren=p1p2···pr, •n= 2est premier, on a la d´ecomposition voulue avecp1= 2etr= 1. plus petit diviseur positif dendiff´erent de1est un nombre premier. On le notep1. On posem=n p1?N?. On distingue deux cas : - Sim= 1alorsn=p1et on a la d´ecomposition voulue (r= 1). - Sim≥2, on peut appliquer l"hypoth`ese de r´ecurrence `amcarm=n

demet qu"on a num´erot´e `a partir de2). On a alorsn=p1m=p1p2...pr. Les nombres premiersp2,...,pr

la d´ecomposition voulue. •Conclusion : tout entiern≥2a une d´ecomposition de la forme voulue.

Unicit´e de la d´ecomposition.

Nous verrons la preuve de l"unicit´e apr`es le th´eor`eme deGauss (section 6).?

La preuve de l"existence de la d´ecomposition en produit de facteurs premiers donne la m´ethode pour trouver

en pratique cette d´ecomposition. Exemple.180 = 2×90 = 2×2×45 = 2×2×3×15 = 2×2×3×3×5.

Quand on a d´ej`a un produit, il suffit de d´ecomposer les facteurs. Exemple : 15×10 = (3×5)×(2×5) = 2×3×5×5.

D´efinition.Soitn?N?etpun nombre premier.

•Sipdivisen, on dit quepest unfacteur premierden •Le plus grand entierktel quepkdivisens"appellel"exposant depdansn.

Dans la d´ecomposition en facteurs premiers, on regroupe les nombres premiers identiques et on ´ecrit

n=pα11pα22···pαss

o`up1,...,pssont des nombres premiers tels quep1< p2<···< psetα1,...,αssont des entiers strictement

positifs.

L"exposant depidansnestαi. Sipn"apparaˆıt pas dans la d´ecomposition, son exposant est 0.

Exemple.n2n"a que des exposants pairs carn2=p2α11p2α22···p2αss.

180 = 2

2×32×5 n"est pas un carr´e. 22×76= (2×73)2est un carr´e.

Application `a la divisibilit´e :

Th´eor`eme 10. Soitaetbdes entiers strictement positifs. Pour tout nombre premierp, notons α(p) l"exposant depdansaetβ(p) l"exposant depdansb. Alorsadivisebsi et seulement si

Preuve. Siadivisebalors il existe un entierqtel queb=aq. La d´ecomposition en facteurs premiers debest

obtenue en multipliant la d´ecomposition deapar celle deq, doncβ(p)≥α(p)pour tout nombre premierp.

premiers deaet deb. On ´ecrit a=pα(p1)

1pα(p2)

2···pα(pr)retb=pβ(p1)

1pβ(p2)

2···pβ(pr)r.

On a alorsb=aqavecq=pβ(p1)-α(p1)

1pβ(p1)-α(p2)

2···pβ(pr)-α(pr)r(qest bien un entier carβ(pi)-α(pi)≥0

par hypoth`ese). Doncadiviseb.? 3 Exemples.•15 = 3×5 = 20×31×51divise 180 = 22×32×51. •25 = 52ne divise pas 180.

•20 = 22×5, donc les diviseurs positifs de 20 sont de la forme 2α5βavecα= 0, 1 ou 2 etβ= 0 ou 1.

d) Crible d"

´Eratosth`ene

Le crible d"

´Eratosth`ene4est un algorithme pour trouver tous les nombres premiers inf´erieurs `a un entierNfix´e.

- On ´ecrit tous les entiers de 1 `aN. On barre 1 qui n"est pas premier.

- Le premier entier non barr´e est 2, il est premier. On barre tous ses multiples sauf lui-mˆeme.

- Le premier entier non barr´e est 3, il est premier. On barre tous ses multiples sauf lui-mˆeme.

- On r´ep`ete l"op´eration.`A chaque ´etape, le premier entier non barr´e est premier (car il n"est divisible par aucun

nombre premier plus petit). On s"arrˆete au moment o`u on consid`ere un nombre premierp >⎷

N(les entiers

navec⎷ n). - L"ensemble des nombres premiers inf´erieurs `aNest alors l"ensemble des entiers non barr´es.

Exemple avecN= 100.

1 2 34 56 78910

11

12 13141516 1718 1920

2122 232425262728 2930

31

3233343536 37383940

41

42 43444546 47484950

5152 535455565758 5960

61

6263646566 67686970

71

72 737475767778 7980

8182 838485868788 8990

919293949596 979899100

Remarque.Quand on consid`ere le nombre premierp, il suffit de barrer les multipleskpaveck≥pcar les

multiples plus petits ont d´ej`a ´et´e barr´es `a une ´etapepr´ec´edente.

4´Eratosth`ene est un math´ematicien et philosophe grec du IIIe si`ecle avant J.C.

4

De plus,qetrsont uniques.

Preuve.

Existence deqetr.

Supposons pour commencer quea?N. Commeb≥1, l"ensemble desn?Ntels quebn > a

est non vide, donc il a un plus petit ´el´ementk?N. Sik= 0alorsa <0 =kb, ce qui est exclu, donck≥1. Par

Supposons maintenanta?Z,a <0. Posonsa?=-a >0. Par ce qui pr´ec`ede, il existe des entiersq?etr?tels

•Sir?= 0,a=-a?=-q?b. On poseq=-q?etr= 0, et on a biena=bq+r. •Sir?>0, on ´ecrita= (-q?b-r?)-b+b=b(-q?-1) + (b-r?). On poseq=-q?-1etr=b-r?. On a a=bq+ret comme0< r?< b, on a0< r < b. C"est l"´ecriture recherch´ee.

Unicit´e deqetr.

donc|r2-r1|< b. Par cons´equent,r2-r1= 0, autrement ditr1=r2. Commeb?= 0, l"´egalit´eb(q1-q2) = 0

entraˆıneq1-q2= 0, soitq1=q2. D"o`u l"unicit´e des entiersqetr.? D´efinition.Soita?Zetb?N?. Effectuer ladivision euclidiennedeaparb, c"est trouver les entiersqet

La division euclidienne est la division avec reste qu"on apprend `a l"´ecole primaire. Sia≥0 alorsq≥0.

Exemple.a= 100,b= 7. 100

7 -714 30
-28 2

Le quotient estq= 14, le reste estr= 2.

Remarque.Le reste de la division euclidienne deaparbest nul si et seulement sibdivisea. b?(partie enti`ere deab).

Preuve.

a Les restes possibles de la division euclidienne denparbsont 0,1,2,...,b-1.

En prenantb= 2, on voit que tout entiernpeut s"´ecrire sous la formen= 2q(r= 0) oun= 2q+ 1 (r= 1).

De mˆeme, tout entiernpeut s"´ecrire sous la formen= 3koun= 3k+ 1 oun= 3k+ 2 (en prenantb= 3). Exemple.Soitn?Z. Montrons quen(n+ 1) est multiple de 2. On ´ecritn= 2k+ravecr= 0 our= 1. - Cas 1 :r= 0.n= 2kdoncn(n+ 1) = 2k(n+ 1). - Cas 2 :r= 1.n= 2k+ 1 doncn(n+ 1) =n(2k+ 2) = 2n(k+ 1).

Dans les deux cas,n(n+ 1) est un multiple de 2.

5 PGCD et PPCM

a) PGCD Soitaetbdeux entiers non nuls. 1 diviseaetbdoncaetbont au moins un diviseur commun. Commeaetb

ont un nombre fini de diviseurs, ils ont un nombre fini de diviseurs communs. Ceci justifie la d´efinition suivante.

D´efinition.Soita,b?Z?. Le plus grand entier qui divise `a la foisaetbs"appelle leplus grand commun

diviseuroupgcddeaetb. On le notepgcd(a,b).

Exemple.pgcd(6,9) = 3 car les diviseurs positifs de 6 sont 1,2,3,6 et les diviseurs positifs de 9 sont 1,3,9.

Remarques.

•pgcd(a,b)≥1 car 1 est un diviseur commun `aaetb. •pgcd(a,b) = pgcd(b,a).

•pgcd(a,b) = pgcd(|a|,|b|) car un nombre et son oppos´e ont les mˆemes diviseurs. On peut donc toujours se

ramener `a des entiers strictement positifs. 5 Propri´et´e 13.Soita,b?N?. Siadivisebalors pgcd(a,b) =a. Preuve. Tout diviseur deaest un diviseur deb, etaest le plus grand diviseur dea.? Application de la d´ecomposition en facteurs premiers au calcul de pgcd : Th´eor`eme 14. Soita,b?N?etpun nombre premier. Soitα(p) l"exposant depdansaetβ(p) l"exposant depdansb. Alors l"exposant depdans pgcd(a,b) est min(α(p),β(p)).

Preuve. Soitdun diviseur positif commun `aaetb. Pour tout nombre premierp, notonsγ(p)l"exposant de

R´eciproquement, tout entier positif dont les exposants sont inf´erieurs o`u ´egaux `amin(α(p),β(p))est un diviseur

commun `aaetb. Le plus grand diviseur commun est donc obtenu quand pour tout nombre premierp, l"exposant

est le plus grand possible, c"est-`a-dire ´egal `amin(α(p),β(p)).?

Exemple.a= 24×5×72

= 2

4×30×51×72,b= 22×3×52

= 2

2×31×52×70. pgcd(a,b) = 22×30×51×70= 20.

b) Algorithme d"Euclide

Lemme 15 (lemme d"Euclide

5).Soita,b?Z?. S"il existe des entiersqetravecr?= 0 tels quea=bq+r

alors les diviseurs communs `aaetbsont exactement les diviseurs communs `abetr, et pgcd(a,b) = pgcd(b,r).

Preuve. Soitdun diviseur commun `aaetb.ddiviseaetb, doncddivisea-bq=r. Doncdest un diviseur commun `abetr. R´eciproquement, sid?un diviseur commun `abetr, alorsd?divisebq+r=a. Doncd?est un diviseur commun `aaetb.

On en d´eduit que les diviseurs communs `aaetbsont exactement les diviseurs communs `abetr. En prenant

le plus grand diviseur commun, on obtientpgcd(a,b) = pgcd(b,r).?

Exemple.Calculonsd= pgcd(273,12).

On fait la division euclidienne de 273 par 12 : 273 = 22×12 + 9. Doncd= pgcd(12,9). On fait la division euclidienne de 12 par 9 : 12 = 9 + 3. Doncd= pgcd(9,3).

Comme 3 divise 9, on obtientd= 3.

Algorithme d"Euclide.

Soita,b?N?. On cherched= pgcd(a,b). On effectue des divisions euclidiennes successives tant que le reste

est non nul. a=bq1+r1r1< b d= pgcd(b,r1) b=r1q2+r2r2< r1d= pgcd(r1,r2) r

1=r2q3+r3r3< r2d= pgcd(r2,r3)

r n-2=rn-1qn+rnrn< rn-1d= pgcd(rn-1,rn) r n-1=rnqn+1+ 0rn+1= 0 r

kest une suite strictement d´ecroissante d"entiers naturels donc, au bout d"un certain temps, on tombe sur un

reste nul et l"algorithme s"arrˆete. Sirn+1= 0 alorsrndivisern-1, donc pgcd(rn-1,rn) =rn. Th´eor`eme 16. Le pgcd deaetbest le dernier reste non nul obtenu par l"algorithme d"Euclide. Remarque.Sir1= 0, c"est quebdivisea, donc pgcd(a,b) =b(l"algorithme s"arrˆete imm´ediatement). Th´eor`eme 17. Soita,b?Z?. Siddiviseaetbalorsddivise pgcd(a,b).

Preuve. On se place d"abord dans le cas o`ua,b?N?. On reprend les notations de l"algorithme d"Euclide. Par

le lemme d"Euclide, les diviseurs communs `aaetbsont les diviseurs communs `abetr1, `ar1etr2,..., `arn-1

etrn. Commerndivisern-1, ce sont les diviseurs dern. Par cons´equent,ddivisernpuisque c"est un diviseur

commun `aaetb. Orrn= pgcd(a,b)par l"algorithme d"Euclide.

Sia,b?Z?, on se ram`ene au cas pr´ec´edent en remarquant que les diviseurs communs `aaetbsont les diviseurs

communs `a|a|et|b|, etpgcd(a,b) = pgcd(|a|,|b|).?

5Euclide est un c´el`ebre math´ematicien grec du IIIe si`ecle avant J.C.

6 Propri´et´e 18.Sia,b,k?Z?, pgcd(ka,kb) =|k|pgcd(a,b). Preuve. On se place d"abord dans le cas o`ua,b,k?N?. On noter1,...,rnetrn+1= 0les restes obtenus dekaetkbavec l"algorithme d"Euclide, on trouve les restes successifskr1,kr2,...,krnetkrn+1= 0. Donc pgcd(ka,kb) =krn=kpgcd(a,b). Sia,b?Z?, il suffit de remarquer quepgcd(ka,kb) = pgcd(|ka|,|kb|) =|k|pgcd(|a|,|b|) =|k|pgcd(a,b).? Exemple.pgcd(1200,900) = 100 pgcd(12,9) = 100×3 = 300. c) Nombres premiers entre eux D´efinition.Soitaetbdeux entiers non nuls. On dit queaetbsontpremiers entre euxsi pgcd(a,b) = 1.

On dit aussi queaest premier avecb.

Exemples.

•15 et 26 sont premiers entre eux. •Deux nombres premiers diff´erents sont premiers entre eux.

Propri´et´e 19.Deux entiers strictement positifs sont premiers entre eux si et seulement s"il n"ont aucun facteur

premier commun. Preuve. C"est une cons´equence du th´eor`eme 14.? Propri´et´e 20.Soita,bdeux entiers non nuls etd= pgcd(a,b). Alorsa detbdsont premiers entre eux.

Preuve. Soite= pgcd?a

d,bd?. Il faut montrer quee= 1. Commeediviseadetbd, il existe des entiersa?,b?tels que a

Une fraction est irr´eductible si le num´erateur et le d´enominateur sont premiers entre eux. Pour obtenir une

fraction irr´eductible ´egale `a p q, il suffit de simplifier par le pgcd : p q=p?q?avecp?=ppgcd(p,q)etq?=qpgcd(p,q). Par la proposition 20, pgcd(p?,q?) = 1. d) PPCM Soitaetbdeux entiers non nuls.abest un multiple commun `aaetb,|ab|>0 aussi. Par cons´equent,aetb

ont au moins un multiple commun strictement positif, ce qui rend possible la d´efinition suivante.

D´efinition.Soitaetbdeux entiers non nuls. Le plus petit entier strictement positif qui est `a la fois multiple

deaetbs"appelle leplus petit commun multipleouppcmdeaetb. On le noteppcm(a,b).

Exemple.ppcm(4,6) = 12.

Le ppcm sert `a mettre des fractions au mˆeme d´enominateur : 1

4+16=312+212=512.

Remarques.

•ppcm(a,b) = ppcm(b,a).

•ppcm(a,b) = ppcm(|a|,|b|) car un nombre et son oppos´e ont les mˆemes multiples. On peut donc toujours se

ramener `a des entiers strictement positifs.

Propri´et´e 21.Soita,b?Z?. Sicest un multiple commun `aaetb, alorscest un multiple de ppcm(a,b).

adivisemetc, doncadivisec-qm=r. De mˆeme,bdiviser. Par cons´equent,rest un multiple commun `a

0< r < m. Doncr= 0, etcest un multiple dem= ppcm(a,b).?

Application de la d´ecomposition en facteurs premiers au calcul de ppcm : Th´eor`eme 22. Soita,b?N?etpun nombre premier. Soitα(p) l"exposant depdansaetβ(p) l"exposant depdansb. Alors l"exposant depdans ppcm(a,b) est max(α(p),β(p)). La preuve est analogue `a celle du th´eor`eme 14. 7

Exemple.a= 24×5×72

= 2

4×30×51×72,b= 22×3×52

= 2

2×31×52×70. ppcm(a,b) = 24×31×52×72.

Th´eor`eme 23. Soita,b?Z?. Alors pgcd(a,b).ppcm(a,b) =|ab|.

Preuve. On se place d"abord dans le cas o`ua,b?N?. Soitp1,...,pnles nombres premiers qui apparaissent dans

les d´ecompositions deaetb. On ´ecrita=pα11···pαnnetb=pβ11···pβnn(avecαi,βi?Npouri? {1,...n}).

Par les th´eor`emes 14 et 22, on sait que

pgcd(a,b) =pγ11···pγnnavecγi= min(αi,βi)pouri? {1,...,n}, ppcm(a,b) =pδ11···pδnnavecδi= max(αi,βi)pouri? {1,...,n}. Donc pgcd(a,b).ppcm(a,b) =pγ1+δ11···pγn+δnn=pα1+β11···pαn+βnn. Orab=pα1+β11···pαn+βnn. Doncpgcd(a,b).ppcm(a,b) =ab. Sia,b?Z?, il suffit de remarquer quepgcd(a,b).ppcm(a,b) = pgcd(|a|,|b|).ppcm(|a|,|b|) =|a||b|.?

Il est facile de calculer le pgcd de deux entiers grˆace `a l"algorithme d"Euclide. Le th´eor`eme 23 permet de calculer

le ppcm `a partir du pgcd. Exemple.Calculons ppcm(792,54). Appliquons tout d"abord l"algorithme d"Euclide :

792 = 54×14 + 36

54 = 36×1 + 18

36 = 18×2 + 0

Donc pgcd(792,54) = 18. On en d´eduit que ppcm(792,54) =792×54

18= 2376.

6 Th´eor`emes de B´ezout et de Gauss

a) Th´eor`eme de B´ezout

Th´eor`eme 24 (th´eor`eme de B´ezout

6). Soitaetbdeux entiers non nuls. Il existe des entiers

relatifsuetvtels queau+bv= pgcd(a,b). Preuve. SoitE={au+bv|u?Z,v?Z,au+bv >0}7.Eun sous-ensemble deN, et il est non vide car il

contient|a|=a×(±1) +b×0. Il a donc un plus petit ´el´ement, qu"on appelled. Commedest un ´el´ement de

E, il existe des entiersu0etv0tels qued=au0+bv0. Nous allons montrer qued= pgcd(a,b). r=a-qd=a-q(au0+bv0) =a(1-qu0)-bqv0, doncrest de la formeau+bvavecu= 1-qu0etv=-qv0. Sir >0, alorsr?E, doncr≥d(dest le plus

Conclusion :pgcd(a,b) =d=au0+bv0.?

Th´eor`eme 25 (th´eor`eme de B´ezout). Deux entiers non nulsaetbsont premiers entre eux si et

seulement s"il existe des entiersuetvtels queau+bv= 1. Preuve. Sipgcd(a,b) = 1, alors par le th´eor`eme 24, il existe des entiersuetvtels queau+bv= 1.

R´eciproquement, supposons qu"il existe des entiersuetvtels queau+bv= 1. Soitd= pgcd(a,b).ddivisea

Exemple.n2etn2+ 1 sont premiers entre eux car (n2+ 1)×1 +n2×(-1) = 1. Remarque.Siau+bv=c?= 1,cn"est pas n´ecessairement ´egal `a pgcd(a,b).

Exemple :a= 4,b= 10, 4a-b= 6 et pgcd(a,b) = 2.

6´Etienne B´ezout est un math´ematicien fran¸cais du XVIIIe si`ecle.

7

Notation d"un ensemble :{x|...}est l"ensemble desxtels que ... ("..." d´esigne les conditions v´erifi´ees parxou par les

param`etres d´efinissantx). On note ´egalement{x;...}ou{x:...}. 8

b) Comment trouver une relation de B´ezoutTrouver une relation de B´ezout pouraetb, c"est trouver des entiersuetvtels queau+bv= pgcd(a,b).

On applique l"algorithme d"Euclide `aaetb. On part de l"´egalit´e donnant le pgcd, et on"remonte»l"algorithme.

Exemple.a= 116,b= 10 116 = 11×10 + 6 (L1)a= 11b+r1

10 = 1×6 + 4 (L2)b=r1+r2

6 = 1×4 + 2 (L3)r1=r2+ pgcd(a,b)

4 = 2×2 + 0

Par la ligne (L3), pgcd(a,b) = 2, et on a l"´egalit´e : pgcd(a,b) =r1-r2.(?)

On exprimer2(reste avec le num´ero le plus ´elev´e) `a l"aide de (L2) :r2=b-r1, puis on remplace dans (?) :

pgcd(a,b) =r1-(b-r1) = 2r1-b.(??) On exprimer1`a l"aide de (L1) :r1=a-11b, puis on remplace dans (??) : pgcd(a,b) = 2(a-11b)-b= 2a-23b.

2a-23b= 2 est une relation de B´ezoutpoura= 116 etb= 10 (u= 2,v=-23).

Remarques.

•Une fois qu"on a calcul´euetv, il est tr`es facile de v´erifier queau+bv= pgcd(a,b).

•uetvne sont pas uniques. Exemple : 7a-81b= 2 est une autre relation de B´ezout poura= 116 etb= 10.

Variante de l"algorithme (plus adapt´e `a la programmation).

On applique l"algorithme d"Euclide `aaetb. On noteq1,...,qnles quotients etr1,...,rnles restes obtenus,

avecrnle dernier reste non nul. - On poseu0= 0,v0= 1,u1= 1,v1=-q1. - Pouri= 2,...,n, on d´efinituietvipar r´ecurrence :ui=ui-2-qiui-1etvi=vi-2-qivi-1. - On a la relation de B´ezout suivante :aun+bvn= pgcd(a,b).

Cette ´egalit´e repose sur le r´esultat suivant, dont la preuve est laiss´ee au lecteur :

Exercice.V´erifier queaui+bvi=ripour touti? {0,...,n}(pouri= 0, on prendr0=b). c) Th´eor`eme de Gaussquotesdbs_dbs35.pdfusesText_40

[PDF] role vitamine a

[PDF] role vitamine d bebe

[PDF] role de la vitamine k

[PDF] role vitamine e

[PDF] role vitamine b12

[PDF] role vitamine c

[PDF] vitamine d source

[PDF] recherche avancée google

[PDF] google livres

[PDF] conseil de classe terminale 3eme trimestre

[PDF] google + opérateur + recherche + pdf

[PDF] recherche pdf gratuit

[PDF] 3eme trimestre terminale inutile

[PDF] forme canonique alpha beta

[PDF] texte d'anglais