# 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?

• All of the following what? Sep 12, 2017 at 10:37
• because of remainder math 2 can be looked at as -1 but (-1)^2 =1^2 = 1, via pigeonhole principle if it doesn't divide by 3 within the first 3 it will never divide by 3 exactly. and quadratic residues are at most $\lceil{n\over 2}\rceil$ for any value of n.
– user451844
Sep 12, 2017 at 10:41
• @RoddyMacPhee, Quadratic residues are at most $\lceil n/2\rceil$? Isn't $4$ a quadratic residue, mod $5$? Sep 12, 2017 at 10:43
• I meant in number of them sorry. so a number n will have at most that amount of quadratic residues.
– user451844
Sep 12, 2017 at 11:34

$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$.

• Thanks. This makes sense to figure out if q^2 is divisible by 3 or 5, but what about the q^2 - 5 case? Sep 12, 2017 at 13:25
• @david Distribute [(q^2)-5]/3 = (q^2)/3 - 5/3 ... and your remainder is going to be [your remainder from (q^2)/3 - your remainder from 5/3] mod 3, so [(0 or 1)-2] mod 3 = [(-1 or -2)] mod 3 = 2 or 1. Sep 12, 2017 at 15:06

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$.

• "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." What does this mean? Also in the subtract 5 case did you mean to put a square over the (3k + 1)? Sep 12, 2017 at 13:27
• I don't know where you're getting "0202" and "1212" and "2222". That's not what I typed, and it's not what I see when I'm looking at my post. I also didn't put a square over anything when I was talking about subtracting $5$. Are you on a PC, or on the mobile app? I think there might be a display problem. Sep 12, 2017 at 13:29
• Sorry the comment didn't get copied correctly. I edited my post. I don't know if you can use LaTeX in the comments so I used ^ as a superscript. When you wrote (3k + 1) - 5, isn't this a possible value of q - 5 and not q^2 - 5. That's the point I wanted to make. Sep 12, 2017 at 14:22
• Ah. Once we've determined that the square is of the form $3k$ or $3k+1$, we can just call it that. The point is that the square is a $0$-type or a $1$-type, which makes the square minus $5$ a $1$-type or a $2$-type. I was showing how a $1$-type minus $5$ is a $2$-type, after having shown that the square could be a $1$-type. Does that make more sense? Sep 12, 2017 at 15:09
• Oh I see. Yeah that makes sense. Thanks. Sep 12, 2017 at 15:50

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 !!

$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$