6
$\begingroup$

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?

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

You had the solution and broke it :)

At

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.