7
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ All of the following what? $\endgroup$ – Bernard Sep 12 '17 at 10:37
  • $\begingroup$ 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. $\endgroup$ – user451844 Sep 12 '17 at 10:41
  • $\begingroup$ @RoddyMacPhee, Quadratic residues are at most $\lceil n/2\rceil$? Isn't $4$ a quadratic residue, mod $5$? $\endgroup$ – G Tony Jacobs Sep 12 '17 at 10:43
  • 1
    $\begingroup$ I meant in number of them sorry. so a number n will have at most that amount of quadratic residues. $\endgroup$ – user451844 Sep 12 '17 at 11:34
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ "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)? $\endgroup$ – rayanisran Sep 12 '17 at 13:27
  • $\begingroup$ 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. $\endgroup$ – G Tony Jacobs Sep 12 '17 at 13:29
  • $\begingroup$ 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. $\endgroup$ – rayanisran Sep 12 '17 at 14:22
  • 1
    $\begingroup$ 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? $\endgroup$ – G Tony Jacobs Sep 12 '17 at 15:09
  • $\begingroup$ Oh I see. Yeah that makes sense. Thanks. $\endgroup$ – rayanisran Sep 12 '17 at 15:50
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks. This makes sense to figure out if q^2 is divisible by 3 or 5, but what about the q^2 - 5 case? $\endgroup$ – rayanisran Sep 12 '17 at 13:25
  • $\begingroup$ @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. $\endgroup$ – user3067860 Sep 12 '17 at 15:06
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.