Find the remainder when a large number is divided by 35. I don't know why I am wrong with this problem. Here is what I did: The last two digit of $6^{2006}$ is 36. So the answer should be 1.  

Find the remainder when $6^{2006}$ is divided by 35.

 A: HINT :
$6^{2006}=36^{1003} \equiv 1^{1003} $ (mod 35)
A: Here is another approach. For solving problems$\pmod{N}$, we can try finding the prime factors of $N$, then solving the problem modulo each of those factors. Sometimes this is easier than directly solving $\pmod{N}$. 
Then something called the Chinese Remainder Theorem lets us combine the results for each factor to produce the result for $N$.
In this case the prime factors of $35$ are $5$ and $7$. Since $6 \equiv 1 \pmod{5}$ and $6 \equiv -1 \pmod{7}$, we see straightaway that:


*

*$6^{2006} \equiv 1\pmod 5$ 

*$6^{2006} \equiv 1 \pmod 7$  , since $2006$ is even
The Chinese Remainder Theorem tells us that, given congruences $N \equiv a \pmod{p}$ and $N \equiv b \pmod {q}$ , then there is a unique $x$ such that $N \equiv x \pmod{pq}$, and it is the same $x$ for all $N$ (and this generalizes to multiple factors).
In the general case you may have to follow an algorithm or use brute force to find $x$. In this case it is right in front of us: letting $N = 1$ satisfies our two congruences. So $1 \pmod{35}$ is the answer we are looking for.
A: Not sure how you've figured "The last two digits of $6^{2006}$ are $36$", but here's my approach:
$$6^2\equiv36\equiv1\pmod{35}\implies6^{2006}\equiv(6^2)^{1003}\equiv1^{1003}\equiv1\pmod{35}$$
