Question

What is the remainder of (16937^30)/31 ?

Answer 1

Heya...

6937 & 31 are coprimes so we can use Euler's theorem to find 16937^30 mod 31.
By Euler's totient function,
Phi (31) = 30.
For a prime p, phi (p) = p-1.
By Euler's theorem,
16937^[phi (31)] mod 31 = 1.
So, 16937^30 mod 31 = 1.