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

Question

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

score 2 · Answer 1 · answered Jun 29 '11 at 20:28

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

answered Jun 29 '11 at 20:28

Thomas Santoli

216

2

You do realize he asked this question last October :) – Zarrax Jun 29 '11 at 21:00
2

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

score 1 · Answer 2 · edited Jun 12 '20 at 10:38

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.

edited Jun 12 '20 at 10:38

Community

1

answered Oct 27 '10 at 17:15

Bill Dubuque

272,048

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

2 Answers2