[PDF] [PDF] arithmetique-capes-2014-2015pdf - Université de Rennes

3.Montrer queZ=fn2Z:gn=egest un sous-groupe deZ:

4.Montrer que siZ=f0galorsyest injective etest infini.

5.On supposeZ6=f0g:Montrer queZ+est non vide et que le cardinal deest égal au plus

Exercice 5.

SoitGun groupe fini et soitHun sous-groupe deG:

1.Montrer que sia2Galors l"application deGdansGqui àg2Gassocieagest une bijection.

Quelle est sa réciproque?

2.Montrer que la relationRdéfinie surGparaRbsi et seulement sia1b2Hest une relation

3.Montrer que sia2Gla classea

RdeapourResta

R=fah:h2Hg=aH:

4.Montrer que sia2Galorsa

RetHont même cardinal.

5.Montrer que l"ordre deH(i.e. son cardinal) divise l"ordre deG:

Exercice 6.

Soientaetbdeux entiers relatifs.

1.Montrer que le sous-ensemble

2.En déduire qu"il existec2Ntel queaZ+bZ=cZ:

Le nombrecainsi obtenu est notépgcd(a;b):

3.Montrer queaetbsont des multiples dec:

4.Soitd2Z:Montrer que siddiviseaetbalorsddivisec:

5.Montrer que 1 et1 sont les seuls diviseurs communs àaetb(aetbsont premiers entre eux) si et

On supposeanon nul.

6.Montrer quecest non nul et quecdiviseaetb:

7.Montrer quecest bien le plus grand diviseur commun àaetbau sens de la relation d"ordre usuel.

Exercice 7.

Soientaetbdeux entiers relatifs.

1.Montrer que le sous-ensembleaZ\bZest un idéal deZ:

2.En déduire qu"il existed2Ntel queaZ\bZ=dZet vérifier que(ka)Z\(kb)Z= (kd)Zsik2N:

Le nombredainsi obtenu est notéppcm(a;b):

3.Montrer quedest un multiple deaetbet que tout multiple deaetbest un multiple ded:

