Find the smallest positive integer $X$ such that $478^{870} \equiv X \ (\text{mod} \ 273)$

Question

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)$

Answer 1

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}.$

Answer 2

Euler's Theorem with $\phi(273)=144$ gives $478^{870}\equiv(-68)^{870}\equiv68^6\equiv4624^3\equiv-17^3\equiv1$.

Answer 3

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 $.

Answer 4

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$