Finding Inverse of 2 (mod m)

$\begingroup$

Suppose $m$ is odd. What integer between $1$ and $m−1$ equals the inverse of $2 ($mod $m)$?

What I have so far:

Let $n$ be the inverse of $2 ($mod $m)$ where $1<n<m-1$

$\Rightarrow$ $2n\equiv1($mod$m)$

$\Rightarrow$ $2n=1+mk$

since $m$ is odd then $m=2l+1$

$\Rightarrow$ $2n=1+(2l+1)k$

I don't really know how to solve for $n ($mod $m)$ as that would put it within $1<n<m-1$

$\endgroup$ 1

3 Answers

$\begingroup$

Note: Supposing that $m=2\ell+1$ then $2\times (\ell+1)=2\ell+2=m+1$

$\endgroup$ $\begingroup$

We want integer $n=\dfrac{1+mk}2$ between $1$ and $m-1$.

Since $m$ is odd, we need $k$ to be odd, in order for $1+mk$ to be divisible by $2$ so $n$ is an integer.

If $k\ge3$ then $\dfrac{1+mk}2>m-1.$ If $k\le-1$ then $\dfrac{1+mk}2<1.$

So it must be $k=1$ and $n=\dfrac{1+m}2$.

$\endgroup$ $\begingroup$

Hint $\bmod\, 2n\!-\!1\!:\,\ 2n\equiv 1.\ $ More generally see Inverse Reciprocity.

$\endgroup$