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} = pa_{3k+2} - qa_{3k+1} = p(pa_{3k+1} - qa_{3k}) - qa_{3k+1} = (p^2 - q)a_{3k+1} - pqa_{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} = pa_{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} \pmod q$ for $n \ge 0$ and we conclude by induction that $a_{n+1} \equiv 2^n \pmod q$. Then we have $-3 = a_{3k} \equiv 2^{3k-1} \pmod q$. On the other hand, the recurrence relation gives $a_{n+2} \equiv 2a_{n+1} - a_n \pmod{q - 1}$. Hence
$$a_{n+2} - a_{n+1} \equiv a_{n+1} - a_n \equiv \cdots \equiv a_1 - a_0 = 1 \pmod{q-1},$$
i.e. $a_{n+1} \equiv n+1 \pmod{q-1}$ for $n \ge 0$. Then $-3 = a_{3k} \equiv 3k \pmod{q-1}$ and the Little Fermat's theorem gives that $2^{3k+3} \equiv 1 \pmod q$. Thus $1 \equiv 2^{3k+3} \equiv 16 \cdot 2^{3k-1} \equiv -48 \pmod 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$.