редица от цели числа ...

[portokal]

Нека [tex]p[/tex] и [tex]q[/tex] са прости числа и {[tex]a_{n}[/tex]}[tex]_{n=1}^\infty[/tex] е редица от цели числа, дефинирана с равенствата

[tex]a_{0}=0[/tex], [tex]a_{1}=1[/tex], [tex]a_{n+2}=pa_{n+1}-qa_{n}[/tex]

при [tex]n\ge 0[/tex].
Да се намерят [tex]p[/tex] и [tex]q[/tex] ,ако съществува [tex]k[/tex] такова, че [tex]a_{3k}=-3[/tex]

[martin123456]

1. [tex]\pmod{p}[/tex]
[tex]a_{n+2} \equiv -qa_n[/tex]. Имаме следната редица остатъци [tex]a_0=0, a_1=1, a_2=0, a_3=-q,\ldots[/tex]. По индукция лесно излиза, че [tex]a_{2k} \equiv 0 \pmod{p}[/tex].
2. Да допуснем, че [tex]p,q[/tex] са нечетни
[tex]\pmod{2}[/tex]
[tex]a_0=0,a_1=1,a_2=1,a_3=0,a_4=1 \ldots[/tex]. По индукция [tex]a_{2k+1} \equiv 0 \pmod{2}[/tex]. Това означава, че [tex]3k \equiv 0 \pmod{2}[/tex].

Случай 1: [tex]p,q[/tex] нечетни
Тогава тъй като [tex]k[/tex] е четно (от 2) излиза, че [tex]3|p[/tex] (от 1). Това значи, че [tex]p=3[/tex]
Случай 2: [tex]p,q[/tex] не са нечетни едновременно
Случай 2.1: [tex]p=2[/tex]
Случай 2.2: [tex]q=2[/tex]

Дефакто стигнахме до 3 случая:
[tex]p=2[/tex]:
[tex]p=3[/tex]:
[tex]q=2[/tex]:

Мислч, че това услеснява нещатата. Ако някой иска да довърша да пише.

[mkmarinov]

От рекурентната зависимост и малко обработка:
[tex]a_{3k+3}=(p^2-q)a_{3k+1}-pqa_{3k}[/tex]
[tex]a_0, a_3[/tex] са четни и ако [tex]p^2-q[/tex] е четно, по индукция всички членове на редицата са четни. Т.е. или [tex]p=2[/tex], или [tex]q=2[/tex]. Ако q=2, p>2: [tex]a_3=p^2-2>a_2, a_4=p.a_3-q.a_2>(p-q)a_2>0[/tex] и по индукция всички членове са положителни, което е противоречие. Т.е. p=2.
[tex]a_{n+2}=2a_{n+1}-qa_n[/tex] => [tex]a_{n+1} \equiv 2a_n (mod q)[/tex]. По индукция [tex]a_{n+1} \equiv 2^n (mod q)[/tex] => [tex]a_{3k} \equiv 2^{3k-1} (mod q)[/tex]
Нетрудно се доказва, че [tex]a_n \equiv n (mod q-1) =>-3= a_{3k} \equiv 3k (mod q-1) =>q-1 / 3k+3[/tex]
=> [tex]2^{3k+3} \equiv 1 (mod q)[/tex] => [tex]16.a_{3k} \equiv 1 (mod q)[/tex] => [tex]-48 \equiv 1 (modq)[/tex] => q=7.