[Citat] Fie ?irul dat prin = 1, = 2, = 4 ?i = + + pentru orice n>=1. Demonstra?i c? pentru orice întreg pozitiv N exist? (m?car) un indice astfel încât N divide

O sa rezolv o problema "asemanatoare".
Anume cea in care plecam cu cele trei valori initiale

ZERO, 1, 1,

si construim sirul definit (liniar) recursiv (printr-o recursiune de ordin trei) prin faptul ca fiecare termen urmator in sir este suma celor trei termeni (EDIT) care il preced.
Dam desigur de "acelasi" sir, usor translatat.

Acum, deoarece nu stiu la ce nivel trebuie sa rezolv problema, o sa o rezolv la nivelul la care ea se explica cel mai usor.

Fixam un astfel de N natural > 0.
Ne intereseaza sirul doar modulo N.
Atunci il luam modulo N si dam de alt sir cu valori in inelul

R = ZZ / N ZZ

al claselor de resturi modulo N.
(EDIT: R nu este multimea numerelor reale, este inelul "ring" (engleza) de clase de resturi modulo N. Cand folosesc o notatie pentru multimea numerelor reale scriu IR sau asa ceva.)
(Primul ZZ sta pentru multimea reprezentantilor claselor, numere intregi, grupul N ZZ sta pentru grupul numerelor intregi divizibile cu N, el spune ca doi reprezentanti conduc la / genereaza aceeasi clasa, daca si numai daca diferenta lor este in N ZZ.)

Consideram acum un sir cu termenii "cu mai multe componente", dar pentru care recursiunea este liniara si de pas unu. (Nu trei.)
Elementele acestui sir sunt vectori coloana (matrici 3x1) cu intrari din R,

Primul element este

[ 0 modulo N ]
[ 1 modulo N ]
[ 1 modulo N ]

(matrice 3x1 cu intrari in R).
scris de acum incolo "mai normal" ca sa nu pierd prea mult loc:
0
1
1
si de acum nu mai scriu acel modulo N, sa convenim asupra faptului ca lucram doar in R.

Trecerea de la un element la altul se obtine prin inmultirea din stanga cu matricea "companion" A (notatie pentru ce vine):
010
001
111
care este o matrice 3x3 peste R si care are determinantul
0+0+1-0-0-0 = 1 (element din R), element inversabil in R.
(Ridicam matricea la una din ZZ pe care o scriem la fel si vedem ca dam de o ridicare inversabila in ZZ.)

Tema:
Care este inversa B (in ZZ) a matricii de mai sus?

Ei bine, A este un element inversabil in grupul finit GL(3,R), Grup al aplicatiilor Liniare (general linear group), al matricilor inversabile 3x3 peste R. Matricea A are un ordin, cu alte cuvinte daca repetam inmultirea

AAA...A

de un numar (suficient de mare) de ori, dam de matricea unitate.
Daca nu credem acest lucru sau daca nu (vrem sa) stim de grupuri,
putem sa ne convingem printr-un element de finitudine.

Ne uitam la sirul de matrici
A, AA, AAA, ...
care nu poate sa ia decat un numar finit (cel mult (3x3)la puterea N) de valori (diferite), deci exista doi indici diferiti pentru care avem egalitate.
De exemplu
AAA...A
=
AAA...A AA...AAAAAA
in matrici 3x3 peste R.

"Simplificam" (prin inmultire din stanga cu inversa B a lui A construita mai sus) cu AAA...A si dam de ce vroiam.

Care este mai departe solutia?

Care e sursa problemei? Sunt sigur c? am mai v?zut-o ?i m? chinui s?-mi amintesc unde...

Problema este de la concursul Viitoriolimpici.ro, etapa a 7-a, clasa a9-a.

[Citat] Problema este de la concursul Viitoriolimpici.ro, etapa a 7-a, clasa a9-a.

