Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

I'm really stuck on this one.

share|improve this question
5  
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
3  
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
add comment

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

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

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|improve this answer
add comment

Your Answer

 
discard

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.