Question

Given m = 2n + 1, what integer between 0 and m is the inverse of 2 modulo m? Answer in terms of n.

Answer 1

Let's take this step by step. Given that \(m=2n+1\), we see that \(m\) has to be an odd integer. So, to start seeing a pattern, let \(m=3=2\cdot 1+1\). Then it follows that \(2^{-1}\equiv 2\pmod{3}\) since \(2\cdot 2 = 4 \equiv 1\pmod{3}\). So in this case, the inverse of 2 is itself. Now, if \(m=5=2\cdot 2+1\), then \(2^{-1}\equiv 3\pmod{5}\). If \(m=7 =2\cdot 3+1\), then \(2^{-1}=4\pmod{7}\). At this point, we should be able to observe a pattern; thus, if \(m=2n+1\), then \(2^{-1}\equiv \underline{\phantom{XX}}\pmod{m}\).

I hope this is enough to help you solve the problem. :-)

Answer 2

Thanks