Da, dar e luat? din alt? parte, precum majoritatea problemelor din acel concurs. ?i nu pot s?-mi amintesc de unde

Initial si eu am vrut sa izolez cumva periodicitatea "de la un cap la altul",
dovedind ca nu avem ceva "periodic de la o vreme"
cum este cazul de exemplu in calculul de zecimale pentru numarul 1 / 48,
dar nu am gasit o solutie fara a pune mana pe "un fel de inversa".
Cred ca idea de mai sus poate fi facuta riguroasa destul de repede,
acest punct este probabil (in conditii de olimpiada de exemplu) partea fragila a argumentarii. Cum filozofia mea in rezolvari este de a acoperi si ceea ce nu se cere dintr-o problema, daca ceea ce se cere se incadreaza in acelasi cadru structural, m-am apucat repede de tiparit. De exemplu, daca N = 1009, este un exercitiu instructiv (de programare cu elemente matematice deosebite) de vazut ca perioada sirului are ceva de-a face cu ordinul matricii A de mai sus vazuta ca matrice in GL( 3, IF(1009) ) .
(Aici IF(1009) este corpul cu 1009 elemente, realizat ca ZZ / 1009 ZZ.)
Cand ajunga acasa dau drumul la sagemath...
(Pentru mine, experimentul de fata este mai important decat rezolvarea problemei...)

[Citat] Cred ca idea de mai sus poate fi facuta riguroasa destul de repede

Ce nu e riguros aici?

[Citat] Ce nu e riguros aici?

Am avut doar foarte mici indoieli relative la faptul ca ceva poate lipsi pe fir. Mi-e greu sa descriu locul cu indoiala. In orice caz, pentru inceput, sirul

- este periodic (cu perioada P) incepand de la un K natural spre +oo,
stim din cele de mai sus, (nu folosesc efectiv in cele ce urmeaza,)

- este periodic (cu perioada Q) incepand de la un -L<0 intreg spre -oo,
stim din cele de mai sus,

dar doar scriind aceste propozitii nu am terminat. Dar terminam repede.
Mergem undeva inainte de indicele sirului (extins)
-L - 2.Q
de unde stim ca avem cel putin o perioada inainte (de -L, deci si) de 0,
vedem ca plecand de aici spre +oo se conserva perioada Q,
deoarece recursiunea "inapoi" dedusa este echivalenta cu recursiunea "inainte" data.
Deoarece indicele zero se afla intr-o perioada,
stim deja ca aceeasi valoare a sirului modulo N (anume zero modulo N) se va repeta in Q, 2Q, 3Q, ...

Argumentul (care mi-a lipsit) este desigur mult sub nivelul de "punere la incercare" al problemei in ansamblu, dar pe vremea mea ma depunctau rau la olimpiade daca nu imbucam bine propozitiile in astfel de locuri.

Am gasit in sfarsit timpul linistit in care sa ma ocup de problema pe care mi-am propus-o singur. Este un caz special care poate arata destul de clar "cam cum se plaseaza perioada" in sirul dat, depinzand de N-ul ales.

[Citat] De exemplu, daca N = 1009, este un exercitiu instructiv (de programare cu elemente matematice deosebite) de vazut ca perioada sirului are ceva de-a face cu ordinul matricii A de mai sus vazuta ca matrice in GL( 3, IF(1009) ) . (Aici IF(1009) este corpul cu 1009 elemente, realizat ca ZZ / 1009 ZZ.) Cand ajunga acasa dau drumul la sagemath... (Pentru mine, experimentul de fata este mai important decat rezolvarea problemei...)

Ne ocupam deci de sirul din ZZ (multimea numerelor intregi) care incepe cu
0,1,1,2,4
si in care de la rangul al patrulea orice termen al sirului este suma celor trei termeni premergatori.

Ne legam de periodicitatea sirului luat modulo N = 1009 ca mai sus.
Deci ne legam de acum incolo de sirul luat modulo N mai bine.

