[PDF] Résumé du cours darithmétique

View - Download Résumé du cours darithmétique

Previous PDF

Next PDF

Maths discr`etes, 2012-2013Universit´e Paris-Sud

R´esum´e du cours d"arithm´etique

Les ensemblesNetZ

N=0,1,2,3,...est l"ensemble des entiers naturels (entiers positifs). 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 ce qui suit, entier est synonyme d"entier relatif.

1 Divisibilit´e dansZ

a) Diviseurs et multiples D´efinition.Soitaetbdeux entiers. On dit queadivisebs"il existe un entierktel queb=ka. On noteab. On dit ´egalement queaest undiviseurdebou quebest unmultipledea. Remarque.Siadiviseb, alorsadivise?b,?adivisebet?adivise?b. b) Propri´et´es Propri´et´es 1.Soita,b,cdes entiers relatifs. (1) Sib= 0 etadivisebalorsa b. En particulier,bZa un nombre fini de diviseurs. (2) Siadivisebetbdiviseaalorsa=boua=?b. (3) Siadivisebetbdivisecalorsadivisec. (4) Siadivisebetc, alors, pour tous entiersnetm,adivisenb+mc. La propri´et´e (4) se g´en´eralise sans difficult´e `a 3 termes ou plus.

2 Division euclidienne

Th´eor`eme 2 (th´eor`eme de la division euclidienne).SoitaZetbN. Il existe des entiersqetrtels quea=bq+ret 0r < b. De plus,qetrsont uniques. D´efinition.SoitaZetbN. Effectuer ladivision euclidiennedeaparb, c"est trouver les entiersqetrtels quea=bq+ravec 0r < b.qest lequotientetrest lerestede la division euclidienne deaparb. Propri´et´e 3.Le reste de la division euclidienne deaparbest nul si et seulement sibdivisea.

3 PGCD

a) D´efinition D´efinition.Soita,bZ. Le plus grand entier qui divise `a la foisaetbs"appelle leplus grand commun diviseuroupgcddeaetb. On le notepgcd(a,b).

Remarque.pgcd(a,b) = pgcd(a,b).

Propri´et´e 4.Soita,bZ. Siadivisebalors pgcd(a,b) =a. 1 b) Algorithme d"Euclide Th´eor`eme 5 (lemme d"Euclide).Soita,bZ. S"il existe des entiersketsavecs= 0 tels quea=bk+salors les diviseurs communs `aaetbsont exactement les diviseurs communs `a bets, et pgcd(a,b) = pgcd(b,s).

Algorithme d"Euclide.

SoitaZetbN. On cherched= pgcd(a,b). On noter0=b. On effectue des divisions euclidiennes successives tant que le reste est non nul. a=r0q1+r10< r1< r0 b=r1q2+r20< r2< r1 r

1=r2q3+r30< r3< r2.

r n3=rn2qn1+rn10< rn1< rn2 r n2=rn1qn+rn0< rn< rn1 r n1=rnqn+1+ 0rn+1= 0 Th´eor`eme 6.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=r0. Propri´et´e 7.Soita,bZ. Siddiviseaetbalorsddivise pgcd(a,b).

Remarque.On peut d´efinir le pgcd de 3 entiers ou plus. La propri´et´e 7 restevalable. Il n"y a

pas d"´equivalent de l"agorithme d"Euclide pour calculer le pgcd de 3 entiers. On peut utiliser la propri´et´e suivante : sid= pgcd(a,b) alors pgcd(a,b,c) = pgcd(d,c). 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. Propri´et´e 8.Soita,bZetd= pgcd(a,b). Alorsa detb dsont premiers entre eux.

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

a) Th´eor`eme de B´ezout Th´eor`eme 9 (th´eor`eme de B´ezout).Soitaetbdeux entiers non nuls.

1) Il existe des entiers relatifsuetvtels queau+bv= pgcd(a,b).

2) S"il existe des entiersuetvtels queau+bv= 1 alorsaetbsont premiers entre eux

