What is the remainder when 49^1000 is divided by 23?

Question

What is the remainder when  49^{1000}  is divided by 23?

A. 9
B. 8
C. 7
D. 6
E. 1

Are You Up For the Challenge: 700 Level Questions: 700 Level Questions

SherzodAzamov · Answer

49^{1000}  =  (46+3)^{1000}  =  23k + 3^{1000}

3 - 3 (mod 23)
 3^2 - 9 (mod 23) 
 3^3 - 4 (mod 23) 
 3^4 - 12 (mod 23) 
 3^5 - 13 (mod 23) 
 3^6 - 16 (mod 23) 
 3^7 - 2 (mod 23) 
 3^8 - 6 (mod 23) 
 3^9 - 18 (mod 23) 
 3^{10} - 8 (mod 23) 
 3^{11} - 1 (mod 23)

Hence,  3^{11k} - 1^k (mod 23)  =  3^{11k} - 1 (mod 23)

3^{1000}  =  3^{11*{90}+10}  -  3^{10} - 8   (mod 23)

The answer is B

Let me know if there is a shorter way

Nik11 · Answer

I ask to confirm the validity of the following approach  (it took me more than 3 min to solve):

49/23 leaves r= 3 ---> 3^1000 that we can write as 81^250/23 leaves r=12 ---> 12^250/23
or 144^125/23 that leaves r=6 ---> 6^125/23 or (3^125 * 2^125) / 23 or (243^25 * 32^25) / 23
this is probably the part that requires a bit of "calculations" since you should multiply 243 by 32 (that gives 7776) 
and divide the result by 23 You'll find a r=2 ---> 2^25 (remember that we had: (243*32)^25)
2^25 or 32^5 this leaves a r=9 hence 9^5/23 or 3^10 or 243^2 that leaves r= 13 ----> 13^2 or 169
169/23 leaves the final r=8 IMO  B

Abdeviliiers · Answer

Reducing each 2(23)+3 to 3 does not change the remainder when this is divided by 23 . (To see this, apply one reduction at a time. Then, one factor gets reduced by a multiple of 23 , and the rest stay the same. Subtract the reduced value from the value before the reduction, and factor out the unaffected factors. What is left is a multiple of 23 . This argument actually works for all remainders when a product is divided by a fixed number.)

Now, what are the remainders when powers of 3 are divided by 23 ?

Exponent Remainder

01

13

29

34 (reduced from 27 )

412

513

616

72

86

918

108

111

So, the remainder when 311 is divided by 23 is 1 . (Fermat’s Little Theorem would be an argument sufficient to prove that the remainder when 322 is divided by 23 is 1 . However, we would still need at least part of the table, as will be seen later.)

This result can be used to lower the exponent on the 3 without changing the remainder after a division by 23 . In particular, 31000=(3990)310=(311)90310 .

Reducing the 311 to 1 and the 310 to 8 does not change the remainder when the product is divided by 23 (by a similar argument as was used to reduce each 2(23)+3 to 3 ). All that is left is (190)8=8 . The remainder when 8 is divided by 23 is 8 , so 8 is the remainder when the original number 491000 is divided by 23 .

rsrighosh · Answer

Bunuel   chetan2u   VeritasKarishma 
Could you please share your approach

carouselambra · Answer

Is there any theorem that we can apply here?
 yashikaaggarwal  could you please help?

CEdward · Answer

Anytime you see divisibility involving large exponents you have two choices. Unit digits or cyclicity.

Take consecutive powers of 7 (e.g. 7^1,7^2,7^3) until you find the remainder of 1. That will tell you what the cycle is (e.g. it could be q cycle of 3,4,5 etc). Then, once you figure that out, divided the large exponent by that result.

Posted from my mobile device

rsrighosh · Answer

SherzodAzamov

a) Could you please explain how did you reach formulating this? Is there any formula u r using?

b) How did u reach the red highlighted part. What is the logic behind it.

c) How did you find remainder of  3^{11} . Did you actually calculate  3^{11}  and divide by 23 to get the mod?

yashikaaggarwal · Answer

We can solve using Euler Method.
Since numerator and denominator are co prime.
Then the value of denominator-1 will leave 1 as remainder if we divide denominator by numerator^denominator-1
Here,
49^22/23 will leave remainder 1
Using this,
We are left with 49^10/23
49 can be written as (23*2+3)^10
Opening bracket, 23*2^10 will not leave any remainder.
3^10/23
We can find value of 3^10 = 59049/23 will leave remainder 8
Or you can break 3^10 into (3^2)^5 or (3^5)^2
9 can't be break into 23 value.
But 243 can be break into (23*10+13)^2
13^2/23 => 169/23 will leave remainder 8.

Answer is B

Posted from my mobile device

chetan2u · Answer

Hi

The question requires Binomial expansion or Euler s formula or some pattern to find your answer.

GMAT would give you remainder questions where you can find a pattern without too much of calculations. 
This question is too calculation intensive to find a way in actuals.

You can leave the question as it is more of Indian IIM type question.

Nik11 · Answer

Is right this approach, isn't it?

Posted from my mobile device

carouselambra · Answer

Thank you and Yashika!

Fdambro294 · Answer

Not GMAT material but I’ll bite.

Since the Base of the NUM’s exponential term and the divisor are co-prime ——-> can use Euler’s Theorem

The given division can be re-written as:

(3 / 23)Rof ^ [ (1,000) / (Euler no. of 23)]Rof

(3) ^ [ (1,000) / (22) ]Rof

Since 1,000 divided by 22 leaves a remainder of 10

(3)^10 = excess remainder

Since remainder must be < less than < divisor, we need to divide through by 23 again

(3)^10 / 23 ———-> yields a remainder of ?

(3)^3 * (3)^3 * (3)^3 * 3 = (27) (27) (27) (3)

Dividing each factor by the divisor of 23 and multiplying the remainders:

(Rem of 4) * (Rem of 4) * (Rem of 4) * (Rem of 3) = excess remainder

(64)(3) = excess remainder

Dividing each factor by 23 again:

(64/23) ——> Rem of (-)5

*

(3/23) ———> Rem of + 3

Negative remainder of (-5) * (3) = -15

-15 + (Divisor of 23) = 8

8 is the answer

Posted from my mobile device

bumpbot · Answer

Automated notice from GMAT Club BumpBot: 

A member just gave Kudos to this thread, showing it’s still useful. I’ve bumped it to the top so more people can benefit. Feel free to add your own questions or solutions.

 This post was generated automatically.

What is the remainder when 49^1000 is divided by 23?

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 49^1000 is divided by 23?

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