3^100,000 mod 53 using Fermat's Little Theorem

Solution:
`3^(100000) ("mod "53)`



Step-1: Identify conditions :
`p=53` is prime.

`a=3` is not divisible by `p=53`.

So, Apply the theorem
`3^(53-1)-=1 ("mod "53)`

`3^(52)-=1 ("mod "53)`

Step-2: Reduce the exponent `100000`

`100000-:52=1923` with a remainder of `4`

i.e., `100000=52xx1923+4`

Step-3: Simplify
We have
`3^(52)-=1 ("mod "53)`

Taking power `1923` on both sides

`(3^(52))^1923-=1^1923 ("mod "53)`

`3^((52xx1923))-=1 ("mod "53)`

Multiply by `3^4` on both sides

`3^((52xx1923))xx3^4-=1xx3^4 ("mod "53)`

`3^((52xx1923)+4)-=3^4 ("mod "53)`

`3^(100000)-=81 ("mod "53)`

`3^(100000)-=28 ("mod "53)`

`:.` The remainder is `28` when you divide `3^(100000)` by `53`

---

---