Hello, pranay!

I have a very primtive approach . . .

Is there any trick to find the remainder when a number is raised to a large power

and we need to find the mod of it?

Example: .What is: 1086^1183 (mod 47) ?

Note that: .1086 ≡ 5 (mod 47)

We have: .5^{1183} (mod 47)

Theorem.Ifpis a prime, then: .a^{p-1} ≡ 1 (mod p)

. . Hence: .5^{46} ≡ 1 (mod 47)

Since 1183 .= .46(25) + 33, .

. . 5^{1183} .= .5^{46(25) + 33} .= .(5^46)^25 * 5^33

. . . . . . . . . . ≡ .1^25 * 5^33 (mod 47) .≡ .5^33 (mod 47)

This is the primitive part.

We can evaluate 5^33 by cranking out certain powers of 5 (mod 47).

. . 5^1 .≡ . 5 (mod 47)

. . 5^2 .≡ .25

. . 5^4 .≡ .14

. . 5^8 .≡ . 8

- 5^16 .≡ .17

- 5^32 .≡ . 7

Hence: .5^33 .= .(5^32)(5^1) .≡ .(7)(5) (mod 47) .≡ .35 (mod 47)

Therefore: . 1086^1183 . ≡ . 35 (mod 47)