Solve $2x \equiv 1 \pmod{p}$ where $p$ is an odd prime.
I'm really stuck on this one.
Solve $2x \equiv 1 \pmod{p}$ where $p$ is an odd prime.
I'm really stuck on this one.
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$.
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.