Euler's Theorem Discrete Mathematics Exponential Modulo

Question

I m trying to solve the answer for this question using Eulers Theorem to calculate the exponential modulo.

3^2000 (mod 12).   Cannot apply Euler's theorem since gcd(3,12) is not equal to 1 .

Is there any way to convert this to another form where gcd() is equal to one and can apply Euler's Theorem?

Answer 1

$3^{2000}\equiv0\pmod 3$ and $3^2\equiv1\pmod4$,

so $3^{2000}\equiv9\pmod{12}$ by the Chinese remainder theorem.

Answer 2

You can extend Euler's theorem by noting a couple of things:

• You can still use it with the coprime part of the modulus as the gcd condition then holds.
• Euler totient is multiplicative on coprime parts, meaning you can Still use the Euler totient of the original modulus ( though the resulting exponent is likely still big)
• If the exponent on the base, is bigger than the exponents on the primes in their gcd, you can can say it's 0 mod that part of the modulus.
• If the exponent were really large ( say 78 digits plus if you want to wait that long) you could write in base one more than the Euler totient to decrease it.
• You can piece things together with Chinese remainder theorem.

In this case we have $3^{2000}\equiv 0\bmod 3$ and $3^{2000}\equiv 3^{0}\equiv 1\bmod 4$ which means by CRT that it's 9 mod 12.