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.
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)