Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

I'm really stuck on this one.

share|cite|improve this question
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$.

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.