remainder

Question

find the remainder when 5 ^ 37 / 63

AkamaiBrah · Answer

The answer is 5.

However the solution requires the knowledge that 5 and 63 are coprime to each other and the application of "Euler's Theorem".

This is not helpful for preparing people for the GMAT and only wastes valuable time for people who think there is a solution in the realm of GMAT-required knowledge.

Anybody can find hard problems on the internet. Quit trying to show off -- you're just wasting people's time.

vcbabu · Answer

37 /4 remainder is 1

so 5^37/63 becomes 5/63 so remainder is 5 .

it is very much gmat problem. This come across during the prep of gmat.

AkamaiBrah · Answer

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?

abhi750 · Answer

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

AkamaiBrah · Answer

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.

vesam · Answer

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

lahoosaher · Answer

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

Thanks for the explanation.

remainder

Prep Toolkit

Top 5 GMAT Debrief Videos

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards