Putere a lui 3

alex2009
Grup: membru
Mesaje: 288
13 Feb 2011, 13:15

[Trimite mesaj privat]

Putere a lui 3 [Editează] [Citează]

Definim sirul

prin

,

si

. Daca

este un numar prim atunci sa se demonstreze ca n este o putere a lui 3.

---
Student Automatica

Euclid
Grup: Administrator
Mesaje: 2659
08 Feb 2011, 11:15

[Trimite mesaj privat]

[Editează] [Citează]

[Citat]
Definim sirul

prin

,

si

. Daca

este un numar prim atunci sa se demonstreze ca n este o putere a lui 3.

Problema este enun?at? în mod foarte neprietenos, deoarece acel ?ir satisface recuren?a liniar?

Definim

Acest ?ir (clar cresc?tor!) satisface o recuren?? liniar? de ordinul trei:

Este suficient s? ar?t?m c?

Pentru n=1 este simplu, deoarece modulo 2 ?irul este periodic: 0,0,1,0,0,1,... etc. Pentru n mai mare decât unu, introducem

Notând

, ?inem cont de

?i ar?t?m c?

sunt divizibile prin

. Practic, acest lucru revine la examinarea a patru polinoame în variabilele

.
cod maxima

(%i24) tellrat(u^2-5);
(%o24) [u^2-5]
(%i25) f(n):=ev(ratdisrep(rat((A+B*u)^n+(A-B*u)^n )),expand,algebraic)+(-1)^n;
(%o25) f(n):=ev(ratdisrep(rat((A+B*u)^n+(A-B*u)^n)),expand,algebraic)+(-1)^n
(%i26) f(2);
(%o26) 10*B^2+2*A^2+1
(%i27) f(1);
(%o27) 2*A-1
(%i28) load("lrats")$

(%i29) fullratsubst((A^2-1)/5,B^2,f(2)),expand,factor;
(%o29) (2*A-1)*(2*A+1)
(%i30) fullratsubst((A^2-1)/5,B^2,f(3)),expand,factor;
(%o30) 8*A^3-6*A-1
(%i31) fullratsubst((A^2-1)/5,B^2,f(4)),expand,factor;
(%o31) (2*A-1)*(2*A+1)*(4*A^2-3)
(%i32) fullratsubst((A^2-1)/5,B^2,f(5)),expand,factor;
(%o32) (2*A-1)*(16*A^4+8*A^3-16*A^2-8*A+1)

Deoarece ?irul Y-grecilor satisface ?i el o recuren?? de ordinul trei, iar modulo

acest ?ir începe cu 0, 0, *, 0, 0, *, afirma?ia de mai sus este demonstrat?.

Recenind la problem?:

Reiter?m critica de mai sus referitoare la forma neprietenoas? în care ne este data recuren?a.
Suntem curio?i de o solu?ie direct?, deoarece e clar c? nu în modul de mai sus a fost descoperit? aceast? proprietate.
Numerele

satisfac cele de mai sus. Am vrea s? mai vedem m?car înc? un exemplu; nu de alta, dar este posibil ca alte numere prime s? nu existe...

---
Euclid

gauss
Grup: Administrator
Mesaje: 6933
09 Feb 2011, 21:28

[Trimite mesaj privat]

[Editează] [Citează]

Doar cateva mentiuni care pot sa e facem sa credem in plus ca problema nu este una de matematica, ci una 'de-a v-a?i ascunselea'.

Sa zicem ca stim ce este sirul fiului lui Bonacci.
Termenul general se scrie cu ajutorul numerelor
u = (1+s)/2 si 1/u
unde s este radicalul de ordinul doi din 5.
desigur ca daca calculam
v = uu dam intamplator de numarul (3+s)/2 .
1/v este (3-s)/2 , deoarece (3+s)(3-s) = 3.3 - s.s = 9-5 = 4.

Numere 2 si 7 au fost gasite dupa ce s-a scris termenul general. Tot asa si relatia artificiala de recurenta...

Pentru motive de teoria numerelor, doresc doar sa mentionez ca inelul de intregi algebrici ZZ[ u ] = { a+bu : a,b in ZZ } are descompunere unica in factori primi. Deseori, divizibilitatea in ZZ (de exemplu pentru termeni ai sirului Fibonacci) se rescrie echivalent la una in ZZ[ u ]. (A se observa ca u este unitate in ZZ[ u ] - rationanlizam numitorul in scrierea lui 1/u.)

Problema mai vrea atunci sa ne impacheteze si divizibilitatea polinomului
Y^(2m) + Y^m + 1
prin
Y^2 + Y + 1
(de exemplu - am luat cazul in care acel (-1) la ceva este un unu... a se vedea si ce se intampla cand este minus unu)
daca puterea m este una nedivizibila prin 3. (Ideea de demonstratie a divizibilitatii este de a verifica prin Bezout ca radacinile lui YY+Y+1 inserate in celalalt polinom dau zero, desigur. Macar devine clar de ce m nu are voie sa fie divizibil cu 3...)
Vazand acest lucru si inlocuind Y cu y, o unitate din ZZ[ u ] egala cu o putere a lui u, rezulta ca
(y^(2m) + y^m + 1) / y^m
se divide prin
(Y^2 + Y + 1) / y
in inelul dat...

Exact acest lucru m-a iritat pe vremea cand am fost la liceu si trebuia sa rezolv probleme de "olimpiada". Aceste probleme au devenit pe atunci atat de artificiale uneori in constuctia lor, incat conduceau elevii intr-o directie gresita.

Nu este rau sa rezolvam astfel de enigme, macar sa le citim si intelegem solutia sau structura in care solutia se prezinta cat decat organic, dar ele nu sunt drumul bun in intelegerea si/sau cercetarea matematica.

---
df (gauss)

alex2009
Grup: membru
Mesaje: 288
13 Feb 2011, 13:15

[Trimite mesaj privat]

[Editează] [Citează]

Ca mai sus se arata prin inductie ca