Fall Mathematical Competition

Let $p$ and $q$ be odd. The recurrence relation gives $a_2=p$ and $a_3=p^2-q$. Therefore $a_0$ and $a_3$ are even. Since $$a_{3k+3}=p{a}_{3k+2}-q{a}_{3k+1}=p(p{a}_{3k+1}-q{a}_{3k})-q{a}_{3k+1}=(p^2-q)a_{3k+1}-pq{a}_{3k}$$ and the number $p^2-q$ is even, we prove by induction that $a_{3k}$ is even for every $k\ge 0$, a contradiction. Let us suppose now that $q=2$. Then $p\ge 3$, since otherwise every $a_n$, $n\ge 2$, is even. We shall prove by induction that $a_{n+1}>a_n\ge 0$ for $n\ge 0$, i.e. $a_n>0$ for every $n\ge 1$, which is a contradiction. The assertion is obvious for $n=0$. Assume that it follows for $n=k$, i.e. $a_{k+1}>a_k\ge 0$. Then we have $$a_{k+2}=p{a}_{k+1}-a_k=(p-2)a_{k+1}+2(a_{k+1}-a_k)>a_{k+1}>0,$$ hence $a_{k+2}>a_{k+1}>0$. It remains to consider the case $p=2,q>2$. It follows by the recurrence relation that we have $a_{n+2}\equiv 2a_{n+1}(\mathrm{mod}q)$ for $n\ge 0$ and we conclude by induction that $a_{n+1}\equiv 2^n(\mathrm{mod}q)$. Then we have $-3=a_{3k}\equiv 2^{3k-1}(\mathrm{mod}q)$. On the other hand, the recurrence relation gives $a_{n+2}\equiv 2a_{n+1}-a_n(\mathrm{mod}q-1)$. Hence $$a_{n+2}-a_{n+1}\equiv a_{n+1}-a_n\equiv \cdots \equiv a_1-a_0=1(\mathrm{mod}q-1),$$ i.e. $a_{n+1}\equiv n+1(\mathrm{mod}q-1)$ for $n\ge 0$. Then $-3=a_{3k}\equiv 3k(\mathrm{mod}q-1)$ and the Little Fermat's theorem gives that $2^{3k+3}\equiv 1(\mathrm{mod}q)$. Thus $1\equiv 2^{3k+3}\equiv 16\cdot 2^{3k-1}\equiv -48(\mathrm{mod}q)$, i.e. $q=7$. In this case we have $a_3=2^2-7=-3$ and the required prime numbers are $p=2$ and $q=7$.