[Math] Calculate $442^{260} \bmod{616}$ using Euler’s theorem

Question

I'm asked to calculate $442^{260} \bmod{616}$, using Euler's theorem.
But if I am to use Euler's theorem to solve an expression on the form $a^x \bmod{n}$, then $a$ and $n$ needs to be relatively prime. How can I change the expression above so that I'll end up with an $a$ and a $n$ such that $\gcd(a,n) = 1$?
I was thinking about using the Chinese Remainder Theorem to split up the expression, but since the prime factorization of $616$ is $2^3 \cdot 7 \cdot 11$, I'll always end up with an even $n$ in one of the equations.

Answer 1

Break the modulus into its prime power factors: $$442^{260}\equiv a\bmod8$$ $$442^{260}\equiv b\bmod7$$ $$442^{260}\equiv c\bmod11$$ $a$ is obviously zero as $442^{260}=8\cdot221^3\cdot442^{257}$. Since 442 is relatively prime to 7 and 11, Euler's theorem (actually Fermat's little theorem, as 7 and 11 are prime) can be used for $b$ and $c$: $$442^6\equiv1\bmod7$$ $$442^{260}\equiv442^{6\cdot43+2}\equiv442^2\bmod7$$ Since $442\equiv1\bmod7$: $$b\equiv442^2\equiv1^2\equiv1\bmod7$$ Meanwhile: $$442^{10}\equiv1\bmod11$$ $$c\equiv442^{260}\equiv442^{10\cdot26}\equiv1\bmod11$$ Hence we have $$442^{260}\equiv 0\bmod8$$ $$442^{260}\equiv 1\bmod7$$ $$442^{260}\equiv 1\bmod11$$ and using the Chinese remainder theorem we find that $$442^{260}\equiv1+3\cdot77\equiv232\bmod616$$