What is the remainder when 5^91 is divided by 91?

Question

What is the remainder when  5^{91}  is divided by 91?

A. 5
B. 8
C. 13
D. 34
E. 47

chetan2u · Accepted Answer

I doubt such a question will come in actuals..

Otherwise..
 1) as per remainder theorem
  91=7*13  so LCM of (7-1,13-1) or (6,12) is 12
So  5^{91}  will give the same remainder as  5^7 , since 91/12 gives 7 as remainder.
 5^7=(5^3)^2*5=(125)^2*5 
125 will leave 125-91=34 as remainder
So  34*34*5=34*170 
170 will leave a remainder of -12
 34*(-12)= 68*(-6)=-23*-6=138 
So remainder=138-91=47

2) if you do not know the theorem you will have to get the terms closer to multiple of 91 
So  5^{91}=(5^4)^{22}*5^3=625^{22}*5^3 
91*7=637, so remainder is  625-637=(-12) 
So new term is  (-12)^{22}*5^3 
 As even power, it will be same as   12^{22}*5^3=4^{22}*3^{22}*5^3

Also  4^3=64  and remainder is 64-91=-27
So  (4^3)^7*4*3^{22}*5^3=(-27)^7*3^{22}*5^3=(-3^3)^7*3^{22}*5^3=-(3^{43}*5^3*4) 
Now  3^6=729  and 91*8=728 so remainder is 1
 -(3^6)^7*3*5^3*4=-(1^7*3*5^3*4)=-1*3*5*100=-1*3*5*9=-135 
So POSITIVE remainder will be  91*2-135=182-135=47

E

you could have used this too to simplify
Now  2^7*5=128*5=640  remainder will be 640-637=3

rahulkashyap · Answer

91 = 7*13

Let us find out Rem  and Rem  - using binomial expansion
We will combine them later.

Rem

= 5(5)^90 / 7 
= 5( 125) ^ 30 / 7
=5 (126-1)^30 / 7

remainder = 5. (-1)^30 = 5 / 7
rem = 5

Rem  
= Rem 5. (5)^90 / 13
= 5. (25)^45 / 13
= 5. (26-1)^45)/ 13
remainder = 5. (-1)^45 / 13
= -5/13 = r= 8

So, our answer is a number which leaves a remainder of 5 when divided by 7 and it should leave a remainder of 8 when divided by 13.

simplifying this, we get N= 91K + 47
Hence 47 is the reaminder

azooktutor · Answer

This one is really tricky! I don't have an answer yet, but I'm wondering if the fact that  5^7  does have a remainder of 47, and that  5^{91} = (5^7)^{13} , is significant.

I'm also wondering if 91's proximity to 100 could be useful. If you were to divide any power of 5 (over  5^1 ) by 100, you would always get a remainder of 25. So perhaps the answer has something to do with using 100 as an approximation and then adding to the remainder.

Very interested to hear others' thoughts!

Edit: formatting

ShailendraSYadav · Answer

5^91/91...Remainder?

Solution:
=5^91/91
=5^91/7*13

=Points to observe 
 5 (num) and 91(deno) are co-primes 
 Need to factor the denominator,
 
=We need to develop 2 equations (as 2 factors are there in denom) based on divisibility of individual denominators..

Part:1
=5^91/7
=Based on Euler's theorem, Euler number for prime number at denom. will be 6. (7-1=6)
=dividing 91/6= 6K+1
=so 5^1/7= 5 
=5 remainder.
=Equation1 N1= 7A+5
 
Part:2
=5^91/13
=Based on Euler's theorem, Euler number for prime number at denom. will be 12. (13-1=12)
=dividing 91/13= 12K+7
=so 5^7/13
=25*25*25*5/13
=8 Remainder
= Equation2 N2= 13B+8

Fill the values in Equation N1 (N1= 7A+5), Values are= 5,12,19,26,33,40,47
Fill the values in Equation N2 (N2= 13B+8), Values are= 8,21,34,47

First value satisfying both the equations will be remainder, i.e. 47.

Thanks!

Sanyami19 · Answer

How did you arrive at the equation N= 91K + 47 from this statement - is a number which leaves a remainder of 5 when divided by 7 and it should leave a remainder of 8 when divided by 13. Could you pls explain in detail?

ABHISEKGMAT123 · Answer

Re(5^91/ 91)
Split 91, the divisor to 13 and 7

Separately find out out the remainders with 13 and 7.
With 7,
E(7)=6, therefore 5^91 actually reduces to Rem(5^1/ 7)----------Remainder is 5; the no is of the form 7a+5
Similarly with 13,
E913)=12, therefore 5^91 actually reduces to Rem(5^7/ 7)----------Remainder is 8; the no is of the form 13b+8
Congruence of these two number types gives 47 the answer.  (7a+5=13b+8)

HarshavardhanR · Answer

The methods highlighted by the good folks above are much better for such a question. That said, I wanted to highlight how one can still solve such a question by brute force simplification.

---
Harsha

Show Spoiler

Attachment:

GMAT-Club-Forum-thxsq3q0.png [ 82.65 KiB | Viewed 153 times ]

What is the remainder when 5^91 is divided by 91?

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

GMAT Problem Solving (PS) Questions

What is the remainder when 5^91 is divided by 91?

Prep Toolkit

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