[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=b pgcd(a,b).

Remarque.Ne pas apprendre par coeur ce r´esultat, mais refaire la m´ethode pr´ec´ed´ente.

3

5 Nombres premiers

a) Reconnaˆıtre un nombre premier D´efinition.Un entiern2 estpremiersi ses seuls diviseurs positifs sont 1 etn. Propri´et´e 13.Si l"entiern2 n"est divisible par aucun nombre premierp n, alorsnest un nombre premier. Th´eor`eme 14 (th´eor`eme d"Euclide).Il existe une infinit´e de nombres premiers. b) D´ecomposition en produit de facteurs premiers Th´eor`eme 15 (d´ecomposition en facteurs premiers).Tout entiern2 peut s"´ecrire de fa¸con unique n=p1p2pr, o`urNetp1,p2,...,prsont des nombres premiers avecp1p2 pr.

D´efinition.SoitnNetpun nombre premier.

Sipdivisen, on dit quepest unfacteur premierden

Le plus grand entierktel quepkdivisens"appellel"exposant depdansn.

Dans le th´eor`eme 15, on peut regrouper les premiers identiques,on obtient l"´enonc´e suivant :

Th´eor`eme 15" (d´ecomposition en facteurs premiers)Tout entiern2 peut s"´ecrire de fa¸con unique n=pα11pα22pαss o`up1,...,pssont des nombres premiers distincts avecp1< p2<< ps, etα1,...,αsN. Remarque.Dans le th´eor`eme 15", l"exposant depidansnestαi. Si un nombre premierp n"apparaˆıt pas dans la d´ecomposition den, son exposant est 0. c) Application `a la divisibilit´e Th´eor`eme 16 (application de la d´ecomposition en facteurs premiers `a la divisibi- lit´e).Soitaetbdes entiers strictement positifs. Pour tout nombre premierp, notonsα(p) l"exposant depdansaetβ(p) l"exposant depdansb. Alorsadivisebsi et seulement si pour tout nombre premierpon a :α(p)β(p). Th´eor`eme 17 (application de la d´ecomposition en facteurs premiers au pgcd).Soit a,bNetpun nombre premier. Soitα(p) l"exposant depdansaetβ(p) l"exposant dep dansb. Alors l"exposant depdans pgcd(a,b) est min(α(p),β(p)). Remarque.Le th´eor`eme 17 reste valable pour calculer le pgcd de 3 entiers ou plus.

6 PPCM

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).

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

Propri´et´e 18.Soita,bZ. Sicest un multiple deaetb, alorscest un multiple de ppcm(a,b). 4 Th´eor`eme 19 (application de la d´ecomposition en facteurs premiers au ppcm).Soit a,bNetpun nombre premier. Soitα(p) l"exposant depdansaetβ(p) l"exposant dep dansb. Alors l"exposant depdans ppcm(a,b) est max(α(p),β(p)). Th´eor`eme 20 (relation entre pgcd et ppcm).Sia,bZ, pgcd(a,b).ppcm(a,b) =ab.

Remarque.On peut d´efinir le ppcdm de 3 entiers ou plus. La propri´et´e 18 et leth´eor`eme

19 restent valables, mais le th´eor`eme 20 ne se g´en´eralise pas `a3 entiers. On peut utiliser la

propri´et´e suivante : si ppcm(a,b) =malors ppcm(a,b,c) = ppcm(m,c).

7 Congruences

Dans la suite, on consid`ere un entiern2.

