In the paper "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems" by R.L. Rivest, A. Shamir, and L. Adleman, they prove correctness of deciphering algorithm by following ways:
Due to Euler and Fermat : for any integer (message) M which is relatively prime to n, Mφ(n) ≡1 (mod n) . (3)
Here φ(n) is the Euler totient function giving number of positive integers less than n which are relatively prime to n. For prime numbers p,
φ(p) = p −1 .
In our case, we have by elementary properties of the totient function [7]:
φ(n) = φ(p) ·φ(q) = (p −1) ·(q −1) (4) = n −(p + q) + 1 .
Since d is relatively prime to φ(n), it has a multiplicative inverse e in the ring of integers modulo φ(n): e ·d ≡1 (mod φ(n)).
Me·d ≡ Mk·φ(n)+1 (mod n) (for some integer k). 7 From (3) we see that for all M such that p does not divide M
Mp−1 ≡1 (mod p)
and since (p −1) divides φ(n)
Mk·φ(n)+1 ≡M (mod p).
This is trivially true when M ≡ 0 (mod p), so that this equality actually holds for all M. Arguing similarly for q yields
Mk·φ(n)+1 ≡M (mod q) .
Together these last two equations imply that for all M,
Me·d ≡Mk·φ(n)+1 ≡M (mod n). This implies (1) and (2) for all M,0 ≤ M < n. T. Therefor E and D are inverse permutations.
I do not understand the part where they do : Me·d ≡ Mk·φ(n)+1 (mod n) (for some integer k) what does that mean? Is it because both e and d are less than φ(n)?
$e \cdot d \equiv 1 \pmod{\phi(n)}$ means that the integer $ed$ has remainder $1$ when divided by $\phi(n)$ so there is some integer $k$ so that $$e\cdot d =k\cdot\phi(n)+1$$
(the $k$ is the integer quotient of $ed$ when divided by $\phi(n)$)
so that $$M^{e\cdot d} \equiv M^{k\phi(n) +1} \pmod{n}$$ then auromtically follows. The exponents are the same, hence the powers of $M$ too.
So it's just a reformulation of $d$ and $e$ being inverses modulo $\phi(n)$.