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?
 A: The quick solution to the Chinese Remainder Theorem exercise is to find integers $w,x,y,z$ such that $105w + 70x+42y + 30z=1$. Then:
$$x\equiv 0\cdot 105w + 1\cdot 70x + 4\cdot 42y + 1\cdot 30z\pmod {210}$$
A: 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.
A: 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.
A: 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}$
A: Here is a solution that does not make use of Fermat's Little Theorem.

The Algorithm:


*

*Input: $x=8,e=38,n=210$

*Output: $y=1$

*Repeat until $e=0$:


*

*If $e\equiv1\pmod2$ then set $y=yx\bmod{n}$

*Set $x=x^2\bmod{n}$

*Set $e=\left\lfloor\frac{e}{2}\right\rfloor$
C Implementation:
int PowMod(int x,int e,int n)
{
    int y = 1;
    while (e > 0)
    {
        if (e & 1)
            y = (y*x)%n;
        x = (x*x)%n;
        e >>= 1;
    }
    return y;
}

int result = PowMod(8,38,210); // 64

Intermediate Output:
   x   |   e   |   y
-------|-------|-------
    8  |   38  |    1
   64  |   19  |    1
  106  |    9  |   64
  106  |    4  |   64
  106  |    2  |   64
  106  |    1  |   64
  106  |    0  |   64


Please note that the complexity is $O(\log_2e)$, resulting in $\lceil\log_238\rceil=6$ iterations.
A: just apply Chinese remainder theorem (See Burton)
A: Notice
$$8^5=210\cdot{156}+8$$
So
$$8^5\equiv8\pmod{210}--(1)$$
Also
$$8^2\equiv64\pmod{210}--(2)$$
By (1),(2) we have
$$8^7\equiv8\cdot{64}\equiv92\pmod{210}$$
Futhermore
$$8^{35}=(8^5)^7\equiv8^7\equiv92\pmod{210}--(3)$$
Morever
$$8^3\equiv512\equiv92\pmod{210}--(4)$$
Therefore, by (3),(4),
$$8^{38}=8^{35}\cdot8^3\equiv92^2\equiv64\pmod{210}$$
A: we have $$64\equiv 8^{38}\mod 210$$
