For some integer $q$, $q^2 - 5$ is divisible by all of the following EXCEPT which of the following? I was stuck trying to solve a GRE math question, and this question came to my mind when I looked at the solution. The question is

For some integer $q$, $q^2 - 5$ is divisible by all of the following EXCEPT


(A) $29$ 
(B) $30$ 
(C) $31$ 
(D) $38$ 
(E) $41$ 

I solved it by eliminating answers (plugging in values for $q$ which obviously took some time and won't work for larger numbers), and the solution states:
Start small. Remember that when divided by $3, q^2$ has remainder $0$ or $1$. So $q^2 - 5$ has remainder $1$ or $2$, meaning not divisible by $3$, so B.
How do we know that the remainder when $\frac{q^2}{3}$ is only going to be $0$ or $1$ only? I know the remainder HAS to be less than 3, but how do you figure out that it can't be $2$? And how do you deduce that it can only be $1$ or $2$ when $5$ is subtracted from the result? It's easy to see when you plug in values and check, but is there a generalized method to find out?
 A: $q$ is an integer, so it can either be congruent to $0$, $1$ or $2$ mod $3$.  Another way to write $q \equiv 2$ mod $3$ is $q \equiv -1$ mod $3$.  This means that $q^2 \equiv 1$ mod $3$ because $(-1)^2=1$.  Therefore, $q^2$ has remainder of only $1$ or $0$.
You can extend this to mod $5$, because all integers are congruent to either $0$, $1$, $2$, $3$, $4$ mod$5$, or alternatively $0$, $1$, $2$, $-2$, $-1$.  Squaring a number means that the squared number is congruent to either $1$ or $2^2$ or is a multiple of $5$.
A: When you look at things modulo $3$, there are three kinds of numbers: those of the form $3k$ (multiples of 3), those of the form $3k+1$, and those of the form $3k+2$. Let's try squaring them, and see what form results:
$$\begin{align}
(3k)^2 &= 9k^2=3(3k^2)\\
(3k+1)^2 &= 9k^2+6k+1=3(3k^2+2k)+1\\
(3k+2)^2 &= 9k^2+12k+4=3(3k^2+4k+1)+1
\end{align}$$
As you can see, each square is of the form $3K$ or $3K+1$ for some new $K$.
An easier way to check this is to simply look at $0^2$, $1^2$ and $2^2$, since the numbers $0$, $1$ and $2$ serve as representatives for the three classes mentioned above.
As for subtracting $5$, you can do similar calculations.
$$(3k+1)-5=3k-4=3k-6+2=3(k-2)+2$$
or to use a more compact notation:
$$1-5\equiv 2\pmod{3}$$
You can also verify that $0-5\equiv 1\pmod3$.
A: See any integer which is not a multiple of 3 can be written as
$$
q = 3K \pm 1
$$
Therefore,
$$
\ q^2 = 9\ k^2 \pm 6K + 1
$$
so, when divided by 3, it always gives remainder as 1.
While for those integers which are multiples of 3, they give remainder as 0.
Hope this Helps !!
A: $q^2-5=( q^2-1) +4
= ( q+1) (q-1) +4$
Now $q-1, q, q+1$ are three consecutive integers  and hence one of them should be a multiple of 3
Case $1$: $q-1$ or $q+1$ is a multiple of $3$ then,  $q^2-5$ is not because $4$ is not a multiple of $3$
Case $2$:  $q$ or $q^2$ is a multiple of $3$ but then $q^2 -5$ is not a multiple of $3$
So $q^2 -5$ can never be a multiple of $3$ and hence the answer is B $30$
