Proof of Unique Solution for Modular Exponentiation In Cryptography The question is about the encryption equation in asymmetric encryption.
For $c\equiv m^e\bmod n$, prove that for every unique $m$ there is a unique $c$.
Here $n=pq$ where $p$ and $q$ are primes larger than $m$ and
the exponent $e$, is $\geq3$ and coprime with $p-1$ and $q-1$.
Thanks!
 A: If ${\rm GCD}(e,(p-1)(q-1))={\rm GCD}(e,\phi(pq))={\rm GCD}(e,\phi(n))=1$ then you can find (by the so called Bezout identity) integers $r,s$ such that
$$
re+s\phi(n)=1.
$$
Thus you have
$$
m\equiv m^{re+s\phi(n)}\equiv c^r\bmod n
$$
and so you recover $m$ from $c$ proving its unicity.
In the above one uses the well known fact that $m^{\phi(n)}\equiv1\bmod n$ since the condition on $m$ implies that ${\rm GCD}(m,n)=1$ ($\phi$ is Euler's function, of course)
A: Hint $\ $ Raise $\ c\equiv m^{\large e}\pmod{pq}$ to power $\, k \equiv \dfrac{1}e\pmod{\phi(pq)}\ $ [it exists by $\,\gcd(e,\phi) = 1]$ 
which yields $\ c^k\equiv m,\ $  i.e. we can simply take the $e$'th root of both sides.
A: Showing that $m$ can be extracted from $c$ is fine, but I was looking for a more direct proof. Here's how I started:
To prove that $c$ is unique to $m$ assume that the opposite is true, i.e. that two different $m$ can equal the same c:
$$m_1^e  \equiv m_2^e \mod n$$ 
where $m_1$ and $m_2$ are distinct.
By definition that means:
$(m_1^e - m_2^e) = kn$ where k is an integer not equal to zero.
This means that if there are two distinct $m$ producing same $c$, then  $(m_1^e - m_2^e)$ is divisible by $n$.
Here $n = pq$, $p, q$ are primes, $e$ is 3 or greater and co-prime with $(p-1)$ and $(q-1)$, and $m$ is not divisible by $n$.
Can we show that the last statement above cannot be true for any $m_1$ and $m_2$? This would prove that $c$ is unique for any $m$ in the equation in the original posting.
