If X and Y are integers, what is the remainder when x^2+Y^2

[ghong14]

http://postimg.org/image/44jzn1z87/

If X and Y are integers, what is the remainder when x^2+Y^2 is divided by 5?

1) When x-y is divided by 5, the remainder is 1
2) When x+y is divided by 5, the remainder is 2


I was trying to do this problem with picking numbers, i.e. numbers that satisfy x-y /5 with a remainder of 1 and x+y/5 with a remainder of 2. I then switched over to an algebraic method:

x-y = 5a+1 a could be 6, 11, 16........(not sure how this even helps)
x+y= 5b+2 b could be 7, 12, 17........

However, I didn't know what to do after that. Not sure if the step was even necessary at all. Is there a more comprehensive approach to solving this problem?

[RonPurewal]

Hi,
Please don't create new threads for problems that are already on the forum.

Check out this thread:
if-x-and-y-are-integers-t15424.html

If you still have questions, please post them there, not here. Thanks.

[ghong14]

Ron, it looks like the previous post has the question completely wrong. Instead of X^2+Y^2 he wrote X^2 and Y^2 and the explanations are therefore out of scope. I be more than happy to paste the question to the original post if you want.

[RonPurewal]

Yeah ok, so I'll leave this thread open.

Here are 2 ways in which you could approach this problem. Neither is particularly docile, but neither is particularly "exotic" or "insight-based" either; this is definitely a "grind" problem.

--

ALGEBRA:

You can actually take your algebraic expressions and run with them.

As you wrote...
x - y = 5a + 1
x + y = 5b + 2
where "a" and "b" are also integers.

so...
square them:
x^2 - 2xy + y^2 = 25(a^2) + 10a + 1
x^2 + 2xy + y^2 = 25(b^2) + 20b + 4

add them:
2(x^2) + 2(y^2) = 25(a^2) + 25(b^2) + 10a + 20b + 5

Every term is a multiple of 5, so 2(x^2 + y^2) -- in other words, 2 times the goal expression -- is a multiple of 5.
Dividing by 2 won't change the fact that something is a multiple of 5 (if it's still guaranteed to be an integer), so you know that the goal expression is a multiple of 5.

Done; the remainder is zero.

--

TESTING CASES:

As you wrote...

x-y could be 6, 11, 16........
x+y could be 7, 12, 17........

Take a look at those.
The point is that (x - y) and (x + y) are separated by 2y, which is an even difference (since y is an integer; 2*integer = even integer).
Therefore, (x - y) and (x + y) are either both even or both odd.
Also, x is halfway between (x - y) and (x + y), so you don't need any fancy algebra to find it.

Some cases with both #s even:
x - y = 6, x + y = 12 --> x = 9, y = 3
x - y = 6, x + y = 22 --> x = 14, y = 8
x - y = 6, x + y = 32 --> x = 19, y = 13
x - y = 16, x + y = 22 --> x = 19, y = 3
x - y = 16, x + y = 32 --> x = 24, y = 8
x - y = 16, x + y = 42 --> x = 29, y = 13

.... hey, i think i see a pattern here. X is always a remainder of 4, Y is always a remainder of 3.
If you try x - y and x + y = odd integers, you'll get the same thing.

At this point, you can try algebra:
x = 5(integer) + 4
y = 5(other integer) + 3
so...
x^2 + y^2
= [25(integer^2) + 40(integer) + 16] + [25(other integer^2) + 30(other integer) + 9]
= (a whole bunch of stuff that's divisible by 5) + 16 + 9
= (a whole bunch of stuff that's divisible by 5) + 25
So the remainder is 0.

If you don't like algebra, you can just test a bunch of these values. (If you're going to object with "But that would take too long!", first you'd better have an answer to "But what else are you gonna do?") You'll keep getting 0 until, eventually, you'll be convinced.

--

The main point I want to make about the methods above is that they are NOT "lightbulb moments" to any significant degree.
(The one possible exception would be the even/odd observation, but even that can be circumvented if you're willing to solve for particular values of x and y, whether by algebra or just by inspection.)

They are not perfectly straightforward -- i.e., it's very difficult to "see a path through" this problem if you aren't actually moving the pen on the paper -- but that's the point. Sometimes you just have to pick up the shovel and start digging.

[uzmail]

Well this is a big hole to dig and this type of Qs would take at least 5 minutes of mine. Oh, gmat...

Thank you Ron for the explanations.

[RonPurewal]

Well this is a big hole to dig and this type of Qs would take at least 5 minutes of mine.

The red thing is almost certainly false.

Don't talk yourself out of trying things.

Remember--As I'm way too fond of saying, there are 2 secrets to success here:
1/ Do stuff.
2/ Don't not do stuff.