b) Comment trouver une relation de B´ezout Trouver une relation de B´ezout pouraetb, c"est trouveruetvtels queau+bv= pgcd(a,b). On applique l"algorithme d"Euclide `aaetb. Gardons les notations de 3b). On a pgcd(a,b) =rn. On part de l"´egalit´e donnant le pgcd et on ´ecrit : pgcd(a,b) =rn2?rn1qn.() Puis on utilise la ligne pr´ec´edente dans l"algorithme d"Euclide pour exprimerrn1(reste avec l"indice le plus ´elev´e dans ()) :rn1=rn3?rn2qn1, on remplacern1dans (), on a : pgcd(a,b) =rn2?(rn3?rn2qn1)qn=?rn3qn+rn2(1 +qnqn1).()

On utilise la ligne pr´ec´edente dans l"algorithme d"Euclide pour exprimerrn2(reste avec l"indice

le plus ´elev´e dans ()), puis on remplacern2dans (). On continue ainsi jusqu"`a ´eliminer les restesrn1,rn2,...,r2,r1. On a alors le pgcd en fonction deaetb. 2

c) Th´eor`eme de GaussTh´eor`eme 10 (th´eor`eme de Gauss).Soita,b,cdes entiers non nuls. Siadivisebcet sia

est premier avecb, alorsadivisec. Th´eor`eme 11 (corollaire du th´eor`eme de Gauss).Soita1,a2,bdes entiers tels quea1et a

2sont premiers entre eux. Sia1eta2divisentb, alors le produita1a2diviseb.

Remarque.Le th´eor`eme 11 se g´en´eralise `a 3 entiers ou plus : sia1,a2,...,ansont deux `a deux

premiers entre eux et divisentb, alorsa1a2andiviseb. d) R´esoudre l"´equationax+by=c On veut trouver toutes les solutions enti`eres de l"´equation :ax+by=c(E) o`ua,b,csont des entiers donn´es aveca,bnon nuls, etx,ysont les inconnues. Th´eor`eme 12.L"´equation (E) admet des solutions si et seulement si pgcd(a,b) divisec.

M´ethode pour r´esoudre l"´equation (E).

Si pgcd(a,b) ne divise pasc, il n"y a pas de solution (th´eor`eme 12). Si pgcd(a,b) divisec, il y a des solutions par le th´eor`eme 12. Voici comment les trouver.

0) Simplifier l"´equation

Si pgcd(a,b) divisec, on divise l"´equation par pgcd(a,b), on trouve que (E) est ´equivalente `a

a x+by=c o`ua=a/pgcd(a,b),b=b/pgcd(a,b) etc=c/pgcd(a,b) (a,b,csont des entiers).

1) Solution particuli`ere

Les entiersaetbsont premiers entre eux (propri´et´e 8). Par le th´eor`eme de B´ezout, il existe

des entiersuetvtels queau+bv= 1. Alorsx0=cuety0=cvforment une solution particuli`ere de (E) carax0+by0=c(au+bv) =c.

2) Recherche de toutes les solutions

Exprimons les autres solutions en fonction de la solution particuli`ere (x0,y0). a x+by=cax+by=ax0+by0a(x?x0) +b(y?y0) = 0 SoitX=x?x0etY=y?y0. Pour r´esoudre (E), il est ´equivalent de r´esoudre a

X=?bY(E)

a etbsont premiers entre eux etbdiviseaX, doncbdiviseXpar le th´eor`eme de Gauss, autrement dit il existekZtel queX=kb. On a alorskab=?bY, et en simplifiant par b = 0 on trouveY=?ka. On vient de montrer que si (X,Y) est solution de (E") alors il existekZtel queX=kb,Y=?ka. On v´erifie facilement l"implication inverse : siX=kb etY=?ka, (X,Y) est bien une solution de (E") pour toutkZ. Les deux implications donnent une ´equivalence : (X,Y) solution de (E") kZ,X=kb,Y=?ka. Par cons´equent, l"ensemble des solutions de (E) est :

S={(x0+kb,y0-ka)|k?Z}aveca=a

pgcd(a,b)etb=bquotesdbs_dbs2.pdfusesText_3

[PDF] arithmétique dans z cours exo7

[PDF] arizona cardinals 87

[PDF] arizona charitable organization registration

[PDF] arizona charitable organizations

[PDF] arizona charitable tax credit list 2020

[PDF] arizona civics test flashcards

[PDF] arizona coin buy list

[PDF] arizona court of appeals forms

[PDF] arizona court of appeals rules

[PDF] arizona dashboard

[PDF] arizona foster charities

[PDF] arizona non profit organizations list

[PDF] arizona private school tax credit 2019

[PDF] arizona qcfo

[PDF] arizona qualifying contributions