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?

You made a small slip up when working $\bmod 2$, this is because $0^n$ is always congruent to $0$ no matter what congruence you are working with . I repeat this step once again.
$8^{38}\equiv 3^{38}\equiv3^{9\cdot4}3^{2}\equiv(3^{4})^{9}3^2\equiv1^9\cdot3^2\equiv9\equiv 4\bmod 5$
$8^{38}\equiv0 \bmod 2$ since it is clearly even.
$8^{38}\equiv(1)^{38}\equiv 1\bmod 7$
$8^{38}\equiv(-1)^{38}\equiv 1 \bmod 3$
So you have the following system of equations:
$x\equiv4 \bmod 5$
$x\equiv 0 \bmod 2$
$x\equiv 1 \bmod 7$
$x\equiv 1 \bmod 3$
There are general ways to solve this, but it is possible to solve it step by step using basic substitutions.
We start by writing $x=2k$ since $x\equiv 0 \bmod 2$
We now have $2k\equiv 1 \bmod 3$. Multiplying by two we get $4k\equiv 2\bmod 3$ since $4\equiv 1$ we have $k\equiv 2 \bmod 3$ so $k=3j+2$ and so $x=2(3j+2)=6j+4$
We have $6j+4\equiv 1 \bmod 7$ so $6j\equiv-3\equiv 4 \bmod 7$. Multiplying by $6$ we get $36j\equiv 24\equiv 3 \bmod 7$ Since $36\equiv 1 \bmod 7$ we have $j\equiv 3 \bmod 7$. So $x=6(7l+3)+4=42l+22$
We have $42l+22\equiv 4 \bmod 5$ from here $42l\equiv -18\equiv2 \bmod 5$ Since $42\equiv 2 \bmod 5$ we have $2l\equiv 2 \bmod 5$ so $l\equiv 1 \bmod 5$. So $l=5s+1$ and $x=42(5s+1)+22=210s+64$. So $8^{38}\equiv 64\bmod 210$

Second solution: Instead of using Fermat's theorem use Carmichael's theorem which says that if $a$ and $n$ are relatively prime then $a^{\lambda(n)}\equiv 1 \bmod n$. Using this and the fact that $\lambda(105)=12$
we get $8^{38}\equiv 8^{36}a^2\equiv (8^{12})^8a^2\equiv 1^38^2\equiv 8^2\equiv64\bmod 105$
Using this and the fact that $8^{38}$ is even we get $8^{38}\equiv 64\bmod 210$

Note: The theorem that tells us that we can separate congruences into congruences mod the power of primes dividing the number is called the Chinese Remainder theorem. This method assures us that the solution exists and that it is unique.
