Multiplication modulo $n$

Question

I encountered the following basic encryption scheme while studying MIT OCW's 6.042 course:

1. Exchange a public prime $p$ and a secret prime $k'$.

2. Encryption: Compute $m'=rem(mk, p)$

3. Decryption:

   i) Compute $k^{-1}$ such that $kk^{-1}=1\pmod n)$

   ii) Now $m'=rem(mk,p)\equiv mk \pmod p$

   $\implies m'k^{-1}\equiv mkk^{-1} \pmod p$

   $\implies m'k^{-1}\equiv m \pmod p$ <--(How?)

I do not understand the last step. How is $kk^{-1} = 1$ ? We have only been taught the basic properties of modulo and I derived the above relation as follows:

Given $kk^{-1}\equiv 1 \pmod p$

$m'\equiv mk \pmod p$

$\implies m'.(kk^{-1}) \equiv mk.1 \pmod p$ [$a\equiv b \pmod n, \space c\equiv d \pmod n \implies ac\equiv bd \pmod n$]

$\implies m'k^{-1} \equiv m \pmod p$ [Since $gcd(k,p) = 1$]

Is my method correct, or is there any other way to derive the relation ?

Answer 1

You have $m'\equiv mk \pmod p$. Multiply both sides by $k^{-1}$ to get $m' k^{-1} \equiv mk k^{-1} \pmod p$.

On the other hand you have $kk^{-1}\equiv 1 \pmod p$. Multiply both sides by $m$ and you get $m kk^{-1}\equiv m \pmod p$.

You end up with $m' k^{-1} \equiv mk k^{-1} \equiv m \pmod p$