1. ## Finding the remainder

Hi , 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?
E.g what is :
1086^1183 mod 47?
Thanks.

2. 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 .If p is 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)

3. Thanks a ton for that