Mathematical Reflections 2012, Issue 6 - Problem J249

Problem:
Find the least prime $p>3$ that divides $3^q-4^q+1$ for all primes $q>3$.

Proposed by Titu Andreescu.

Solution:
Since $3^5-4^5+1=-780=-(2^2\cdot3\cdot5\cdot13)$, and $3^7-4^7+1$ is not divisible by $5$, we only have to show that $p=13$ divides $3^q-4^q+1$ for all primes $q>3$. Since $q$ is a prime, $q=6k \pm 1$ for some $k \in \mathbb{N}^*$. Moreover, $3^{6k} \equiv 1 \pmod{13}$ and $4^{6k} \equiv 1 \pmod{13}$, then
$$\begin{array}{rrrrrr} 3^{6k+1}-4^{6k+1}+1 & \equiv & 3-4+1 \equiv & 0 & \pmod{13} \\ 3^{6k-1}-4^{6k-1}+1 & \equiv & 9-10+1 \equiv & 0 & \pmod{13}, \end{array}$$
which gives the conclusion.