# 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

## 2 Answers

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

-
You do realize he asked this question last October :) –  Zarrax Jun 29 '11 at 21:00
@Zarrax: Somebody who might find this answer useful to them might find it next October, i.e., I don't think it matters when someone answers it. Otherwise, the question would not still remain on the site if it rendered useless. :) –  night owl Jun 30 '11 at 0:38
$(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.

-