Prove that $2^q+q^2$ is divisible by 3 where $q$ is a prime and $q\geq5$.

Question

I'm looking to prove that $2^q+q^2$ is divisible by $3$ where $q$ is a prime such that $q\geq5$.

I know that primes greater than five will be congruent to either $1\ (\text{mod}\ 3)$ or $2\ (\text{mod}\ 3)$, which means that the $q^2$-term will always be congruent to $1\ (\text{mod}\ 3)$ which simplifies the problem to finding the congruence of $2^q+1\ (\text{mod}\ 3)$. However, I'm unable to go any further as I'm unable to show that the congruence of $2^q\ (\text{mod}\ 3)$ is always equal to $2$.

Answer 1

Since $2 \equiv -1 \pmod{3}$ you are looking at $(-1)^q$ where $q$ is odd

Answer 2

To show that congruence of $2^q\pmod 3$ is equal to 2 for a prime $q\geq 5$, it's sufficient to prove it for odd numbers, because any prime $q\geq 5$ is odd. So it reduces to verifying that $2^1\equiv 2\pmod 3$ and $2^2\equiv 1\pmod 3$.

Answer 3

For an odd prime $q \geq 5$ we have $q^2 \equiv 3$. And if $q = 2n + 1$ then $2^q = (2^n)^2 \dot 2 \equiv 2$. So $2^q + q^2 \equiv 1$.

Answer 4

$2^{1} \equiv 2 \pmod{3}$; $2^{2} \equiv 1 \pmod{3}$;

$2^{3} \equiv 2 \pmod{3}$; $2^{4} \equiv 1 \pmod{3}$;

$2^{5} \equiv 2 \pmod{3}$; $2^{6} \equiv 1 \pmod{3}$;

$...$

Note that when the exponent is odd, the remainder equals to $2$ and when the exponent is even, the remainder is $1$.

This pattern keeps repeating because multiplying number with a remainder of $1\pmod{3}$ by $2$ equals to $2\pmod{3}$, and multiplying again by $2$ gives us the remainder of $4$, which is $1\pmod{3}$.

Because $q$ is odd, $2^{q} \equiv 2 \pmod{3}$.