Why 3 is a multiplicative inverse of 7 in modular arithmetic?

928 Views Asked by At

why is 3 a multiplicative inverse of 7 in modular arithmetic of 5 ? I'm not able to understand how this is true.

PS: I know 3*7-1 % 5 = 0. I'm not able to make sense of inverses in modular arithmetic.

2

There are 2 best solutions below

2
On

$x^{-1}$ is said to be the multiplicative inverse of $x$ if:

$$x \cdot x^{-1} = 1$$

So in this case:

$$3 \cdot 7 = 21 \equiv 1 \mod (5)$$

0
On

A multiplicative inverse of $x \in \mathbb{R}$ is an element $x^{-1} \in \mathbb{R}$ which satisfies $xx^{-1} = 1$ (or equivalently, $x^{-1}x = 1$). Every non-zero real number has a multiplicative inverse and it is unique.

A multiplicative inverse of $x$ modulo $n$ is $x^{-1}$ such that $xx^{-1} \equiv 1 \bmod n$ (or equivalently, $x^{-1}x \equiv 1 \bmod n$). Unlike the first case, the multiplicative inverse of $x$ may not exist, even if $x$ is non-zero. For example, $2$ does not have a multiplicative inverse modulo $4$. In general, $x$ has a multiplicative inverse modulo $n$ if and only if $x$ and $n$ are coprime; in particular, if $n$ is prime, any $x$ which is not a multiple of $n$ has a multiplicative inverse. When the multiplicative inverse exists, it is unique modulo $n$.

In your case, $n = 5$ which is prime, so every integer which is not a multiple of $5$ has a multiplicative inverse. In particular, as $7$ is not a multiple of $5$, it has a multiplicative inverse. As multiplicative inverses are unique modulo $n$, we would only have to check the numbers $1, 2, 3,$ and $4$. As you have noted, $7\times 3 \equiv 1 \bmod 5$, so by definition, $3$ is the multiplicative inverse of $7$.