Given $a,b\in\mathbb Z^+$, and let $F_{a,b}:\mathbb N\to\mathbb N$ be a function such that $F_{a,b}(0)=0$, $F_{a,b}(1)=1$ and $F_{a,b}(n+1)=a\cdot F_{a,b}(n)+b\cdot F_{a,b}(n-1)$. $F_{1,1}$ correspond to the Fibonacci function.

Conjecture for which I would like to see a proof:

If $a,b$ are co-prime and $p>2$ is a prime that doesn't divide $b$, then

$F_{a,b}\left(p-\left(\frac{a^2+4b}{p}\right)\right)\equiv 0\pmod p$,

where $\left(\frac{a^2+4b}{p}\right)$ is the Legendre symbol.

I have tested the conjecture with $10,000$ randomly selected $a,b,p$.

Observation: for Fibonacci numbers $a=b=1$ and $a^2+4b=5$.

See also The $\gcd$ operator commutes with functions defined by linear recurrence relations

I've never been interested in the Fibonacci numbers and when I recently read about them on Wikipedia I realized that all this interesting theorems for Fibonacci numbers could be generalized to linear recurrence relations with constant coefficients.

This funny relation $p|F_{p-(\frac{5}{p})}$ promted for an explanation. I guessed that the '$5$' came from the solution of the characteristic polynomial of the recurrence relation for the Fibonacci relation with the solutions $\frac{1\pm\sqrt{5}}{2}$. Subtracting the greater root from the smaller and square gives $5$ and this seems to be correct. For the general case $x_{n+2}-ax_{n+1}-bx_n=0$ the characteristic polynomial is $t^2-at-b=0$ with the solutions $\frac{a\pm\sqrt{a^2+4b}}{2}$.

Since I have an excellent system to check hypotheses (BigZ) the conjecture was easy to test computationally.


I'm running low on time so here is half:

Suppose $a^2 + 4b$ is a quadratic residue mod $p$, then indeed we can see by completing the square $x^2 - ax -b$ has two solutions in $\mathbb{F}_p$ lets call them $c,d$.

It's then easy to show by induction that mod $p$ we have that $F_{a,b}(n) \equiv \frac{1}{c-d}c^n - \frac{1}{c-d} d^n$

But then Fermat's little theorem tells us that $c^{p-1} \equiv 1$ and $d^{p-1} \equiv 1$ so $F_{a,b}(p-1) \equiv 0$ as desired.

The other case is more complicated and I don't have time to write it right now but you can take the same approach as above but this time $c,d$ lie in $\mathbb{F}_{p^2}$, the quadratic field extension of $\mathbb{F}_p$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.