0

I'm reading a book on Cryptography and in the book it explains:

A modular multiplication is quite natural to define over such a set of numbers. Let’s take the following multiplication, for example:

3 x 2 = 6

With what you learned above, you know that 6 is congruent to 1 modulo 5, and thus the equation can be rewritten as

3 x 2 = 1 mod 5

Quite straightforward isn’t it? Note that the previous equation tells us that 3 is the inverse of 2, and vice versa. So we can also write, for example:

3^-1 = 2 mod 5

I can understand that 3 x 2 = 6.

And 6 mod 5 = 1 or 6 % 5 == 1. Therefore 3x2 = 1 mod 5

However what I don't understand is how it suddenly become proof that: 3^-1 = 2 mod 5

I understand that 3^-1 = 1/3.... so if 3^-1 = 2 mod 5

then

1/3 = 2 mod 5 no? I'm getting confused....

What foundational knowledge do I need to understand and how to connect the dots????

Thank you.

Wang Kah Lun
  • 10,240
preston
  • 101
  • 1
  • In beginning abstract algebra, one learns that $aa^{-1}=1$, where $1$ is the identity element – J. W. Tanner May 16 '21 at 04:47
  • You need to stop thinking in terms of remainders and learn about congruences. Many resources linked to WP. – Jyrki Lahtonen May 16 '21 at 04:50
  • I understand that 3^-1 = 1/3.... so if 3^-1 = 2 mod 5

    then

    1/3 = 2 mod 5 no? I'm getting confused....

     – preston May 16 '21 at 04:51
  • $a^{-1}=b$ simply means that with respect to the multiplication in question we have $a\cdot b=1$. You can then use it to solve linear equations just like in junior high. Given the congruence $$3x\equiv4\pmod5$$ you solve it by multiplying it with $3^{-1}$ just like you would solve the equation $3x=4$. Only this time $3^{-1}=2$, so $$x\equiv3^{-1}\cdot3x\equiv3^{-1}\cdot4=2\cdot4=8\equiv3.$$ And you can verify that this is a solution as $3\cdot3=9\equiv4$. – Jyrki Lahtonen May 16 '21 at 04:53
  • $2^{-1} =3 \mod 5$ – zkutch May 16 '21 at 04:58
  • May be the mental block you have is thinking that $3^{-1}$ has a meaning that does not depend on the context? In the reals or rationals $3^{-1}$ is, indeed $\dfrac13$. In $\Bbb{Z}5$ it means $2$. In $\Bbb{Z}{10}$ it means $7$. Whatever you can have in place of $x$ such that $3x=1$ is true. The meaning of the product in $3\cdot x$ depends on the context so the meaning of $3^{-1}$ will then change accordingly. – Jyrki Lahtonen May 16 '21 at 05:08
  • if 3x2 = 1 mod 5 then 6 mod 5 = 1 so 6/3 mod 5 = 1 / 3 which is another representation of 2 mod 5 = 3 ^-1. ......correct? – preston May 16 '21 at 06:54
  • Correct, cause $6 \cdot 3^{-1}=6 \cdot 2 =12 \equiv 2$. – zkutch May 16 '21 at 10:52

1 Answers1

1

Hint: holds $(5k+\color{red}{2})(5l+\color{red}{3})=5n+\color{red}{1}$.

zkutch
  • 13,410