By knowing $1 = 1^{-1} \mod p$ for a prime $p$, why can we obtain multiplicative inverse of $i$ for i = 2,...,p-1?

Question

By knowing $1 = 1^{-1} \mod p$ for a prime $p$, why can we obtain multiplicative inverse of $i$ for i = 2,...,p-1?

In particular, why does the following work?

$$ i^{-1} \mod p = p - ((p \mod i)^{-1}\mod p) \cdot (\lfloor \frac{p}{i} \rfloor \mod p) $$

Answer 1

• $p\equiv 0\bmod p$
• $ i(i^{-1})\equiv 1\bmod p$
• $i\lfloor{p\over i}\rfloor\equiv -(p\bmod i)\bmod p$
• $-(p\bmod i)\cdot(p\bmod i)^{-1}\equiv -1\bmod p$

Partially screwed up my original thought. The only reason primes need to be invoked, is because you want the whole range $2,\ldots,p-1$ which is only a modular multiplicative group if $p$ is prime.