Result of mod division

Question

I am trying to understand the result of modulo division aka multiplication with the multiplicative inverse. When I try (using a computer program) the following example the result makes sense: $$ 6 \times 3^{-1} \equiv 2\pmod{13} $$

But I cannot understand the result for the following examples: $$ 1 \times 3^{-1} \equiv 9 \pmod{13} $$ $$ 2 \times 3^{-1} \equiv 5 \pmod{13} $$ $$ 5 \times 3^{-1} \equiv 6 \pmod{13} $$

Can someone explain the result when the equivalent non-mod division would yield a decimal instead of a whole number?

Answer 1

Hint:

Look at $$ 9 \times 3\equiv\, ? \pmod{13} $$ $$ 5 \times 3\equiv\, ? \pmod{13}$$ $$ 6 \times 3\equiv\, ? \pmod{13} $$

Answer 2

It is not a real division, it is a multiplication by the inverse of $3$ modulo $13$.

Now $\;9\times 3\equiv 1\mod 13$ since $9\times 3=2\times 13+1$, so $3^{-1}\equiv 9$.

Thus you have

$$6\times 3^{-1}\equiv 6\times 9=54\equiv 2\mod 13,$$ and similarly for all other multiplications.

Answer 3

Notice that this works because: $$ 6 \times 3^{-1} \mod 13 = 2 \times 3 \times 3^{-1} \mod 13= 2 \times 1 \mod 13$$ And actually we also know that: $$1 \equiv 27 \mod 13 \equiv 3 \times 9 \mod 13 $$ $$2 \equiv 15 \mod 13 \equiv 3 \times 5 \mod 13 $$ $$5 \equiv 18 \mod 13 \equiv 3 \times 6 \mod 13 $$ If we multiply by $3^{-1}$ this means we cancel out the factor of $3$.

Answer 4

With the modular multiplicative inverse of an integer $x$ you want to compute the smallest $y$ such that

$$xy\equiv1\;mod(n)\iff y\equiv x^{-1}\; mod(n)$$

In order to compute these values, you can either use the extended Euclidean algorithm or Euler's theorem (since I find the EEA more useful, I'll use this algorithm instead of Euler's theorem.)

---

With the extended Euclidean algorithm:

The first part of the EEA for $a,b\mid(a>b)$ is just like the standard Euclidean algorithm, which proceeds by a succession of Euclidean divisions whose quotients are not used, only the remainders are kept. More precisely, it consists in computing the following sequence $$a=q_1*b+r_1$$ $$b=q_2*r_1+r_2$$ $$r_1=q_3*r_2+r_3$$ $$.$$ $$.$$ $$r_n=q_{n+2}*r_{n+1}+0$$

Where $q_k$ are the quotients (note that $q_k=\lfloor \frac{r_{k-2}}{r_{k-1}}\rfloor$) and $r_k$ the reminders after performing the Euclidean division. The algorithm stops when $r_{n+2}=0$ and results in $gcd(a,b)=r_{n+1}$
For instance for $a=97, \;b=21$ $$97=4*21+13$$ $$21=1*13+8$$ $$13=1*8+5$$ $$8=1*5+3$$ $$5=1*3+2$$ $$3=2*1+1$$ $$2=2*1+0$$ $$\Rightarrow gcd(97,21)=1$$

Now in the EEA, you have to perform the standard EA solving for the remainders as a linear combination of $a$ and $b$ $$97=4*21+13 \Rightarrow 13=97-4*21$$ $$21=1*13+8\Rightarrow 8=21-1*13=21-1*(97-4*21)=5*21-97$$ $$13=1*8+5 \Rightarrow 5=13-8=97-4*21-(5*21-97)=2*97-9*21$$ $$8=1*5+3 \Rightarrow 3=8-5=5*21-97-(2*97-9*21)=14*21-3*97$$ $$5=1*3+2 \Rightarrow 2=5-3=2*97-9*21-(14*21-3*97)=5*97-23*21$$ $$3=2*1+1 \Rightarrow 1=3-2=14*21-3*97-(5*97-23*21)=37*21-8*97$$

This last expression is known as Bèzouts identity or Bèzouts Lemma, which states that for any integers $a$ and $b$ with lcd$(a,b)=d$, $\exists$ coefficients $j$ and $i$ such that $$aj+bi=d$$ The greatest common divisor of two integers $a,b$ is, by the way, the smallest linear combination of these numbers you can make, which you can compute with the EEA. Having that said, note that $$aj+bi \equiv aj\equiv d \; mod(b)$$ So, if gcd$(a,b)=1$, (and only under this condition $\exists$ a multiplicative inverse) the modular multiplicative inverse of $a\; mod(b)$ is the coefficient $j$ of $a$ in Bèzout's identity.

For the exercises you have:

$$13=4*3+1$$ $$3=3*1+0$$ $$\Rightarrow 1*13-4*3=1$$ $$\Rightarrow 3^{-1}\equiv -4\equiv9\; mod(13)$$ $$$$ $$2*3^{-1}\equiv 2*9 \equiv 18 \equiv 5\; mod(13)$$ $$5*3^{-1}\equiv 5*9 \equiv 45 \equiv 6\; mod(13)$$