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

\(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

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

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 .

Bunuel chetan2u VeritasKarishma
Could you please share your approach
_________________

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

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
_________________

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?
_________________

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
_________________

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

Is right this approach, isn't it?

Posted from my mobile device

Thank you and Yashika!

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

Hello from the GMAT Club BumpBot!

Thanks to another GMAT Club member, I have just discovered this valuable topic, yet it had no discussion for over a year. I am now bumping it up - doing my job. I think you may find it valuable (esp those replies with Kudos).

Want to see all other topics I dig out? Follow me (click follow button on profile). You will receive a summary of all topics I bump in your profile area as well as via email.
_________________