Facem un mic experiment matematic pentru a vedea cand apare primul 0 mod N, si cand apare pentru prima oara (strict dupa inceputul dat mai sus)
secventa 0 mod N, 1 mod N, 1 mod N,
dupa care desigur ca avem ciclare.

Folosesc cel mai simplu sage. Codul urmator poate fi pe intelesul tuturor:


sage: N = 1009
sage: R = IntegerModRing(N)
sage: R
Ring of integers modulo 1009
sage: sir = []
sage: sir.append( R(0) )
sage: sir.append( R(1) )
sage: sir.append( R(1) )
sage: sir
[0, 1, 1]
sage: for k in [ 3..100 ]:
....: sir.append( sir[-1] + sir[-2] + sir[-3] )
....:
sage: sir
[0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 696, 109, 723, 519, 342, 575, 427, 335, 328, 81, 744, 144, 969, 848, 952, 751, 533, 218, 493, 235, 946, 665, 837, 430, 923, 172, 516, 602, 281, 390, 264, 935, 580, 770, 267, 608, 636, 502, 737, 866, 87, 681, 625, 384, 681, 681, 737, 81, 490, 299, 870, 650, 810, 312, 763, 876, 942, 563, 363, 859, 776, 989, 606, 353, 939, 889, 163, 982, 16, 152, 141, 309, 602, 43, 954, 590, 578, 104, 263, 945, 303, 502, 741, 537, 771, 31, 330]
sage:

Bun, mai sus sunt primii cam 100 de termeni ai sirului si inca nu am dat de 0.

Las masina atunci sa mearga mai departe si imi printez locurile unde apare un 0. Cam acelsi cod nepus la punct a trimis masina de calcul in genunchi pentru N = 1009.


sage: N = 1009
sage: R = IntegerModRing(N)
sage: a = R(0); b=R(1); c=R(1); d=a+b+c;
sage: a,b,c,d
(0, 1, 1, 2)
sage: indexulLui_d = 3
sage: while d != R(0):
.... a=b;b=c;c=d; d=a+b+c; indexulLui_d += 1;

Dupa ce se termina am dat repede de primul index in care dam de zero, acesta este 4797. Am incercat si mai mult, dar programarea nu este chiar asa de limpede. La prima incercare, dupa ce am asteptat o vreme si am vazut ca ventilatorul este rau turat, m-am decis sa salvez cele scrise, sa opresc calculul si sa incerc cu un exemplu mai modest. Ma leg mai bine de N=19 in loc de 1009. Ciclarea are loc dupa cel mult N³ pasi. Numarul N³ este modest. Deci pot lucra si asa:


sage: N = 19
sage: R = IntegerModRing(N)
sage: sir = [ R(0), R(1), R(1) ]
sage: for k in [3..N^3-1]:
....: a = sir[-1] + sir[-2] + sir[-3]
....: sir.append(a)
....: if a == R(0): print "Anulare pentru k=%d" % k
....: if a == R(0) and sir[-2] == R(0) and sir[-3] == R(1):
....: print "CICLARE!"
....: break
....:
Anulare pentru k=18
Anulare pentru k=28
Anulare pentru k=55
Anulare pentru k=62
Anulare pentru k=70
Anulare pentru k=103
Anulare pentru k=116
Anulare pentru k=119
Anulare pentru k=120
Anulare pentru k=138
Anulare pentru k=148
Anulare pentru k=175
Anulare pentru k=182
Anulare pentru k=190
Anulare pentru k=223
Anulare pentru k=236
Anulare pentru k=239
Anulare pentru k=240
Anulare pentru k=258
Anulare pentru k=268
Anulare pentru k=295
Anulare pentru k=302
Anulare pentru k=310
Anulare pentru k=343
Anulare pentru k=356
Anulare pentru k=359
Anulare pentru k=360
CICLARE!
sage:


