[PDF] M2 EFM

View - Download M2 EFM

Previous PDF

Next PDF

M2 EFM

TD MATHÉMATIQUES APPLIQUÉES : ARITHMÉTIQUE

CHRISTOPHE RITZENTHALER

1.Euclide, relation de Bézout, pgcd

Exercice 1.[DKM94, p.14] Montrer que6jn3npour tout entiernpositif. Exercice 2.[DKM94, p.15] Pour chacune des affirmations suivantes, dire si elle est vraie ou fausse en donnant soit une démonstration, soit un contre-exemple. (1) Sipgcd(a;b) = pgcd(a;c)alorsppcm(a;b) = ppcm(a;c). (2) Sipgcd(a;b) = pgcd(a;c)alorspgcd(a2;b2) = pgcd(a2;c2). (3) Sianjbnoùn1alorsajb. (4) Siamjbnoù1m < nalorsajb. Exercice 3.[DKM94, p.14] Montrer que le cube d"un entier positif peut toujours s"écrire comme la différence de deux carrés. Exercice 4.(Version plus générale dans [Dem97, p34]). Soientm;n2Z. Montrer quepgcd(Xm1;Xn1) =Xpgcd(m;n)1.

Exercice 5.Etude de1[n](lire [Dem97, pp9-14]).

Soitb2, on définit l"entier naturel1[n]:= (111|{z} nfois) b,i.e. 1 [n]=bn1b1:

1) Montrer que simdivisenalors1[m]divise1[n].

2) En utilisant l"exercice 4 montrer quemetnsont premiers entre eux si et seulement

s"il en est de même de1[m]et1[n].

Exercice 6.Théorème de Lucas[Dem97, p37].

La suite de Fibonacci est définie par la relation de récurrenceFn+2=Fn+1+Fn et les conditions initialesF1= 1;F0= 0. on veut montrer le théorème de Lucas : pgcd(Fn;Fm) =Fpgcd(n;m).

1) Le résultat qui suit est un résultat annexe. Montrer que pour toutn0,Fn=

1p5 (n+ (1)n+1n), oùest la racine positive de l"équationX2=X+ 1.est appelé lenombre d"oret vérifie= 1 +1.

2) Maintenant on s"intéresse aux résultats préliminaires au théorème de Lucas. Montrer

que pour toutn1on a F n+1Fn1F2n= (1)n:

En déduire queFnetFn+1sont premiers entre eux.

3) Montrer pourm1etn0la relation

F n+m=FmFn+1+Fm1Fn: [Faire une récurrence surmet une surn]. 1

4) Soitd2N, montrer la propriété suivante :

ddiviseFmetFn()ddiviseFnetFn+m:()

5) On va montrer que toute suite d"entiers(Fn)satisfaisant()avecF0= 0vérifie le

théorème de Lucas. a) Montrer que pour toutk1on a ddiviseFmetFn()ddiviseFnetFn+km: b) On supposem > n. Soitrle reste de la division euclidienne demparn. Montrer quepgcd(Fm;Fn) = pgcd(Fn;Fr). c) Conclure en utilisant l"algorithme d"Euclide.

2.Congruence

Exercice 7.[DKM94, p.54] Donner un exemple d"un système de résidus complet modulo

17qui est composé entièrement de multiples de3.

Exercice 8.[DKM94, p.54] Écrire une seule congruence qui est équivalente à la paire de congruence x1 (mod 4); x2 (mod 3): Exercice 9.[DKM94, p.54] Montrer que la différence de deux cubes consécutifs n"est jamais divisible par5. Exercice 10.[DKM94, p.55] Résoudre les congruences suivantes (1)2x1 (mod 7) (2)12x9 (mod 6) (3)5x 1 (mod 8) Exercice 11.SoitGun groupe etg2G. Montrer quegn= 1ssinest un multiple de l"ordre deg. Montrer que sign= 1et que pour toutppremier divisantn,gn=p6= 1alors nest l"ordre deg. Exercice 12.Montrer que sinest le produit deh1nombre premiers impairs distincts alors le nombre de solutions dex21 (modn)est2h. Exercice 13.Sianam(modp)pourppremier etaun élément primitif, que peut-on dire des entiersnetm? Exercice 14.Petit théorème de Fermat[DKM94, p55]. Soientp;qdeux nombres premiers distincts. Montrer que p q1+qp11 (modpq):

