Shuvam C. answered • 05/23/22
CS Major at University of Michigan
Fermat's Little Theorem states that given a prime number p and and integer a, then a^p ≡ a (mod p). This also allows us to say that if a isn't divisible by p, then a^(p-1) ≡ 1 (mod p). (In the case that a is divisible by p, then a raised to any power is equivalent to 0 modulus p, but that isn't very useful)
The first example you give is actually not applicable to Fermat's Little Theorem since 1234567 isn't prime and the modulus number must be prime. The second example would work but it might be a bit confusing or tedious to use such a large base, so I'll choose some smaller numbers to demonstrate with and I hope you'll be able to follow my process and apply it to any number you want.
Say we want to calculate 2^{1,000,000} mod 47. By Fermat's Little Theorem, 2^46 ≡ 1 (mod 47). Now, we can see that 1000000 / 46 = 21739 with a remainder of 6. Raise both sides of the equation to the power of 21739 to get (2^46)^21739 ≡ 1^21739 (mod 47) so 2^999994 ≡ 1 (mod 47). Now multiply both sides by 2^6 to get 2^1000000 ≡ 2^6 (mod 47). 2^6 = 64 and 64 ≡ 17 (mod 47).
So, our final answer is 2^1000000 ≡ 17 (mod 47).