4.Montrer que sia=ca0;b=cb0avecc=pgcd(a;b)alorsd=ppcm(a;b) =ca0b0(utiliser Bezout

5.Montrer quedest bien le plus petit multiple commun (naturel) àaetbau sens de l"ordre usuel.

Exercice 8.

1.Montrer que sirn16=0 alorsrn

2.Montrer que sin>palorsrn=0:

3.Montrer qu"il existeNtel querN6=0 maisrN+1=0:

4.Montrer quepgcd(p;q) =rN:

Exercice 9.

Soita;b2Z:Donner un algorithme pour trouverpgcd(a;b)etu;v2Ztels queua+vb=pgcd(a;b):

Exercice 10.

écriture réduite des rationnels

Soitrun rationnel strictement positif :r=ab

avec(a;b)2NN:

1.Soit(a0;b0)2NN:Montrer quer=a0b

0si et seulement siab0a0b=0:

2.Montrer qu"il existe(A;B)2NNunique tel quepgcd(A;B) =1 etr=AB

(écriture réduite).

3.Soitrd"écriture réduiter=AB

etsd"écriture réduites=CD :On poseB=B0PetD=D0Pavec P=pgcd(B;D):Montrer que l"écriture réduite der+sest de la former+s=EF avecF=B0D0Q:

4.Soientp1;:::;pkdes nombres premiers tous différents. Montrer que1p

1+:::+1p

kn"est pas entier. 3

Exercice 11.

Soitn2N:Soit la relationndéfinie surZparanbsi et seulement sindiviseab:

1.Montrer quenest une relation d"équivalence.

Lorsqueanbon dit queaest congru àbmodulonqu"on peut écrireab(n)ouabmodulon:

2.Montrer que sia2Zalors le restea0de la division euclidienne deaparnvérifieana0:

3.Montrer que la relationnpossède exactementnclasses d"équivalence, chacune d"elles possèdant

un unique représentant parmi les entiers compris entre 0 etn1: On noteZ=nZl"ensemble des classes déquivalence denet sia2Zon notea nla classe deapour n(appelée aussi classe deamodulon).

4.Montrer que sianbetk2Zalorsa+knb+ketkankb:

5.Montrer que sianb;cndetk2Zalorsa+cn=b+dnetkan=kbn:

6.Montrer queZ=nZpeut être muni de deux lois+netntelles que

-(Z=nZ;+n;n)est un anneau commutatif, - l"application deZdansZ=nZest un morphisme d"anneau.

Exercice 12.

les générateurs deZ=nZ

Soitn2Net soitm2Z:Montrer quem

nest un générateur deZ=nZ(i.e.=Z=nZou encorem nest d"ordren) si et seulement sipgcd(n;m) =1:

Exercice 13.

les sous-groupes deZ=nZ

Soitn2N:

1.Soitd2Ntel queddivisenet soitm2Nle quotient denpard:Montrer que la classem

nengendre un sous-groupeGddeZ=nZisomorphe au groupeZ=dZ:

2.Soitm2Z:Montrer que n>=oùt=pgcd(n;m): SoitGun sous-groupe deZ=nZnon réduit àf0get soitm2Nle plus petit entier strictement positif dont la classe modulonappartient àG:

3.Soitb2Ntel queb

n2Get soitqetrle quotient et le reste de la division euclidienne debparm:

Montrer quer

n2G:

4.Montrer quemdivisen:

5.Montrer queG= n>est isomorphe àZ=dZoùdest le quotient denparm: On noteDl"ensemble des diviseurs den:Pour toutddansDon noteOdl"ensemble des éléments d"ordreddeZ=nZet on notef(d)le nombre d"éléments d"ordreddeZ=dZ(indicatrice d"Euler).

6.Montrer que sid;d02Detd6=d0alorsOdetOd0sont disjoints.

7.Montrer que

Z=nZ=[

d2DO d:

8.Montrer que

n=å d2Df(d):

Exercice 14.

théorème des restes chinois

Soientn;m2N:

1.Soienta;b2Z:Montrer que siamnbalorsambetanb:

2.Montrer que l"applicationq= (q1;q2)deZ=mnZdansZ=mZZ=nZdéfinie par

q(a mn) = (a m;a n)sia2Z est un morphisme de groupe.

3.On suppose quepgcd(m;n)6=1:Montrer qu"il existea2Ztel queam0 etan0 maisa6mn0

et en déduire queqn"est ni injectif ni surjectif. 4 On suppose quepgcd(m;n) =1 et on considèreu;v2Ztels queum+vn=1:

4.Soienta;b2Z:Montrer que siambetanbalorsamnbet en déduire queqest un isomor-

phisme de groupe.

5.Soienta;b2Z:

5.a.Montrer quec=avn+bumvérifiecmaetcnb:

5.b.Montrer qued2Zvérifiedmaetdnbsi et seulement sidc0mn:

6.Montrer que sigest un générateur deZ=mnZalorsq1(g)etq2(g)sont des générateurs deZ=mZ

etZ=nZ:

7.Soit(a;b)2Z=mZZ=nZavecagénérateur deZ=mZetbgénérateur deZ=nZ:Montrer que

l"uniquec2Z=mnZtel queq(c) = (a;b)est un générateur deZ=mnZ:

8.Montrer que le nombref(mn)de générateurs deZ=mnZest égal au produitf(m)f(n)du nombre

de générateurs deZ=mZpar le nombre de générateurs deZ=nZ:

9.Montrer que sim1;:::;mksont deux à deux premiers entre eux alors :

-Z=m1:::mkZest isomorphe àZ=m1Z:::Z=mkZ -f(m1:::mk) =f(m1):::f(mk):

10.On suppose quem1;:::;mksont deux à deux premiers entre eux. Sii=1;::;kon poseni=m1:::mkm

i.

10.a.Montrer que sii=1;::;kil existeui;vi2Ztels queuimi+vini=1:

10.b.Montrer que sia1;:::;ak2Zalorsa=v1n1a1+:::+vknkakvérifieamiaipour touti=1;:::;k:

Exercice 15.

l"indicatrice d"Euler

Soitnun entier supérieur ou égal à 2:On notef(n)le nombre de générateurs deZ=nZc"est à dire le

nombre d"entiers naturels premiers avecnet plus petits quen:

1.Montrer que sinest premier (i.e. sans diviseurs autres que 1 et lui même dansN) alorsf(n)=n1:

2.On supposen=pravecppremier etr2Nsupérieur ou égal à 2:

2.a.Soitmun entier compris entre 1 etn:Montrer que simetpne sont pas premier entre eux alorsp

divisem:

2.b.Montrer qu"il y apr1entiersmnon premiers avecnet compris entre 1 etn:

2.c.En déduire

f(n) =f(pr) = (prpr1) =n 11p

3.On suppose quen=pr11:::prk1:Montrer que

f(n) =n 11p 1 11p k

Exercice 16.

Soitpun nombre premier, c"est à dire un entier relatif qui admet exactement quatre diviseurs dansZ:

1.Soita2Z=pZ:Montrer qu"il existeb2Ztel queabp1:

2.Montrer que(Z=pZ;+p;p)est un corps.

3.Soitn2N:Montrer que si(Z=nZ;+n;n)est un corps alorsnest premier.

Exercice 17.

On munit le groupe(Z=2ZZ=2Z;+)d"une deuxième loi notéeet définie de la façon suivante : (0;0) (1;1) (1;0) (0;1)(0;0)(0;0) (0;0) (0;0) (0;0) (1;1)(0;0) (1;1) (1;0) (0;1) (1;0)(0;0) (1;0) (0;1) (1;1) (0;1)(0;0) (0;1) (1;1) (1;0)

1.La loiadmet-elle un neutre et un élément absorbant?

5

2.Vérifier que tout élément autre que(0;0)est inversible.

3.Comment déduire de la table queest commutative?

4.Vérifier que la loiest associative.

5.Comment déduire de la table queest distributive par rapport à+?

6.Que conclure sur(Z=2ZZ=2Z;+;)?

Exercice 18.

Soitn2N:

1.Montrer que sip2Npremier divise 1+n! alorsp>n:

2.Montrer qu"il existe une infinité de nombres premiers.

On supposen2:

3.Montrer que sik2Net 2knalorskdivisen!+k:

4.Montrer que pour touta;b>0 il existep;qpremiers tels quea entier compris entrep+1 etq1 n"est pas premier.

Exercice 19.

SoitAl"ensemble des entiers naturels premiers et congrus à 3 modulo 4.

1.Montrer queAest non vide.

2.Soientp1;:::;pk2A:On poseP=4p1:::pk1:

2.a.Montrer que sii=1;:::;kalorspgcd(P;pi) =1:

2.b.Montrer que l"ensembleEdes entiers naturels congrus à 1 modulo 4 est stable par multiplication :

sim;n2Ealorsmn2E:

2.c.Montrer qu"il existep2Anfp1;:::;pkg:

2.d.Montrer qu"il existe une infinité d"entiers naturels premiers et congrus à 3 modulo 4.

Exercice 20.

Soitn2N:Donner un algorithme de calcul des nombres premiers inférieurs ou égaux àn:

Exercice 21.

lemme de Gauss, par Bezout

Soienta;b;c2N:On suppose quepgcd(a;c) =1:

1.Montrer qu"il existeu;v2Ztels queua+vc=1:

2.En déduire qu"il existeU;V2Ztels queb=Uab+Vc:

3.Montrer que sicdiviseabetpgcd(a;c) =1 alorscdiviseb(lemme de Gauss).

Exercice 22.

lemme d"Euclide, preuve de Gauss Soienta;b;p2Navecppremier divisantab:L"objet de l"exercice est de montrer quepdiviseaoub sans avoir recours au lemme de Gauss. On raisonne par l"absurde en montrant que l"hypothèsepne divise nianibmène à une contradiction.

On supposepgcd(p;a) =pgcd(p;b) =1:

1.Vérifier queE=fn2N:pgcd(p;n) =1 etpdivisenbgest non vide et possède un plus petit

élément notéA:

quotesdbs_dbs23.pdfusesText_29