remainder

Hmm. Please show me by what basic theorem (37 mod 4) = 1 implies that (5^37 mod 63) = (5 mod 63).
IMHO, that's a pretty big "hand wave."

And by what logic do you test 37 mod 4 in the first place?

The answer is 5..

Guys, I do not understand how vcbabu solved it.. Neither do I know Eulers theorm or coprimes..

It is pretty straightforward..

5^3 = 125 .. and when 125 is divided by 63, the remainder is -1

=> 5^37/63
=> (5^36 * 5)/63
pls note that 5^36 will yield a remainder of 1 as it can be written as 5^(3*12)

so final remainder is 1 * 5 = 5

I didn't pick pen for this answer.. May be you have a better way to do it.. but I think this works as well..

This is actually a very clever solution which is actually a variation of the use of Euler's theorem. Forget about the fancy names -- in plain words, basically, if A and B do not have common factors (i.e., they are "coprime") then there exists an exponent n for which A^n / B will have remainder of 1.

For this problem, that number is 6 (the computation of which is beyond the scope of this forum). Hence if 5^6 mod 63 = 1 then 5^(6*6) mod 63 also has mod 1 and, similar to your reasoning, 5^(6*6 + 1) mod 63 = 5. You can determine that 5^6 mod 63 = 1, but that is quite difficult considering 125^2 is a five-figure number that you have to divide by 63.

Your solution is clever because most people (including me) are NOT taught to think of remainders in terms of negative numbers -- in fact, you are not guaranteed to find a remainder of -1 (though you will always find one of +1) and this works ONLY if the numbers do not have a common factor.

I still think this is too hard of a problem for the GMAT (need to accept concept of "negative remainder", need to apply some guesswork to find the exponent that yilds a remainder of -1 (which is not guaranteed) and understand that the remainder will alternate between -1 (or 62) and 1 for increasing multiples of 3 in the exponent), but perhaps i was wrong .

Whatever the case, kudos to you for solving this in a clever and straight forwad manner. Nice job.

5 ^ 37 = (5^(12*3) * 5)
5 ^ 3 = 125
125 / 63 = -1 (As per Eulers theorem)

5^3 and 5^36 will gave same reminder,
=> 1 * 5 = 5

Ans:5

This probelm is very difficult for GMAT.
Good one though.

Thanks for the explanation.