3.Nombres premiers

Exercice 15.[DKM94, p.33] Soitpun nombre premier. Pour chacune des affirmations suivantes, dire si elle est vraie ou fausse en donnant soit une démonstration, soit un contre-exemple. (1) Sipjaetpja2+b2alorspjb. (2) Sipja9alorspja. (3) Sipj(a2+b2)etpj(b2+c2)alorspj(a2c2). (4) Sipj(a2+b2)etpj(b2+c2)alorspj(a2+c2). 2 Exercice 16(Critère de primalité de Lehmer).Soitn3impair. Alorsnest premier si et seulement si il existea2[1;:::;n2]tel quean11 (modn)eta(n1)=q61 (modn)pour tout diviseur premier den1.

Exercice 17.Nombres de Fermat

Pourn0on définitFern:= 22n+ 1lenèmenombre de Fermat.

1) Montrer queFern=

n1Y i=0Fer i! + 2, en déduire le théorème de Goldbach :" Deux nombres de Fermat distincts sont premiers entre eux".

2) Soienta2;n1. Montrer que sian+ 1est premier alorsaest pair etnest une

puissance de 2. Exercice 18.Critère de Pépin (Test de primalité des nombres de Fermat)[Dem97, p80,p122. Attention, erreur dans l"énoncé du livre].

Soitn1. Montrer que

Fer nest premier()322n1 1 (mod Fern): [Rappel de la loi de réciprocité quadratique : Soientp6=qpremiers impairs,pq (1)(p1)(q1)4 qp

Tester la primalité deFernpourn= 1;:::;10.

3

CORRECTION

4.Divisibilité

Correction exercice 1Comme6 = 23et que2et3sont premiers entre eux, il suffit de montrer que2et3divisen3n= (n1)n(n+ 1). Comme c"est le produit de 3 entiers consécutifs, l"un d"eux est toujours pair et l"un deux est toujours un multiple de

3d"où le résultat.

Correction exercice 2

(1) C"est faux puisquepgcd(2;3) = pgcd(4;5) = 1maisppcm(2;3) = 66= ppcm(4;5) = 20. (2) C"est vrai : il suffit de montrer quepgcd(a;b)2= pgcd(a2;b2). En divisantaetb par leur pgcd, il suffit de montrer que siaetbsont premiers entre eux alorsa2et b

2sont premiers entre eux. Raisonnons par l"absurde et soitpun premier divisant

pgcd(a2;b2). On a donc quepja2etpjb2. Commepest premier, cela implique que pjaet quepjbdoncaetbne sont pas premiers entre eux. (3) C"est vrai. Soitd= pgcd(a;b). On aa=dAetb=dBoùpgcd(A;B) = 1. Ainsi on a (comme précédemment)pgcd(An;Bn) = 1et puisqueanjbnon obtient A ndnjBndnsoitAnjBn. Puisqu"ils sont premiers entre eux, ceci n"est possible que siA= 1et doncd=a. Ceci implique queb=dB=aBet doncajb. (4) C"est faux en prenant par exemplea= 4;b= 2etm= 1etn= 2. Correction exercice 3On souhaite montrer que pour toutnentier, il existe des entiers x;ytels quen3=x2y2. Pour cela il suffit de trouverx;ytels quex+y=n2et xy=nc"est-à-direx= (n+n2)=2ety= (n2n)=2ce qui est possible carn+n2et n

2nsont tous les deux pairs.

Correction exercice 4.

Supposonsmn, écrivonsm=qn+rla division euclidienne demparn. On commence par montrer quepgcd(Xm1;Xn1) = pgcd(Xn1;Xr1). On a X m1 =Xqn+r=Xr(Xqn1) +Xr1; =Xr(Xn1) q1X i=0X ni! +Xr1: Notonsd:= pgcd(Xm1;Xn1);d0:= pgcd(Xn1;Xr1).ddiviseXm1et X n1donc, d"après l"équation ci-dessus,ddiviseXr1. A fortioriddivised0. Le même raisonnement montre qued0divised. Ainsi,d=d0. Finalement, soitr0:= pgcd(m;n), en itérant ce raisonnement et en appliquant l"algorithme d"Euclide, on a pgcd(Xm1;Xn1) = pgcd(Xn1;Xr1); = pgcd(Xd1;X01); =Xd1; =Xpgcd(m;n)1:

Correction exercice 5.

4

1) Soientn=kmpourk1. On a

b n1 = (bm1)k1X i=0b mi:

D"où, en divisant parb1,1[m]divise1[n].

2) On a

