3
$\begingroup$

$$2009^{2007} \equiv x \pmod {2012}$$

Now I used Fermat's theorem in this case and got

$2009^{1004} \equiv 1$

or further

$2009^{2008} \equiv 1$

Now this overshoots the exponent I need, so after dividing

$2009^{2007} \equiv \frac 1{2009}$

To get a smaller number, I guess you could say

$-3^{2007} \equiv \frac 1{-3}$

How do I get the actual remainder from this? I saw some questions related to this but I didn't see a clear cut way to solve this.

Additionally, are there other, simpler ways to solve this?

$\endgroup$
2
$\begingroup$

You want the multiplicative inverse of $-3 \mod 2012$.

Try a bit, to get $-3\cdot1341 \equiv 1 \mod 2012$

Therefore the multiplicative inverse is 1341.

$\endgroup$
  • $\begingroup$ I see. Since this was a multiple choice question, I could just check all the possible answers, so I got $1341$. How would I go around this if it wasn't given the possible answers? $\endgroup$ – John Doe May 31 '15 at 14:26
  • $\begingroup$ I just calculated it for you. In general, you could use the extended Euclidian algorithm. $\endgroup$ – wythagoras May 31 '15 at 14:30
2
$\begingroup$

${\rm mod}\ n = 3k\!-\!1\!:\,\ n\equiv0\,\Rightarrow\,3k\equiv 1\,\Rightarrow\, 1/3\equiv k\equiv (n\!+\!1)/3$

$\endgroup$
  • $\begingroup$ This doesn't make much sense to me. Can you clarify this? What are $n,k$? $\endgroup$ – wythagoras May 31 '15 at 15:01
  • $\begingroup$ @wythagoras $\,n\,$ is any integer of the form $\,3k\!-\!1,\,$ e.g. $\,n=2012\,$ in the OP. Similarly for $\,n = 3k\!+\!1.\,$ So we have a general formula to compute $\,1/3\,$ modulo any modulu $\,n\,$ coprime to $3$ $\endgroup$ – Bill Dubuque May 31 '15 at 15:04
  • $\begingroup$ Your answer is not correct. It is not (n+1)/3=(2012+1)/3=2013/3=671. $\endgroup$ – wythagoras May 31 '15 at 15:07
  • $\begingroup$ @wythagoras It is the correct value of $\,1/3.\,$ If you seek the value of $\,-1/3\,$ then of course you need only negate the value of $\,1/3.\ \ $ $\endgroup$ – Bill Dubuque May 31 '15 at 15:10
  • $\begingroup$ I would never use such notation, but I see that it is correct, so (+1). $\endgroup$ – wythagoras May 31 '15 at 15:11

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.