[PDF] M2 EFM 2) En utilisant l'exercice





Previous PDF Next PDF



PGCD ET NOMBRES PREMIERS

Exemple : 22 et 15 sont premiers entre eux. On est alors assuré que l'équation admet un couple solution d'entiers. Méthode : Démontrer que deux entiers 



Exercices de MATHÉMATIQUES

Montrer que si deux nombres entiers x et y sont premiers entre eux il en est de même pour les entiers 2x + y et 5x + 2y. 2. Déterminer les entiers naturels 



Correction devoir maison Exercice 1 : 1)Si n est un nombre entier

2)Démontrer que deux nombres entiers consécutifs sont premiers entre eux. Soit n un entier naturel tel que n > 0. On considère donc n et n + 1 deux entiers 



PGCD Théorème de Bézout Théorème de Gauss

Christophe ROSSIGNOL?. Année scolaire 2018/2019. Table des matières. 1 PGCD Nombres premiers entre eux. 2. 1.1 PGCD de deux nombres entiers naturels .



les nombres de fibonacci

lequel il cherche à calculer le nombre de Nous allons montrer que deux termes succes- ... 2 et F. 1 sont premiers entre eux. • Supposons que F.



Eléments de base en arithmétique

Montrer que si n est la somme des carrés de deux entiers consécutifs Deux nombres sont dits premiers entre eux si leur plus grand diviseur.



Feuille 7 : Arithmétique

Exercice 7-2 Calculer le pgcd de 48 et 210 et de 81 et 237. Exercice 7-5 Démontrer que



M2 EFM

2) En utilisant l'exercice 4 montrer que m et n sont premiers entre eux si Montrer que si n est le produit de h ? 1 nombre premiers impairs distincts.



suites de fibonacci

Montrer que pour que x le troisième nombre F. 3.



Exercices de mathématiques - Exo7

Exercice 11 ***IT. Pour n ? N on pose Fn = 22n. +1 (nombres de FERMAT). Montrer que les nombres de Fermat sont deux à deux premiers entre eux. Correction ?.



[PDF] PGCD – NOMBRES PREMIERS ENTRE EUX - Pierre Lux

L'ensemble des diviseurs communs à a et à b est l'ensemble des diviseurs de leur PGCD Preuve : a et b sont deux entiers naturels non nuls On note D = PGCD(a 



[PDF] PGCD ET NOMBRES PREMIERS - maths et tiques

Démontrer que pour tout entier naturel n 2n + 3 et 5n + 7 sont premiers entre eux D'après le théorème de Bézout avec les coefficients 5 et -2 on peut 



[PDF] 2° Lorsque deux nombres sont premiers entre eux

Lorsque deux nombres sont premiers entre eux leurs puissances quelconques sont premières entre elles Soient les nombres 22 et i5qui sont premiers entre 



[PDF] Chapitre 1 Arithmétique Partie 6 : Nombres premiers entre eux

On dit qu'un nombre entier naturel p ? 2 est premier si ses seuls diviseurs positifs sont 1 et p Remarque : Les nombres premiers feront l'objet d'une étude 



[PDF] Probabilité pour que deux entiers soient premiers entre eux

La fonction de Möbius est la fonction µ : N? ? Z définie par : – µ(1) = 1 – µ(p1 ··· pr)=(?1)r si les pi sont des nombres premiers distincts – µ(n)=0 sinon 



[PDF] Probabilité que deux entiers soient premiers entre eux - ENS Rennes

Proposition 1 Pour n ? N? on note rn la probabilité que deux entiers choisis au hasard dans [1n]2 soient premiers entre eux On a : rn ??????



[PDF] Nombres premiers entre eux - Free

Deux nombres sont donc premiers entre eux s'ils n'ont d'autres diviseurs communs que 1 et Démontrer en utilisant le théorème de Bezout la propriété :



[PDF] Nombres premiers entre eux - Serveur de mathématiques - LMRL

1) Calculer le PGCD de 45 et 46 puis le PGCD de 200 et 201 Démontrer que deux entiers naturels consécutifs sont premiers entre eux 2) Démontrer que pour tout 



[PDF] Arithmétique - suite - Pages personnelles Université Rennes 2

Quels sont les diviseurs communs `a 390 et 525 ? Page 2 Nombres premiers - Nombres premiers entre eux Nombre premier : Un nombre entier 



[PDF] 1´Enoncé

De mani`ere plus générale on peut montrer que si a et b sont deux entiers premiers entre eux alors il existe une infinité de nombres premiers de la forme an + b 

  • Comment montrer que 2a B et a sont premiers entre eux ?

    De au + bv = 1, on déduit a(u-v) + (a+b)v = 1, donc a et a+b sont premiers entre eux.
  • Comment savoir si deux polynômes sont premiers entre eux ?

    On dit que deux polynômes non tous deux nuls sont premiers entre eux si leur PGCD est égal à 1.
  • En effet, on peut écrire (n + 1) x 1 - n x 1 = 1, donc d'après le théorème de Bézout, les entiers n et n + 1 sont premiers entre eux. On a donc PGCD(n ; n+1) = 1 = (n + 1) - n.

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:quotesdbs_dbs41.pdfusesText_41
[PDF] montrer que n et 2n+1 sont premiers entre eux

[PDF] exercice calcul tva ht ttc

[PDF] on note dn le pgcd de n(n+3) et de (2n+1)

[PDF] pgcd(a^2 b^2)

[PDF] montrer que n et n+1 sont premiers entre eux

[PDF] pgcd*ppcm=ab

[PDF] ppcm de deux nombres premiers entre eux

[PDF] cours developpement communautaire

[PDF] montrer qu'il existe une infinité de nombres premiers de la forme 4n+1

[PDF] extraction du charbon

[PDF] origine du charbon

[PDF] 3 conditions necessaires a la formation du charbon

[PDF] la formation des combustibles fossiles schéma

[PDF] origine des combustibles fossiles seconde

[PDF] formation du charbon schéma