a) D´efinition et propri´et´es D´efinition.Soita,bZ. On dit queaest congru `abmodulonsia?best un multiple den. On dit aussi queaetbsont congrus modulon. On noteab(n) ouabmodn.

Remarques.

La relation de congruence est sym´etrique :ab(n)ba(n). ab(n) ?a ?b(n). ab(n) kZ,a=b+kn a0 (n)ndivisea. Propri´et´e 21.SoitaZ. Il existe un unique entierrtel quear(n) et 0rn?1. rest le reste de la division euclidienne deaparn.

Propri´et´e 22.Siab(n) etbc(n) alorsac(n).

b) Compatibilit´e avec les op´erations Propri´et´es 23.Soita,b,c,dZtels queab(n) etcd(n). Alors a+cb+d(n) etacbd(n). pour tout entierk1,akbk(n). 8

´Equations de congruence

a) Quand simplifierab≡ac(n)? Propri´et´e 24.Soita,b,cZ. S"il existeuZtel queua1 (n) alorsabac(n) implique bc(n). Th´eor`eme 25.SoitaZ. Il existeuZtel queau1 (n) si et seulement si pgcd(a,n) = 1. M´ethode pour trouverucomme dans le th´eor`eme :siau+nv= 1 est une relation de

B´ezout entreaetn, alorsau1(n).

b) R´esoudre l"´equationax≡c(n) On veut trouver toutes les solutions enti`eres de l"´equation :axc(n) (E) o`uaetcsont des entiers donn´es avecanon nul, et o`uxZest l"inconnue.

Cas o`uaetnsont premiers entre eux.

5 Propri´et´e 26.Soitaetndes entiers premiers entre eux (n2) etuZtel queau1 (n). L"´equationaxc(n) est ´equivalente `axuc(n).

Cas o`uaetnne sont pas premiers entre eux.

xsolution de (E) kZ,ax=c+kn kZ, (x,k) solution deax?kn=c. La derni`ere ´equation est de la formeax+by=c(avecy=ketb=n), qui a ´et´e vue en 4.d). Si pgcd(a,n) ne divise pasc, alorsax?kn=cn"a pas de solution. Si pgcd(a,n) divisec, on posea=a/pgcd(a,n),n=n/pgcd(a,n) etc=c/pgcd(a,n). On a donc xsolution de (E) kZ,ax?nk=caxc(n). On est ramen´e au cas pr´ec´edent puisqueaetnsont premiers entre eux. c) Syst`emes de congruences Th´eor`eme 27 (th´eor`eme des restes chinois).Sin1,n2,...,nksont des entiers positifs 2 `a

2 premiers entre eux, alors, pour tousa1,...,akZ, le syst`eme

xa1(n1) xa2(n2). xak(nk) a des solutions et, six0est une solution particuli`ere, alors l"ensemble des solutions s"´ecrit xZxx0(n1n2...nk). M´ethode pour r´esoudre un syst`eme `a deux ´equations(S)xa(n) xb(m) xsolution de (S) k,kZ,x=a+kn=b+km x=a+knavec (k,k) solution dekn?km=b?a On est ramen´e `a r´esoudre une ´equation de la formeAX+BY=C, avecX=k,Y=k. On peut se contenter de chercher une solution particuli`ere (k0,k0), on en d´eduit une solution particuli`ere de (S), puis on applique le th´eor`eme 27 pour avoir toutes les solutions de (S). M´ethode pour r´esoudre un syst`eme de congruence `a 3 ´equations. (S3)xa(n) xb(m) xc(p)avecn,m,pdes entiers 2 `a 2 premiers entre eux.

1) On r´esout le syst`eme partiel

xa(n) xb(m) Selon le th´eor`eme 27, on trouve les solutions sous la formexx0(nm) pour un certainx0Z.

2) Le syst`eme (S3) est alors´equivalent au syst`eme de congruence `a 2´equationsxx0(nm)

xc(p) On r´esout ce syst`eme et on obtient les solutions de (S3).

9 Petit th´eor`eme de Fermat

Th´eor`eme 28 (th´eor`eme de Fermat).Soitpun nombre premier etxun entier. Alors : xpx(p), sipne divise pasx, alorsxp11 (p). 6quotesdbs_dbs14.pdfusesText_20

[PDF] generalized hough transform python

[PDF] generally

[PDF] generate code for aiims 2019

[PDF] generation of alternating current

[PDF] generation of code for final registration aiims

[PDF] generation of computer 1st to 5th

[PDF] generation of computer notes

[PDF] generation of computer notes pdf

[PDF] generation of computer ppt

[PDF] generation of computer wikipedia

[PDF] generation of programming languages

[PDF] generations of programming languages pdf

[PDF] generic abn form pdf

[PDF] generic type java

[PDF] generics collection