[PDF] M2 EFM Montrer que si an + 1

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>< :x

21 (modp1)

x

21 (modph)

Chacune de ces équations a au plus deux solutions carZ=piZest un corps. De plus comme lespisont impairs, chaque équation a exactement deux solutions distinctes1et1. La résolution des systèmesxi=1 (modpi)donne donc2hsolutions distinctes modulon. 7 Correction exercice 13Siaest un élément primitif, il est en particulier non nul donc inversible modulopet donc on aanm1 (modp). On en conclut quenmest divisible par l"ordre deaqui est(p) =p1doncmn(modp1).

Correction exercice 14.

petqétant premiers entre eux on a, d"après le petit théorème de Fermat, quepq1+qp1 est solution du systèmex1 (modp); x1 (modq): Orx0= 1en est une autre, et par le théorème des restes chinois (version pratique) on a que deux solutions sont congrues modulopq. Ainsipq1+qp11 (modpq).

Correction exercice 15

(1) On a quepjb2doncpjb. (2) C"est vrai, en écrivant par exemple la factorisation dea. (3) On peut raisonner modulop, et donc0(a2+b2)(b2+c2)a2c2modp. (4) Non :5j12+ 22et5j12+ 32mais5ne divise pas22+ 32. Correction exercice 16Sinest premier, soitaun élément primitif. Son ordre estn1 donc on a la propriété souhaitée. Inversementaest un élément d"ordren1donc#(Z=nZ)n1et donc tous les élements non nuls sont inversibles :nest premier.

Correction exercice 17.

1) On montre la formule par récurrence :

Pourn= 0on a bienFer0= 2.

Supposons que pourn0on aFern=n1Y

i=0Fer i+2. Alors n Y i=0Fer i+2 = Fernn1Y i=0Fer i+2; = Fer n(Fern2) + 2; = Fer

2n2Fern+2;

=22n+ 12222n+ 1+ 2; = 2

2n+1+222n+ 1222n 62 +62;

= Fer n+1: Ainsi, tout diviseur commun à deux nombres de Fermat distincts divise 2. Or ceux-ci sont impairs, d"où la conclusion. Remarquons qu"on a redémontré l"existence d"une infinité de nombres premiers.

2) Commean+ 13est premier alors il est impair. Donc2janet par le lemme de

Gauss2ja:De plus, notonsn= 2mkaveckimpair. On a

a n+ 1 =a2mk+ 1 =a2m+ 1k1X i=0(1)ia2mi: Oran+ 1est premier donc nécessairementl= 2met ainsik= 1. 8

Correction exercice 18.

Rappels sur le symbole de Legendre.Etant donnéspun nombre premier impair etanon divisible parp, on dit queaest un carré (ou résidu quadratique) modulops"il existebtel queab2(modp). On définit le symbole de Legendreap =1siaest un carré modulop,

1sinon.

On a que:p

est multiplicative etap ap12 (modp): La loi de réciprocité quadratique, démontrée par Gauss, exprime pq en fonction deqp

Retour à la correction.

(. Remarquons queFern12 = 22n1et que 2 est le seul facteur premier deFern1. Donc par le critère de primalité de Lehmer, on a queFernest premier. ). Commen1, on aFern= 42n1+ 1, donc Fer n1 (mod 4); et par la loi de réciprocité quadratique on a3Fer n =Fern3 . De plus, Fer n1 + 1 (mod 3) doncFernn"est pas un carré modulo 3 (on vérifie directement que seuls 0 et 1 sont des carrés modulo 3),i.e.Fern3 =1. Ainsi 3

22n1= 3Fer

n12 3Fer n (mod Fer n) 1 (mod Fern):

References

[Dem97] Michel Demazure.Cours d"algèbre. Nouvelle Bibliothèque Mathématique [New Mathematics

Library], 1. Cassini, Paris, 1997. Primalité. Divisibilité. Codes. [Primality. Divisibility. Codes].

[DKM94] Jean Marie De Koninck and Armel Mercier.Introduction à la théorie des nombres. Collection

universitaire de mathématiques. MODULO, Mont-Royal, 1994. 9quotesdbs_dbs41.pdfusesText_41

[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

[PDF] nombre d'atomes sur terre

[PDF] pv=nrt

[PDF] liste segpa meurthe et moselle

[PDF] erea briey telephone