Calculate $442^{260} \bmod{616}$ using Euler's theorem 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. 
 A: 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$$
A: Since $\gcd(442,77)=1$ and $\varphi(77)=\varphi(7)\varphi(11)=6\cdot10=60$ we have $442^{60}\equiv1\pmod{77}$ by Euler; Hence $442^{240}=\left(442^{60}\right)^4\equiv1\pmod{77}$.
Now $221\equiv-10\pmod{77}$
$\implies\ 221^3\equiv-1000\equiv1\pmod{77}\ (\because1001=13\cdot77)$;
$\therefore\ 221^{20}\equiv221^2\equiv100\equiv23\pmod{77}$.
Also $2^8=256\equiv25\pmod{77}$
$\implies\ 2^{16}\equiv625\equiv9\pmod{77}$
$\implies\ 2^{17}\equiv18\pmod{77}$. Hence
$$2^{17}\cdot221^{20}\cdot442^{240}\equiv18\cdot23\cdot1=414\equiv29\pmod{77}$$
and multiplying through by $2^3=8$ gives
$$442^{260}\equiv8\cdot29\ =\ 232\pmod{8\cdot77=616}$$
A: Use the Chinese remainder theorem: $\;616=8\times7\times 11$, so
\begin{align}\mathbf Z/616\mathbf Z&\simeq\mathbf Z/8\mathbf Z\times\mathbf Z/7\mathbf Z\times\mathbf Z11\mathbf Z\\
442&\mapsto ([442]_8,[442]_7,[442]_{11})=(2,1,2)\\
442^{260}&\mapsto (2^{260},1^{260},2^{260})=(0,1,1)
\end{align}
(We used Lil' Fermat for $2^{260}\bmod11$).
There remains to solve the system of congruences:
$$x\equiv\begin{cases}0\mod8,\\1\mod 7,\\1\mod11.\end{cases}$$
We'll begin with the last two  congruences. Clearly the solution is $\;x\equiv1\mod 77$.
Next we solve the system $\;x\equiv\begin{cases}0\mod8,\\1\mod 77.\end{cases}$
We need a Bézout's relation between $8$ and $77$. The extended Euclidean algorithm instantly yields
$$29\times 8-3\times77=1,$$
so the solution is
$$x\equiv 1\times29\times8-0\times3\times77=\color{red}{232}\mod616.$$
