Find the remainder when 3200 is divided by 45SolutionWe cann

Find the remainder when 3^200 is divided by 45

Solution

We cannot compute 3^200 in anywhere near the time allotted, so we should look for a pattern in much simpler problems that we can scale up to 3^200.

Lets devide power of 3 which is 200

3²⁰⁰ = (3⁴)⁵⁰

= 81⁵⁰

= (45+36)⁵⁰

   = 45K +36⁵⁰   ................K is multiple for 45

Now consider only 36⁵⁰

36⁵⁰= (36²)²⁵

= (1296)²⁵

= (45*28 +36)²⁵

= 45K + 36²⁵

Now for 36²⁵

36²⁵ = (6⁵)¹⁰

= (7740 + 36)¹⁰

= 45K + 36¹⁰

36¹⁰ = 6²⁰

= (7740 +36)⁴

= 45K + 36⁴

36⁴ = 45K +36

So remainder for 3²⁰⁰ divided by 45 is equal 36.