pgcd

1[m];1[n]= pgcdbm1b1;bn1b1

1b1pgcd(bm1;bn1);

bpgcd(m;n)1b1d"après l"exercice 4; = 1 [pgcd(m;n)]: D"où l"équivalencem,npremiers entre eux ssi1[m]et1[n]le sont.

Correction exercice 6.

1) Preuve par récurrence :

Pourn= 0,00= 11 = 0 =F0, et pourn= 1,1p5

(1) = 1 =F1. Soitn2N, supposons la formule vérifiée pourFn+1etFn, alors F n+2=Fn+1+Fn; 1p5 n+1+ (1)n+2(n+1)+n+ (1)n+1n; 1p5 n+1+n+ (1)n+3((n+1)+n; 1p5 0 B

BB@n+1

1 +1 |{z} =+(1)n+3(n+1) 1 +1 1 |{z} =11 C CCA; 1p5 n+2+ (1)n+3(n+2):

2) Preuve par récurrence :

Pourn= 1, on aF2F0F21= 101 =1:

SupposonsFnFn2F2n1= (1)n1. Alors

F n+1Fn1F2n= (Fn+Fn1)Fn1F2n; =FnFn1+F2n1F2n; =Fn(Fn1Fn) +F2n1; =FnFn2+F2n1; = (1)n: Posonsun:= (1)nFn1;vn:= (1)nFn, on aFn+1un+Fnvn= 1. Donc par BézoutFn etFn+1sont premiers entre eux. 5

3)Etape 1.

Fixonsm1. Pourn= 0on aFm=FmF1|{z}

=1+Fm1F0|{z} =0, et pourn= 1on a F m+1=FmF2|{z} =1+Fm1F1|{z} =1. SoitN1, supposons que pourn=N1;Non aFn+m=FmFn+1+Fm1Fn, avecm fixé. Alors F

N+1+m=F(N+m)+1=FN+m+FN+m1|{z}

=F(N1)+m; =FmFN+1+Fm1FN|{z}

H.R.+FmFN+Fm1FN1|{z}

H.R.; =Fm(FN+1+FN) +Fm1(FN+FN1); =FmFN+2+Fm1FN+1:

Etape 2.

Fixonsn0. Pourm= 1on aFn+1=F1|{z}

=1F m+F0|{z} =0F n, et pourm= 2on a F n+2=F2|{z} =1Fn+1+F1|{z} =1Fn. SoitM2, supposons que pourm=M1;Mon aFn+m=FmFn+1+Fm1Fnpourm fixé. Alors F n+M+1=Fn+M+Fn+(M1); =FMFn+1+FM1Fn+FM1Fn+1+FM2Fn(H.R.); = (FM+FM1)Fn+1+ (FM1+FM2)Fn; =FM+1Fn+1+FMFn:

