# Find the remainder of $7^{2002}$ divided by 101.

This is what I have so far: Since 101 is a prime and does not divide 7, we can apply Fermat's Little Theorem to see that $$7^{100} \equiv 1 \ (mod \ 101)$$ We can then reduce $7^{2002}$ to $7^{2} (7^{100})^{20} \equiv 7^{2}(1)^{20} \ (mod \ 101)$ which is where I'm stuck at. $7^2=49 \equiv 150 \ (mod \ 101)$. How do I reduce $7^2$ in a way that is constructive towards my solution since $(mod \ 101)$ is such a large modulus to operate in?

• $7^2 \pmod{101} \equiv 49\pmod{101}$ You did the hard part... :) – apnorton Nov 3 '13 at 20:22
• 49 is already as reduced as it's going to get. – vadim123 Nov 3 '13 at 20:22
• Don't you already have the answer ($7^2 \equiv 49 (\mod 101)$)? – José Siqueira Nov 3 '13 at 20:22
• $49$ is enough for the answer. You won't need $150$. – CODE Nov 3 '13 at 20:23
• When you divide by $101$, your remainder should be some non-negative integer less than $101$. $49$ is fine. – Ben Grossmann Nov 3 '13 at 20:39

$$7^{2002} \equiv 49\pmod {101} \,,$$
you are done, the remainder must be $49$. Indeed, if you denote the remainder by $r$ then $0 \leq r \leq 100$ and
$$r \equiv 49 \pmod{101} \,.$$
This means that $101|r-49$, and since $-49 \leq r-49 < 52$ you get $r-49=0$.