Pana la ciclare mai dureaza ceva, desi prima reaparitie a lui 0 mod N este destul de repede, pe locul 18...

Lasand cam acelasi cod sa mearga pentru N=109, cu mesaje doar pentru prima anulare si pentru ciclare...

sage: N = 109
sage: R = IntegerModRing(N)
sage: anulareDeja = False
sage: sir = [ R(0), R(1), R(1) ]
sage: for k in [3..N^3-1]:
....: a = sir[-1] + sir[-2] + sir[-3]
....: sir.append(a)
....: if a == R(0) and not anulareDeja: print "Anulare pentru k=%d" % k
....: if a == R(0) and sir[-2] == R(0) and sir[-3] == R(1):
....: print "k=%d :: CICLARE!" % k
....: break
....:
Anulare pentru k=105
k=990 :: CICLARE!
sage:

Acelasi lucru cu N = 1009...

N = 1009
R = IntegerModRing(N)
a=R(0); b=R(1); c=R(1); d=a+b+c
for k in xrange( 3, N^3-1 ):
if d == R(0):
print "Anulare pentru k=%d" % k
if d == R(0) and c == R(0) and b == R(1):
print "k=%d :: CICLARE" % k
break
a=b; b=c; c=d; d=a+b+c

Dam de o salata de mesaje mai mare...
Anulare pentru k=4797
Anulare pentru k=4890
Anulare pentru k=4977
Anulare pentru k=7182
Anulare pentru k=7390
Anulare pentru k=7527
Anulare pentru k=9015
Anulare pentru k=9037
Anulare pentru k=10610
Anulare pentru k=12021
Anulare pentru k=12882
Anulare pentru k=13150
::::::::::::::::::::::::
Anulare pentru k=501764
Anulare pentru k=503614
Anulare pentru k=503920
Anulare pentru k=506673
Anulare pentru k=507522
Anulare pentru k=508587
Anulare pentru k=509023
Anulare pentru k=509036
Anulare pentru k=509039
Anulare pentru k=509040
k=509040 :: CICLARE

INTREBARE:
Exista un mod mai rapid de detectare a perioadei?
Ce joc special
- asociaza lui N=19 perioada P=360,
- asociaza lui N=109 perioada P=990,
- asociaza lui N=1009 perioada P=509040
?

Iata cam cum putem proceda structural.
Cer scuze daca am plictisit, mai ales daca am tiparit prea mult text inestetic la o problema estetica.

Va rog sa ma credeti, usa care se deschide se deschide spre o lume noua, importanta si plina de surprize structurale.
In zilele de azi putem scrie cod matematic structural, acest lucru trebuie sa intre cat se poate de repede la catedrele de liceu si facultate. (Nu este musai, dar ar fi bine, deoarece 30% din matematicienii dotati s-ar putea ajuta intr-un mod nebanuit... Desigur ca nu exista un profit imediat sau de durata pentru cei de la catedra care "nu cerceteaza"...)

Sa ne uitam la urmatorul cod:
sage: N = 19
sage: G = GL( 3, GF(N) )
sage: # N trebuie sa fie prim mai sus, GF(N) este "general field" cu N elemente
sage: A = matrix( GF(19), 3,3, [0,1,0, 0,0,1, 1,1,1] )
sage: A
[0 1 0]
[0 0 1]
[1 1 1]
sage: A.parent()
Full MatrixSpace of 3 by 3 dense matrices over Finite Field of size 19
sage: a = G(A)
sage: a
[0 1 0]
[0 0 1]
[1 1 1]
sage: a.parent()
General Linear Group of degree 3 over Finite Field of size 19
sage: a.order()
360
sage: G.order()
304812862560
sage: (N^3-1) * (N^3-N) * (N^3-N^2)
304812862560

