2
$\begingroup$

Solve $2x \equiv 1 \pmod{p}$ where $p$ is an odd prime.

I'm really stuck on this one.

  • 3
    When p=3, x=2. p=5,x=3. p=11,x=6. p=17,x=9. Do you see any pattern?2010-10-27

2 Answers 2

2

If $p$ is odd, it will be in the form $2n+1$. So $2(n+1)=2n+2=2n+1+1=p+1$ so it is 1 (mod p).

So $n+1$ is the inverse of $2$ mod $p$.

  • 0
    $(p+1)/2$ is a better answer because it depends only on $p$.2011-06-30
1

The trick proposed by Qiaochu in the comment is actually a very special case of Gauss's algorithm for computing inverses $\rm\:(mod\ p)\:$ for $\rm\:p\:$ prime. This special case of the Euclidean algorithm works simply by repeatedly scaling the fraction so to reduce the denominator until it reaches one. See my linked post for further details.