Basically it is similar to the RSA algorithm.
Let p and q be distince primes and let e and d be the integers satisfying
$de≡1$ (mod (p-1)(q-1)).Suppose further that c is an integer with gcd(c,pq)>1.
Prove that $x≡c^d$ (mod pq) is a solution to the congruence $x^e≡c$ (mod pq).
I have done with when gcd(c,pq)=1 which I found pretty easy. But for when gcd(c,pq)>1, c and pq has same factor. So, $p$ or $q$ or $pq$ is a divisor of c.
And then I am stuck with it.
What is the next step of the proof?
Thank you.
So, you're trying to show $c^{de}\equiv c\pmod{pq}$. It suffices to show $c^{de}\equiv c\pmod p$ and $c^{de}\equiv c\pmod q$. Consider two cases for the first of these, depending on whether or not $c$ is a multiple of $p$. Can you take it from there?