Modular Arithmetic Combination I'm trying to find the remainder of $\frac{2^{2010}}{35}$. The first two parts of the question asked for the remainder when dividing $2^{2010}$ by 5 and then by 7.
To solve for the first two problems, I used Euler's Theorem:
$$2^{2010}=(2^{3})^{670}$$
Let $a=2$ and $n=5$, then
$$2^{3}\equiv1\pmod 5$$
$$2^{2010}=(2^{3})^{670}\equiv1^{670}\equiv1\pmod5$$
And so I found that the remainder was 1 (please correct me if I made a mistake).
I repeated the process for dividing by 7, and got the same result, the only difference where the exponents which did not effect the result.
How would I combine the two results, $2^{2010}\equiv1\pmod5$ and $2^{2010}\equiv1\pmod7$?
 A: Another way:
$$2^4\equiv1\pmod5,2^3\equiv1\pmod7$$
$$\implies2^{\text{lcm}(3,4)}\equiv1\pmod{\text{lcm}(5,7)}$$
Now lcm$(5,7)=35$ and lcm$(3,4)=12,2010\equiv6\pmod{12}$
$$\implies2^{2010}\equiv2^6\pmod{35}\equiv?$$
A: $$2^{2010} \pmod{35}$$
Note that $2^2 \equiv 4 \equiv -1 \pmod 5$
So $2^{2010} \equiv (2^2)^{1005} \equiv (-1)^{1005} \equiv -1 \pmod 5$
Note that $2^3 \equiv 8 \equiv 1 \pmod 7$
So $2^{2010} \equiv (2^3)^{670} \equiv 1 \pmod 7$
The Chinese remainder theorem states that there is an isomorphism
$$f:\mathbb Z_{35} \to \mathbb Z_5 \times \mathbb Z_7$$
Beyond that, it states that 
$f(n) = (n,n)$ and,
if $f(A) = (1,0)$ and $f(B) = (0,1)$, then $f^{-1}(m,n) = Am + Bn \pmod{35}$
Let $n \equiv 2^{2010} \pmod{35}$. You have found that $n \equiv -1 \pmod 5$ and $n \equiv 1 \pmod 7$.
You what to find the value of $n$ for which $f(n) = (-1,1)$.
First we need to find some number $x$ such that $f(x) = (1,0)$
That means $x \equiv 1 \pmod 5$ and $x \equiv 0 \pmod 7$.
$x \equiv 0 \pmod 7$ means that $x$ is a multiple of $7$. The first few multiples of $7$ are $7, 14, 21$ and we see that 
$$21 \equiv 1 \pmod 5 \ \text{and} \ 21 \equiv 0 \pmod 7$$
So $f(21) = (1, 0)$
Next we need to find $y$ such that $y \equiv 0 \pmod 5 \ \text{and} \ y \equiv 1 \pmod 7$
Thr first few multiples of $5$ are $5, 10, 15$ and we see that
$$15 \equiv 0 \pmod 5 \ \text{and} \ 15 \equiv 1 \pmod 7$$
It follows that $f^{-1}(-1,1) \equiv -1(21) + 1(15) \equiv -6 \equiv 29 \pmod{35}$
So your answer is that the remainder is $29$.
