# Solving $2x \equiv 1 \pmod{p}$ where $p$ is an odd prime

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

I'm really stuck on this one.

-
In congruences, you can replace either side with that same thing plus a multiple of p. So you can replace 1 with, say, p+1... –  Qiaochu Yuan Oct 27 '10 at 16:48
When p=3, x=2. p=5,x=3. p=11,x=6. p=17,x=9. Do you see any pattern? –  Aryabhata Oct 27 '10 at 17:11

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$.
$(p+1)/2$ is a better answer because it depends only on $p$. –  lhf Jun 30 '11 at 0:55
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.