# Result of mod division

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?

• try to see $3^{-1}$ as the number which multiplied by 3 gives 1, so mod $13$, since $3*9=27 = 1$ mod $13$ hence $3^{-1}=9$ mod 13
– ALG
Nov 26, 2018 at 20:53

Hint:

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

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.

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)$$

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$$.

• But that doesn't work for $\ 1\times 3^{-1}\$ or $\ 5\times 3^{-1}\ \$ Nov 26, 2018 at 21:37
• Actually we know that $1 \equiv 27 \mod 13 \equiv 3 \times 9 \mod 13$
– user459879
Nov 26, 2018 at 21:43
• I would prefer using the Euclidean algorithm to actually find all such elements by solving the linear diphantine equation: $$3k + 13l =1$$ All such $k$ are inverses of 3.
– user459879
Nov 26, 2018 at 21:44