need help in this!

Question

Remainder when 7^50 is divided by 13 is

a. 10
b. 11
c. 12
d. 25
e. None

Please give answer with full explanation!

gurpreetsingh · Answer

IMO A - 10

Remainder of 7^50 when divided by 13 is same as of 49^25

now if we divide 49 by 13 we get remainder as 10 thus

Remainder of 7^50 when divided by 13 is same as of 10^25 
Remainder of 7^50 when divided by 13 is same as of 100^12 * 10

now if we divide 100 by 13 we get remainder as 9 thus

Remainder of 7^50 when divided by 13 is same as of 9^12 * 10
Remainder of 7^50 when divided by 13 is same as of 81^6 *10

now when we divide 81 by 13 we get remainder as 3, thus

Remainder of 7^50 when divided by 13 is same as of 3^6 *10
Remainder of 7^50 when divided by 13 is same as of 9^3 *10
Remainder of 7^50 when divided by 13 is same as of 81*90
now when we divide 81 by 13 we get remainder as 3
when we divide 90 by 13 we get remainder as 12

Remainder of 7^50 when divided by 13 is same as 3*12 = 36
now when we divide 36 by 13 we get remainder as 10.

Thus 10 - A

Theory::

suppose the number N1, N2, N3 give quotient Q1,Q2,Q3 and remainders R1,R2,R3 when divided by D

N1 = D * Q1 + R1
N1 = D * Q2 + R1
N1 = D * Q3 + R1 and so on

Case 1.    P = N1*N2*N3 = (D * Q1 + R1) * (D * Q2 + R2) * (D * Q3 + R3) ... so on

P = D*K + R1*R2*R3 .. so on where K is some number.

Thus the remainder when P is divided by D is same as the remainder when R1*R2*R3...so on is divided by D
Reason : since only R1*R2*R3..so on, is free of D.

Case 2.   S = N1+N2+N3 = (D * Q1 + R1) + (D * Q2 + R2) + (D * Q3 + R3) ... so on

S = D*K + R1+R2+R3  ..so on

Thus the remainder when S is divided by D is same as the remainder when R1+R2+R3 ..so on is divided by D
Reason : since only R1+R2+R3 ..so on, is free of D.

hardnstrong · Answer

Thanks Gurpreet

This way is pretty good to solve such kind of problems. I solved few more using the same method

Though i understood the method, still couldn't understand the theory part. Can you please explain the theory in a easier way, for better understanding

+1 to you mate

lprassanth · Answer

Aliter:

LCM of 7 and 13 is 91. So for every 91*n, the remainder is 0.
So we need to find out the greatest n that will pitch 91*n to just less than 7^50.
so (7^50 - 91*n) {when n is so maximized} is the remainder.. and this remainder, evidently, lies between 1 and 91.
this implies that 7(7^49 - 13*n) is the remainder
This means that the remainder is a multiple of 7......  observation 1

We know that, the units digit of 7^50 is 9.  ......  observation 2

Combining 1 and 2 --> we are looking for a number divisible by 7 which is
1) less than 91
2) and ends with a 9.
The only possible number is 49.
This means that (7^50 - 91*n) {when n is so maximized} = 49
so  49 MOD 13 = 10

Pardon the complexity/narration. Comments welcome.

idiot · Answer

now, that's pretty efficient :idea:

+1 buddy

gurpreetsingh · Answer

read the theory again and open up the brackets of case1, you will get all the numbers multiplied by D except R1*R2*R3

take simple eg.... (x+1)(x+2) = x*x + 2*x +1*x + 1*2
only 1 and 2 when multiplied together will not have value of X

now go back to the case1 of the theory.
and using the eg above open up the brackets, you will get D*K + R1*R2*R3
=> when divided by D it will leave remainder as R1*R2*R3
but if R1*R2*R3 > D then we can further divide it by D
so actual remainder will the remainder of R1*R2*R3 when divided by D

If you have understood case1...case 2 will look easy to u.

Let me know if this helps....

need help in this!

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