# $2009^{2007} \equiv x \pmod {2012}$ Dealing with mods of fractions?

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

## 2 Answers

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.

• 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? – John Doe May 31 '15 at 14:26
• I just calculated it for you. In general, you could use the extended Euclidian algorithm. – wythagoras May 31 '15 at 14:30

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

• This doesn't make much sense to me. Can you clarify this? What are $n,k$? – wythagoras May 31 '15 at 15:01
• @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$ – Bill Dubuque May 31 '15 at 15:04
• Your answer is not correct. It is not (n+1)/3=(2012+1)/3=2013/3=671. – wythagoras May 31 '15 at 15:07
• @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.\ \$ – Bill Dubuque May 31 '15 at 15:10
• I would never use such notation, but I see that it is correct, so (+1). – wythagoras May 31 '15 at 15:11