Vrftsjtryk

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 2pmod{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?

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

$$xyequiv1;mod(n)iff yequiv 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,bmid(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+8Rightarrow 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 ajequiv 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 -4equiv9; 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)$$

Hint:

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

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

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

Thus you have

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

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