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?

An alternate solution using the Chinese Remainder Theorem.
First off, $2, 3, 5$ and 7 are pairwise relatively prime thus we know the following system of congruences has a unique solution modulo $2\times3\times5\times7=210$.
\begin{cases} x \equiv 4  \pmod {5} \\  x \equiv 0  \pmod {2} \\  x \equiv 1  \pmod {7} \\  x \equiv 1  \pmod {3} \end{cases}
Start with the first congruence and turn it into an equation
$x\equiv 4 \pmod 5$
$\iff x = 5k + 4$ (by definition of congruence)
Plugging this in the second congruence:
$5k+4 \equiv 0\pmod {2}$
$\iff$
$5k \equiv 0 \pmod {2}$
To get rid of the 5 on the left hand side, multiply both sides of the congruence by the inverse of 5 mod 2 which is 1 by the extended euclidean algorithm. Thus:
$k \equiv 0 \pmod {2}$
$\iff$
$k = 2k'$
Which means $x = 5k + 4 = 5(2k') + 4 = 10k' + 4$
Now replacing in the third equation:
$10k' + 4 \equiv 1 \pmod {7}$
$\iff$
$10k' \equiv 4 \pmod {7}$
Multiply both sides by 5, the inverse of 10 mod 7.
$k' \equiv 6 \pmod {7}$
$\iff$
$k' = 7k'' + 6$
Which means $x = 10k' +4 = 10(7k'' + 6) + 4 = 70k'' + 64$
Finally replacing in the last equation:
$70k'' + 64 \equiv 1 \pmod {3}$
$\iff$
$70k' \equiv 0 \pmod {3}$
Multiply both sides by 1, the inverse of 70 mod 3.
$k' \equiv 0 \pmod {3}$
$\iff$
$k'' = 3k'''$
Thus
$x = 70k'' + 64 = 70(3k''') + 64 = 210k''' + 64$
$\iff$
$x \equiv 64 \pmod {210}$
