MathDB

3

Part of 2016 Brazil Undergrad MO

Problems(1)

Primes and linear recurrences

Source: 38th Brazilian Undergrad MO (2016) - First Day, Problem 3

11/25/2016
Let it k≥1k \geq 1 be an integer. Define the sequence (an)n≥1(a_n)_{n \geq 1} by a0=0,a1=1a_0=0,a_1=1 and
an+2=kan+1+an a_{n+2} = ka_{n+1}+a_n
for n≥0n \geq 0. Let it pp an odd prime number. Denote m(p)m(p) as the smallest positive integer mm such that p∣amp | a_m. Denote T(p)T(p) as the smallest positive integer TT such that for every natural jj we gave p∣(aT+j−aj)p | (a_{T+j}-a_j).
[list='i'] [*] Show that T(p)≤(p−1)⋅m(p)T(p) \leq (p-1) \cdot m(p). [*] Show that if T(p)=(p−1)⋅m(p)T(p) = (p-1) \cdot m(p) then
∏1≤j≤T(p)−1j≢0(modm(p))aj≡(−1)m(p)−1(modp) \prod_{1 \leq j \leq T(p)-1}^{j \not \equiv 0 \pmod{m(p)}}{a_j} \equiv (-1)^{m(p)-1} \pmod{p}

number theoryrecurrence relation