Is the modular multiplicative inverse $2^{-1}$ a special case in $\mathbb{Z}_p$ for prime $p > 2$?

113 Views Asked by At

I'm a non-mathematician but I've been reading up on number theory as part of furthering my understanding of cryptography, and I've been focusing particularly on modular arithmetic in $\mathbb{Z}_p$ for $p > 2$, where $p$ is prime.

I'm mostly understanding it, but I came across the following example:

$$2^{-1}\textrm{ in }\mathbb{Z}_p\textrm{ is }\frac{p+1}{2}$$

This appears to work, and I can't find any counterexamples, but I'm struggling to understand whether it's a special case for $x=2$ or part of a more general rule, or where this identity was even derived from.

Further confusing me is that $x^{-1}=x^{p-2}$ in $\mathbb{Z}_p$ for $x \neq 0$, which would imply that $2^{p-2}\equiv\frac{p+1}{2}$ in $\mathbb{Z}_p$ for all prime $p > 2$, and I can't see how this arises.

How does this work?

1

There are 1 best solutions below

0
On BEST ANSWER

For all odd $n>2$ (in particular for all prime $n>2$),

$2\times\dfrac{n+1}2=n+1\equiv1\pmod n$,

so $2^{-1}\equiv\dfrac{n+1}2\pmod n$.

You are correct that, for prime $n>2$, $2^{n-2}\equiv2^{-1}$, so $2^{n-2}\equiv \dfrac{n+1}2\pmod n$.

This is essentially $2^{n-1}\equiv n+1\equiv 1\pmod n.$