If p is a positive odd integer, what is the remainder when p is divided by 4?

1. When p is divided by 8, the remainder is 5.
2. p is the sum of the squares of two positive integers


Here is how I solved it (after the exam :) ). Wondering if there is an easier approach.

A) (8*n + 5)/4 -> sufficient

B) p is odd. So in the sum one is odd and one is even.

p = e^2 + o^2

e^2 will be divisible by 4.
o^2 = (2n+1)(2n+1) / 4 = (4n^2 + 4n + 1)/4 -> sufficient

there are two different ways in which i could interpret this question:
one) you're wondering whether there's a method that's not as intellectually challenging / exhausting as this one, even though it might take longer;
two) you're wondering whether there's a faster method, even if that method may be more intellectually demanding;
three) you're looking for a method that is both intellectually simpler and faster.

i'll answer them all.

one)
yeah, you can always plug in a bunch of numbers until you've satisfied yourself that the statements are sufficient.
for (1), just find the first few numbers that give remainder 5 upon division by 8: 5, 13, 21, 29, 37, etc. all of these give remainders of 1 upon division by 4, so that's convincing enough. sufficient. (note: the gmat WILL NOT give problems on which a spurious pattern appears, only to be broken after the 40th or 50th number; if you see a pattern persist for 4-5 cases, you can take it on faith that the pattern persists indefinitely.)
for (2), you should make the same realization you made above: one of the numbers has to be odd and the other even. then just try a bunch of possibilities:
1^2 + 2^2 = 5
2^2 + 3^2 = 13
3^2 + 4^2 = 25, etc
1^2 + 4^2 = 17
2^2 + 5^2 = 29
3^2 + 6^2 = 45, etc
all these give a remainder of 1 upon division by 4. sufficient.

--

two)
two options here.
first option: learn the basics of what's called 'modulo arithmetic'. if you're interested, i can post the very very very basics in this thread; it's a lot like the 'clock arithmetic' that you may have studied in grade school, if you went to a cool enough grade school.
second option: memorize the fact that all even perfect squares are divisible by 4 (and thus give remainder 0 upon division by 4), and that all odd perfect squares are one more than a multiple of 4 (and thus give remainder 1 upon division by 4). therefore, if one of the squares is even and the other odd (as stipulated by statement 2), the overall remainder will be 0 + 1 = 1. these are the facts that you derived via algebra above, but of course it's faster if you have them by heart.

--

three)
not a chance.

Thanks for the response and the exam tips. I am interested in knowing about modulo arithmetic. Please post some basic qs.

here's the easiest way to think about modulo arithmetic: think about it the way you'd think about 'clock arithmetic' (something you may have done as an enrichment exercise in grade school). this 'clock arithmetic' - which you can think of as performing arithmetic around a clock, with the numbers 0-11 only (imagine an 0 where the 12 normally goes on a clock face) - can be generalized to any number, not just 12, although it's easiest to describe 12 first because the clock face provides a convenient visual.

here's basically the way it works:
first, note that the numbers on the clock face - 0 through 11 - are exactly the numbers that are possible remainders upon division by 12. therefore, think of these numbers as standing for remainders upon division by 12. (they don't have to - in fact, modulo arithmetic has a slew of applications that have nothing whatsoever to do with remainders - but remainders are the only application of modulo arithmetic that's relevant to the gmat.)

--NOTE: the following examples are all "mod 12" (i.e., using 12 as a base, as in clock arithmetic)--

ADDING: just add the normal way, but take away 12 if a number is larger than 12.
examples: 4 + 3 = 7; 8 + 8 = 4; 5 + 7 = 0

SUBTRACTING: just subtract the normal way, but add 12 if a number is smaller than 12.
examples: 8 - 3 = 5; 3 - 5 = 10; 0 - 3 = 9

MULTIPLYING: just multiply the normal way, but take away as many 12's as necessary to return the number to the acceptable range (0-11).
examples: 5 x 6 = 6; 3 x 8 = 0; 11 x 11 = 1 (think about how many 12's you have to take away in each case)

dividing is a bit hairy, but it's irrelevant; it doesn't have any immediate applications to the wild world of remainders.

as you can see, the arithmetic operations aren't that different from traditional arithmetic operations; you just have to 'correct' the results for having gone around the clock a certain number of times. the great thing is that all the usual rules of arithmetic, such as the distributive and commutative properties, still apply, so most of your already extant mathematical intuition will still be valid.

--

now make the relevant analogies for any other base (base is called "modulo"). for statement (2) of this problem, you're using modulo 4, so we'll do that.
for instance, 3 + 2 is now 1, and 3 x 2 is now 2 (because you take away 4's).

facts:
* in modulo 4 there are only 4 positive integers (!): 0, 1, 2, and 3
* in modulo 4, evens are still evens and odds are still odds: 0 and 2 are even, and 1 and 3 are odd. (this wouldn't happen if you were using an odd modulo, such as 5; think about why not)
* all the rules about odds and evens (o + o = e, o + e = o, etc) are still valid

so:
the following is a list of ALL perfect squares in modulo 4:
0^2 = 0
1^2 = 1
2^2 = 0
3^2 = 1
it's pretty easy to see that the only odd sum you can get is 0 + 1 = 1. this means that your remainder is 1, so statement 2 is sufficient.
this is REALLY quick if you understand the underlying basics of modulo arithmetic.

let me know whether this stuff makes sense to you. i'm actually glad you're interested in it; it's good stuff.

Hey Ron,

Awesome...

although..could you explain a bit further... about modulo 5.. as you suggested.... odd even tip ??

i tried for 8 - odd even sqaures...and they give only 0,1,4 as remainders... made it so simple...
but i got the same for 5... ???

thanks

you can't really talk about "odd" and "even" anymore when your modulo is an odd number.

here's why:
with an even modulo (like 4), all even numbers stay even, and all odd numbers stay odd:
odd numbers: 1 --> 1, 3 --> 3, 5 --> 1, 7 --> 3, 9 --> 1, etc
even numbers: 2 --> 2, 4 --> 0, 6 --> 2, 8 --> 0, 10 --> 2, etc

with an odd modulo, though, you've got problems, because some numbers will flip the script on you.
for instance, 6 (which is even) becomes 1 (odd) modulo 5.
you can come up with the same sort of examples with any odd modulo.

--

analogy:
if you change a picture by just sliding things around, but not rotating them, then concepts such as "top", "bottom", "left", and "right" are still meaningful.
however, if you're allowed to rotate or reflect the picture, then there's really no such thing as left/right/top/bottom anymore, because those concepts would now depend upon the transformation employed.
same goes for odd/even, which are preserved under an even modulo but not under an odd one.

i hope that makes sense.