Gmat Prep PT1 question

A very common mistake on DS questions, especially under the time pressure of the test, is missing information provided in the question. p is an odd integer here, so only one of your two examples is applicable.

Plugging in numbers is a more reliable approach for remainders questions than for questions on pretty much any other subject - there's a whole area of math that you don't need to know about called modular arithmetic that guarantees remainders follow certain patterns, so what's true for a couple of sets of numbers is usually true for other numbers.

One fact from modular arithmetic that can be useful to know: you can add remainders, as long as you're dividing by a fixed number. That is (to take an example), if the remainder is 2 when you divide x by 7, and the remainder is 3 when you divide y by 7, the remainder will be 5 when you divide x+y by 7. You could use that here (along with the first part of the explanation below) to see that the remainder should be 1 using Statement 2.

We can prove everything in the abstract, though it's a bit tedious to do:

if p is odd, and p is the sum of two squares, it must be the sum of an odd square and an even square - that is, it must be the sum of the square of an even number and the square of an odd number. So we know p = x^2 + y^2, where x is even and y is odd.

If you take an even number x, we can write x as 2k, for some integer k. Then x^2 = 4*k^2. That is, every even square is a multiple of 4.

If you take an odd number y, we can write y as 2m + 1, for some integer m. Then y^2 = (2m + 1)^2 = 4m^2 + 4m + 1 = 4(m^2 + m) + 1. So any odd square is 1 more than a multiple of 4 -- that is, it has a remainder of 1 when you divide by 4.

If we now add: p = x^2 + y^2 = 4k^2 + 4m^2 + 4m + 1 = 4(k^2 + m^2 + m) + 1, we see that p is one more than a multiple of 4, so the remainder must be 1 when we divide p by 4.

cramya wrote:

That is (to take an example), if the remainder is 2 when you divide x by 7, and the remainder is 3 when you divide y by 7, the remainder will be 5 when you divide x+y by 7.

On the same note this can be extended for subtraction and multiplication. Correct me if I am mistaken here.

Yes, it can be extended to both multiplication and subtraction. The one thing I left out - you sometimes need to 'wrap' your answer back into the correct range for remainders. So, if:

-the remainder is 5 when j is divided by 7
-the remainder is 6 when k is divided by 7

then you can be sure that:

-Since 5 + 6 = 11, the remainder will be 4 when we divide j + k by 7 (we take the remainder when 11 is divided by 7, since 11 is too large to be the remainder here)

-Since 5 - 6 = -1, the remainder will be 6 when we divide j - k by 7 (since the remainder cannot be -1, we add 7 to get it into the correct range)

-Since 5*6 = 30, the remainder will be 2 when j*k is divided by 7 (again, we take the remainder when 30 is divided by 7, since 30 is too large).