Find the smallest positive integer $X$ such that $478^{870} \equiv X \ (\text{mod} \ 273)$ Appreciate if one could advise if my solution is correct. Here is my attempt of the problem: 
Since $(273, 478) =1,$ by Euler's theorem, $478^{\phi(273)}=478^{144} \equiv 1 \ \ (\text{mod} \ 273) \implies 478^{864} \equiv 1 \ \ (\text{mod} \ 273).$ 
Next, $478^{2} \equiv 22 \ \ (\text{mod} \ 39) \implies 478^{6} \equiv 22^{3} \equiv 1 \  \ (\text{mod} \ 39)$ and $478^{\phi(7)} = 478^{6} \equiv 1 \ \ (\text{mod} \ 7) $
Hence, $478^{6} \equiv 1 \ \ (\text{mod} \ 273)$ and $478^{864+6}= 478^{870} \equiv 1 \ \ (\text{mod} \ 273)$
 A: Euler's Theorem with $\phi(273)=144$ gives $478^{870}\equiv(-68)^{870}\equiv68^6\equiv4624^3\equiv-17^3\equiv1$.
A: Your idea to use Chinese Remainder Theorem is good, but we can apply it more cleanly.  We have $273 = 3\cdot 7\cdot 13,$ so we localize at each prime:
$$X\equiv 478^{870} \equiv 1^{870} \equiv 1 \pmod{3}$$
$$X\equiv 478^{870} \equiv 2^{6\cdot 145} \equiv 1 \pmod{7}$$
$$X\equiv 478^{870} \equiv (-3)^{6+12\cdot 72} \equiv 3^6 \equiv 27^2 \equiv 1^2 \equiv 1 \pmod{13}$$
By Chinese Remainder Theorem $X\equiv 1 \pmod{273}.$
A: Recall Carmichael's theorem: $a^{\lambda(m)} \equiv 1 \bmod m$ for all $a$ coprime with $m$.
Now $\lambda(273)=lcm(\phi(3),\phi(7),\phi(13))=lcm(2,6,12)=12$ and $870 \equiv 6 \bmod 12$.
Therefore
$
478^{870} \equiv 205^{6} \equiv (-68)^{6} \equiv 4^6 \cdot 17^6 \equiv 1 \bmod 273
$.
A: Hint $\ \ \begin{align}478\ \  &\equiv 1,2,-3\,\bmod 3,7,13\\ \Rightarrow\, 478^{\large\color{#0b0}3}&\equiv 1,1,\color{#c00}{{-}1}\,  \bmod 3,7,13\end{align}\ $ and $\ \ \color{#c00}2\cdot \color{#0b0}{3\ }\mid 870$
Remark $ $ The idea is that $\,6 = \color{#c00}2\cdot \color{#0b0}{3\ }$ is a common multiple of the orders of $a=478$ mod $\,3,7,13$  therefore $\,a^6\equiv 1$ for each modulus, hence also modulo their lcm = product $= 273$, i.e. $\,3,7,13\mid a^6-1\,\Rightarrow\, 273\mid a^6-1,\,$  This is the idea behind the Carmichael approach in lhf's answer, but it uses Euler's $\,\phi(m)\,$ as its multiple of the order $\!\bmod m$
