Nombres de Fermat, Mersenne et Fibonacci

blogdemaths.wordpress.com 1

Nombres de F ermat

On définit la suite (F

n) des nombres de Fermat par :

8n2N;Fn= 22n+1Théorème - .Pour toutm >0,

F m= F0F1:::Fm1+2Démonstration.Le théorème est évidemment vrai sim= 1.

Soitm >0.

F m+12 = 22m+11 = (22m)21 = (22m1)(22m+1) = (Fm2)Fm

Donc, par récurrence, si on suppose que F

m= F0F1:::Fm1+2 alors F m+1= (Fm2)Fm+2 (F0F1:::Fm1)Fm+2 = F

0F1:::Fm1Fm+2

ce qui prouve le théorème.2Nombres de Mersenne

On définit la suite (M

n) de nombres de Mersenne par :

8n2N;Mn= 2n1Théorème - .Pour toutm > n,

PGCD(M

m;Mn) = MPGCD(m;n)Autrement dit, PGCD(2 m1;2n1) = 2PGCD(m;n)1. Démonstration.Sim > n, alors on peut faire la division euclidienne demparn: m=nq+ravecr < n blogdemaths.wordpress.com1

Ainsi,

2 m1 = 2m2nq+2nq1 = 2 nq+r2qn+2qn1 = 2 qn2r2nq+2nq1 = 2 qn(2r1)+(2n)q1 = 2 qn(2r1)+(2n1)(1+2n+22n+:::+2(q1)n) Donc, M m= 2nqMr+Mn(1+2n+22n+:::+2(q1)n)

Montrons alors que les diviseurs communs à M

met Mnsont identiques aux diviseurs communs à M net Mr. Sidest un diviseur commun à Mmet Mnalorsddivise MmMn(1+2n+22n+ :::+2(q1)n) = 2nqMr. Mais commeddivise le nombre Mnqui est impair,dne peut diviser 2 et donc nécessairement,ddivise Mr. Réciproquement, siddivise Mnet Mralorsddivise 2nqMr+Mn(1+2n+22n+ :::+2(q1)n) = Mm. Nous avons donc montré que les diviseurs communs de Mmet M nsont les mêmes que les diviseurs communs de Mnet Mr. D"où :

PGCD(M

m;Mn) = PGCD(Mn;Mr) Si on considère la suite (rn) des restes successifs dans l"algorithme d"Euclide appliqué àmetn, et si on noterNle dernier reste non nul (qui se trouve être le PGCD demet n) alors :8>>>>>><>>>>>>:PGCD(M m;Mn) = PGCD(Mn;Mr0)

PGCD(M

n;Mr0) = PGCD(Mr0;Mr1)

PGCD(M

rN1;MrN) = PGCD(MrN;M0) Or, M

0= 0 donc PGCD(Mm;Mn) = PGCD(MrN;M0) = MrN= MPGCD(m;n). CQFD.3Nombres de F ibonacci

On définit la suite (fn) des nombres de Fibonacci par :

8>>>><>>>>:f

0= 0 f 1= 1 f n+2=fn+1+fnpour toutn2NThéorème - .Pour toutm > n,

PGCD(fm;fn) =fPGCD(m;n)Démonstration.Le principe est similaire à celui mis en oeuvre pour les nombres de

Mersenne.

Etape 1 :

On commence par montrer l"égalité suivante :

8u;v >0;fu+v=fufv+1+fu1fv(1)

On fixevet on fait une récurrence suru.

Siu= 1,fufv+1+fu1fv= 1fv+1+0fv=f1+v

On suppose l propriété vraie au rangu.

f u+1+v=fu+(v+1) =fufv+2+fu1fv+1 =fu(fv+1+fv)+fu1fv+1 = (fu+fu1)fv+1+fufv =fu+1fv+1+fufv CQFD.

Etape 2 :

On montre par récurrence que pour tout entierv >0 et tout entier naturelq,fvdivise f qv(la récurrence est faite surq) : Siq= 0, le résultat est évident carfvdivisef0= 0. On suppose quefvdivisefqv. D"après l"égalité (1), on a : f (q+1)v=fqv+v =fqvfv+1+fqv1fv et commefvdivisefqvetfv, il divisefqvfv+1+fqv1fvdoncf(q+1)v.

Etape 3 :

On montre que deux nombres de Fibonacci consécutifs sont premiers entre eux, c"est-à-dire que pour tout entier natureln, PGCD(fn;fn+1) = 1. C"est vrai sin= 0 car PGCD(f0;f1) = PGCD(0;1) = 1.

On suppose que PGCD(fn;fn+1) = 1.

Sidest un diviseur commun àfn+1etfn+2alorsddivisefn+2fn+1=fn. Ainsi, dest un diviseur commun àfn+1etfndoncd= 1 (car par hypothèse de récur- rence, le plus grand diviseur commun àfn+1etfnest 1).

Etape 4 :

A présent, passons à la démonstration du théorème à proprement parler. Soitm > n. On commence par effectuer la division euclidienne demparn: m=nq+ravecr < n En appliquant l"égalité (1) démontrée précédemment àu=nqetv=r, on obtient : f m=fnq+r =fnqfr+1+fnq1fr

Comme pour les nombres de Mersenne, on montre que les diviseurs commun àfmetfnsont identiques aux diviseurs commun àfnetfr:

3 Siddivisefmetfnalors il divisefmetfnq(voir étape 2) donc il divisefm f nqfr+1=fnq1fr. Mais commefnqetfnq1sont consécutifs, ils sont premiers entre eux (étape 3), donc, puisqueddivisefnq, il est lui aussi premierfnq1. Mais puisqueddivise le produitfnq1fr, c"est qu"il divisefr. Réciproquement, siddivisefnetfr, alorsddivisefnq(étape 2) et donc il divise f nqfr+1+fnq1fr=fm. On en déduit que PGCD(fm;fn) = PGCD(fn;fr) et le même raisonnement utilisant l"algorithme d"Euclide que celui effectué pour les nombres de Mersenne montre que : PGCD(fm;fn) = PGCD(frN;f0) = PGCD(fPGCD(m;n);0) =fPGCD(m;n)4quotesdbs_dbs47.pdfusesText_47

[PDF] Nombres de Fermat, Mersenne et Fibonacci - Blogdemaths

Les nombres de Fermat