What is the remainder when 2^99 is divided by 99?

Bunuel
VeritasKarishma

Thanks for your insights on the post.

Wanted to check if we can split the terms and find the individual remainders via the multiplicative theorem. Can you please let me know if that would be a correct approach.

For example -

We are asked to find the Remainder of (\(\frac{ 2^ {99} }{ 99}\))

(\(\frac{ 2^ {99} }{ 99}\)) = (\(\frac{ 2^ {99} }{33 }\)) * (\(\frac{ 1 }{ 3}\))

Therefore,

Remainder (\(\frac{ 2^ {99} }{ 99}\)) = Remainder (\(\frac{ 2^ {99} }{33 }\)) * Remainder (\(\frac{ 1 }{ 3}\))

Step 01 - Remainder (\(\frac{ 2^ {99} }{33 }\))

= Remainder [ (\(\frac{ 2^ {95} }{33 }\)) * (\(\frac{ 2^ {4} }{33 }\)) ]

= Remainder [ (\(\frac{ (2^ {5}) ^ {19} }{33 }\)) * (\(\frac{ 2^ {4} }{33 }\)) ]

= (\(\frac{ (-1) ^ {19} }{33 }\)) * 16

= (\(\frac{ (-1) ^ {19} }{33 }\)) * 16

= -16

Now we cannot have -16, therefore the remainder = 33 - 16 = 17

Remainder (\(\frac{ 2^ {99} }{ 33}\)) = 17

Step 02 - Remainder (\(\frac{ 1 }{3 }\))

= 1

Step 03 - Multiply both the remainders

= 17 * 1 = 17