# 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.

• $6^{2006}\equiv 36^{1003}\equiv 1^{1003}\equiv 1\pmod{35}$. Commented May 22, 2016 at 13:53
• Your reasoning is wrong, for example $136\equiv 31 \mod 35$. Commented May 22, 2016 at 13:55
• It is not true that the last two digits of $6^{2006}$ are $36$, they are $56$, but that does not help you with $6^{2006} \pmod {35}$ Commented May 22, 2016 at 13:57
• The last two digits of $6^{2006}$ are $56$, not $36$. wolframalpha.com/input/?i=6%5E(2006)+mod+100 Commented May 22, 2016 at 13:57
• For this type of problem in general, see How do I compute $a^b\,\bmod c$ by hand? Commented May 22, 2016 at 23:53

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}$$

• The last two digits of $6^{2006}$ are $56$, not $36$. wolframalpha.com/input/?i=6%5E(2006)+mod+100 Commented May 22, 2016 at 13:57
• @user236182: And even if they were $36$, it still wouldn't imply that the remainder of the number divided by $35$ is $1$. Commented May 22, 2016 at 14:00

HINT :

$6^{2006}=36^{1003} \equiv 1^{1003}$ (mod 35)

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.