Find the integer x: $x \equiv 8^{38} \pmod {210}$ Find the integer x: $x \equiv 8^{38} \pmod {210}$
I broke the top into prime mods:
$$x \equiv 8^{38} \pmod 3$$
$$x \equiv 8^{38} \pmod {70}$$
But $x \equiv 8^{38} \pmod {70}$ can be broken up more:
$$x \equiv 8^{38} \pmod 7$$
$$x \equiv 8^{38} \pmod {10}$$
But $x \equiv 8^{38} \pmod {10}$ can be broken up more:
$$x \equiv 8^{38} \pmod 5$$
$$x \equiv 8^{38} \pmod 2$$
In the end,I am left with:
$$x \equiv 8^{38} \pmod 5$$
$$x \equiv 8^{38} \pmod 2$$
$$x \equiv 8^{38} \pmod 7$$
$$x \equiv 8^{38} \pmod 3$$
Solving each using fermat's theorem:


*

*$x \equiv 8^{38}\equiv8^{4(9)}8^2\equiv64 \equiv 4 \pmod 5$

*$x \equiv 8^{38} \equiv 8^{1(38)}\equiv 1 \pmod 2$

*$x \equiv 8^{38} \equiv 8^{6(6)}8^2\equiv 64 \equiv 1 \pmod 7$

*$x \equiv 8^{38} \equiv 8^{2(19)}\equiv 1 \pmod 3$
So now, I have four congruences. How can i solve them?

By Fermat: $\,\color{#0a0}{2,4,6}\mid\color{#c00}{12}\,\Rightarrow {\rm mod}\ \color{#0a0}{3,5,7}\!:\ 8^{\color{#c00}{12}}\equiv 1,\,$ so $\, 8^{38}\equiv 8^2(8^{\color{#c00}{12}})^3\equiv 8^2\,$ and $ $ mod $\,2$

Remark $\ $ It generalizes. Above is special case $\,\varphi = 36,\,k=2\,$ of the following generalization of Fermat and Euler's theorem $\rm\color{blue}{(E)},\,$ which clearly extends to any number of primes. 
Theorem $\ \ \, n^{\large \varphi+k}\equiv n^{\large k}\pmod{p^i q^j}\ \ $ if $\ p\ne q\,$ are prime, $ \ \color{#0a0}{\varphi(p^i),\varphi(q^j)\mid \varphi},\ $  $\, i,j \le k $ 
${\bf Proof}\,\ \ p\nmid n\,\Rightarrow\, {\rm mod\ }p^i\!:\  n^{ \varphi}\equiv 1\,\Rightarrow\, n^{\varphi+k}\equiv n^k,\ $ by $\,\  n^{\large \color{#0a0}\varphi} = (n^{\color{#0a0}{\large \varphi(p^{ i})}})^{\large \color{#0a0}\ell}\overset{\color{blue}{\rm (E)}}\equiv 1^{\large \ell}\equiv 1$ 
$\qquad\quad\ \ \color{#c00}{p\mid n}\,\Rightarrow\, {\rm mod\ }p^i\!:\  n^k\equiv 0\,\equiv\, n^{\varphi+k}\ $ by $\ n^k = n^{k-i} \color{#c00}n^i = n^{k-i} (\color{#c00}{mp})^i$ and $\,k\ge i$
So $\ p^i\!\mid n^{\varphi+k}\!-n^k.\,$ By symmetry $\,q^j$ divides it too, so their lcm $ = p^iq^j\,$ divides it too. $\ $ QED
See also Carmichael's Lambda function, a generalization of Euler's phi function.