In orice caz putem cere:
sage: A.charpoly()
x^3 + 18*x^2 + 18*x + 18
sage: A.charpoly().factor()
(x + 6) * (x^2 + 12*x + 3)
sage: A.charpoly().parent()
Univariate Polynomial Ring in x over Finite Field of size 19
sage:

Primul factor se anuleaza in $-6\in\mathbb{F}_{19}$, ordinul multiplicativ al acestui element este...
sage: F = GF(19)
sage: u = F(-6)
sage: u.multiplicative_order()
18
deci cel mai mare ordin la care ne putem astepta potrivit teoremei lui Fermat.

Ne uitam la polinomul care ramane... El are radacinile... hm, intr-un corp extensie patratica a lui GF(19). Sa le calculam si sa vedem ce ordin au ele...
Ei bine...
sage: R.<x> = GF(19)[]
sage: R
Univariate Polynomial Ring in x over Finite Field of size 19
sage: K.<u> = GF( 19^2, name='u', modulus=x^2 + 12*x + 3 )
sage: K
Finite Field in u of size 19^2
sage: u^2 + 12*u + 3
0
sage: v = -12-u
sage: v
18*u + 7
sage: v^2 + 12*v + 3
0
sage: u.multiplicative_order()
360
sage: v.multiplicative_order()
360


Putem face acum acelasi lucru cu N=1009.
Codul pe care il tiparim este de forma...

N = 1009
F = GF(N)
G = GL( 3, F )
A = matrix( F, 3,3, [0,1,0, 0,0,1, 1,1,1] )
a = G(A)
a.parent()
a.order()
G.order()
(N^3-1) * (N^3-N) * (N^3-N^2)
P = A.charpoly()
P.parent()
P.factor()

Dam de...
sage: N = 1009
sage: F = GF(N)
sage: G = GL( 3, F )
sage: A = matrix( F, 3,3, [0,1,0, 0,0,1, 1,1,1] )
sage: a = G(A)
sage: a.parent()
General Linear Group of degree 3 over Finite Field of size 1009
sage: a.order()
509040
sage: G.order()
1082902696158696930067783680
sage: (N^3-1) * (N^3-N) * (N^3-N^2)
1082902696158696930067783680
sage: P = A.charpoly()
sage: P.parent()
Univariate Polynomial Ring in x over Finite Field of size 1009
sage: P.factor()
(x + 882) * (x^2 + 126*x + 866)
sage: R.<x> = F[]
sage: K.<u> = GF( 1009^2, name='u', modulus=x^2 + 126*x + 866 )
sage: u.multiplicative_order()
509040

Pentru N = 31 de exemplu, polinomul caracteristic pe care il obtinem este ireductibil. Intr-un astfel de caz ne-am putea astepta la o perioada relativ mare (fata de 31), nu se intampla insa asa, un pseudomotiv este si faptul ca N^3-1 se divide cu N-1 = 30 care vine cu multi divizori...
Trebuie sa inchei aici. Nu inainte de a propune...


PROBLEMA:
Fie p un numar prim.
Fie A matricea companion cu intrarile din ZZ modulo p (notat GF(p))

010
001
111

Atunci ordinul lui A divide ordinul grupului
G = GL( 3, GF(p) )
de matrici 3x3 din GF(p) inversabile.

Se stie ca ordinul lui G este (p^3-1)(p^3-p)(p^3-p^2) .
Dar daca intelegem diagonalizarea, rezulta chiar mai mult, anume:

ordinul lui A (si deci si perioada sirului din problema initiala)
divide unul din numerele urmatoare
p^3-1,
p^2-1 (pe care nu il mai inmultim cu p-1, deoarece (p-1) divide (p^2-1)
(si p-1)

Cum putem alege p astfel incat ordinul lui A sa fie relativ mare fata de p ?
Intrebarea de mai sus nu este bine pusa, o intrebare clara, dar ambitioasa ar fi:

Care este supremumul multimii de valori
ordin(A) / (p^3) ,
calculate pentru toate numerele prime p...