How to make a proof of the correctness of the RSA encryption and decryption formula for $GCD(m_i,n)=1$ and $GCD(m_i,n) \neq1$ where encryption is defined as $c_i = m_{i}^e$ mod n and decryption $m_i = c_{i}^d$ mod n.
So thanks @poncho for giving tips, I wrote a following proof:
Recall that the integers $e > 0$ and $k > 0$ are chosen such that
$ ed = 1 + k(p − 1)(q − 1)$
It suffices to show that the two congruences
$(m^e)^d \equiv m\ \textrm{mod}\ p $ and $(m^e)^d \equiv m\ \textrm{mod}\ q $ hold. p and q are distinct primes, so $gcd(p,q) = 1$ and the above congruences imply that
$(m^e)^d \equiv m\ \textrm{mod}\ n $ by the Chinese Remainder Theorem. If $m \equiv 0\ \textrm{mod}\ p $, then certainly
$(m^e)^d \equiv m\ \textrm{mod}\ p $. If $m \not\equiv 0\ \textrm{mod}\ p $, then $m^{p-1} \equiv 1\ \textrm{mod}\ p $ beacuse of Fermat's little theorem ($a^{p-1} \equiv 1\ \textrm{mod}\ p $) hence,
$$ (m^e)^d \equiv m^{1 + k(p - 1)(q - 1)} \equiv m(m^{p-1})^{k(q-1)} \equiv m 1^{k(q-1)} \equiv m\ \textrm{mod}\ p
$$
Therefore $(m^e)^d \equiv m\ \textrm{mod}\ p $ holds for all integers m. Replacing p by q in the previous argument shows that $m \equiv (m^e)^d \textrm{mod}\ q $ holds for all integers m
Any comments about correctness of my proof are appreciated!
