2
$\begingroup$

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

I'm really stuck on this one.

  • 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...2010-10-27
  • 3
    When p=3, x=2. p=5,x=3. p=11,x=6. p=17,x=9. Do you see any pattern?2010-10-27

2 Answers 2

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

  • 2
    You do realize he asked this question last October :)2011-06-29
  • 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. :)2011-06-30
  • 0
    $(p+1)/2$ is a better answer because it depends only on $p$.2011-06-30
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.