4)). On a montré

F n+m=Fm|{z} divisible pardFn+1+Fm1Fn|{z} divisible pard:

DoncddiviseFn+m.

(. On aFmFn+1=Fn+mFm1FndoncFmFn+1est divisible pard. Or on a montré en

2) queFnetFn+1sont premiers entre eux, doncd6 jFn+1, ainsidjFm.

5a) On montre l"équivalence par récurrence surk. Le cask= 1est démontré au 4).

On suppose l"équivalence vraie pourket montrons-la pourk+ 1: ). On supposedjFmetdjFn, alors par hypothèse de récurrenceddivise aussiFm+kn. Donc par()ddiviseFm+kn+n=Fm+(k+1)n, d"où l"implication cherchée. (. On supposeddiviseFnetFm+(k+1)n=Fm+kn+n, alors par()ddiviseFnetFm+kn. DoncddiviseFmetFnpar hypothèse de récurrence.

5b) On écritm=qn+rla division euclidienne demparn. On aq1carm > n.

Notonsd:= pgcd(Fm;Fn)etd0:= pgcd(Fn;Fr). On a

d

0jFn;d0jFr)|{z}par()d

0jFqn+r;d0jFn)d0jFm;d0jFn)d0jd:

6

D"oùd=d0.

5c) Notonsd:= pgcd(Fm;Fn). Appliquant l"algorithme d"Euclide au 5b), on a

pgcd(Fm;Fn) = pgcd(Fpgcd(m;n);F0) = pgcd(Fpgcd(m;n);0) =Fpgcd(m;n):

5.Congruences

Correction exercice 7C"est possible puisque3est premier à17. En prenant les mul- tiples successifs on obtient : Correction exercice 8L"inverse de3modulo4est3et l"inverse de4mod3est1. On obtient donc x(12=4)31 + (12=3)12 = 5 (mod 12): Correction exercice 9On a(x+ 1)3x3= 3x2+ 3x+ 1 =a(x). En calculanta(x) (mod 5)pourx= 0;:::;4, on constate qu"on n"obtient jamais0. D"où le résultat.

Correction exercice 10

(1) L"inverse de2modulo7est4doncx4 (mod 7). (2)120 (mod 6)mais9pas donc il n"y a pas de solution. (3) L"inverse de5modulo8est5doncx3 (mod 8). Correction exercice 11Supposons quenne soit pas un multiple dedet soit alors n=dq+ravec0< r < dle reste de la division euclidienne denpard. On a g n= 1 =gdq+r=gdqgr=gr donc il existerait un0< r < dtel quegr= 1: absurde par définition de l"ordre d"un

élément.

Puisquegn= 1on an=ds. Supposons quenn"est pas l"ordre degalors on as >1, en particulier il existe un premierpdivisants(et donc aussin). Calculons g n=p=gds=p=gds=p= 1 d"où le résultat.

Correction exercice 12Écrivonsn=Qh

i=1pioù lespisont des premiers impairs distincts. L"équationx21 (modn)est donc équivalente au système 8>< :xquotesdbs_dbs41.pdfusesText_41

[PDF] si 2 n 1 premier alors n premier

[PDF] nombre de mersenne pdf

[PDF] nombre de mersenne démonstration

[PDF] a^n-1 premier alors a=2

[PDF] le tourisme des français en 2016

[PDF] français vacances statistiques 2016

[PDF] tourisme français ? l'étranger

[PDF] ou partent les français en vacances

[PDF] pourcentage de français qui partent en vacances ? l'étranger

[PDF] nombre marche tour eiffel 2 etage

[PDF] hauteur tour eiffel 1er etage

[PDF] 1 etage combien de marches

[PDF] combien de marches pour monter au deuxième étage de la tour eiffel

[PDF] fonction logarithme bac pro exercice

[PDF] nombre de molécules dans 1 litre d'air