# Proof of correctness

We now consider $c^d = m^{ed} = m$necessary for the successful description of an RSA ciphertext. The core of this result is due to Euler's theorem which states

$a^{\phi(n)} \equiv 1 \mod n$

for all coprime integers $(a,n)$ and $\phi(n)$ is Euler's totient function.

As a reminder, we say two integers are coprime if they share no non-trivial factors. This is the same statement that $\gcd(a,n)=1$.

From the definition of the protocol, we have that

$ed \equiv 1 \mod \phi(n), \;\; \Rightarrow \;\; ed = 1 + k\phi(n)$

for some $k \in \mathbb{Z}$. Combining this with Euler's theorem, we see that we recover $m$from the ciphertext

When the requirement $\gcd(m, n) = 1$does not hold, we can instead look at the equivalences modulo $p$and $q$respectively. Clearly, when $\gcd(m, n) = n,$we have that $c \equiv m \equiv 0 \mod n$and our correctness still holds. Now, consider the case $m = k\cdot p,$where we have that $c \equiv m \equiv 0 \mod p$and $c^d \equiv (m^e)^d \pmod q.$Since we have already excluded the case that $\gcd(m, q) = q,$we can conclude that $\gcd(m, q) = 1,$as $q$is prime. This means that $m^{\ell\phi(q)} \equiv 1 \mod q$and by the multiplicative properties of the $\phi$function, we determine that $m^{\ell_n\phi(n)} = m^{\ell\phi(q)} \equiv 1 \mod q.$We conclude by invoking the Chinese Remainder theorem with

that $m^{e\cdot d} \equiv m \mod n.$The case for $m = k\cdot q$follows in a parallel manner.