# Proving $x \equiv c^d \mod{(pq)}$ is a solution to $x^e \equiv c \mod{(pq)}$ when $gcd(c, pq) > 1$

I'm trying to prove that $x \equiv c^d \mod{(pq)}$ is a solution to $x^e \equiv c \mod{(pq)}$ when $gcd(c, pq) > 1$ and where $p, q$ are two odd prime numbers and $de \equiv 1 \mod{(pq)}$.

My attempt:

Since $de \equiv 1 \mod{(pq)}$, there exists an integer $k$ s.t $de = 1 + k\cdot pq.$

Thus,

$(c^d)^e \equiv c^{de} \equiv c\cdot(c^{(p-1)(q-1)})^k \mod{(pq)}.$

Since $p, q$ are two odd primes, $gcd(c, pq)$ can either be $p, q$ or $pq$ as far as I can see.

Let's say $gcd(c, pq) = pq$. Then we have,

$c^{(p-1)(q-1)} \equiv 0 \mod{(pq)}$ so we end up with 0. This case holds.

Now let's say $gcd(c, pq) = p$

Then we have,

$c^{(p-1)(q-1)} \equiv 0 \mod{(p)}$ and

$c^{(p-1)(q-1)} \equiv 1 \mod{(q)}$.

By using Chinese Remainder Theorem, we can write,

$c^{(p-1)(q-1)} \equiv p\cdot(p^{-1} \mod{q}) \mod{(pq)}$.

At this point I'm stuck. No idea how to proceed.

Given $x^e \equiv c \mod pq$ and $de \equiv 1 \mod pq$ for primes $p$ and $q$.
Notice that the second congruence implies that $d$ and $e$ are modular inverses; that is, $$d \equiv e^{-1} \mod pq$$ Now back to the original statement $$x^e \equiv c \mod pq$$ Raising both sides to the power of $d \equiv e^{-1}$ yields $$x^{e(e^{-1})} \equiv c^d \mod pq$$ And this simplifies to the result of $$x \equiv c^d \mod pq$$
Note that for $d$, the modular inverse of $e$, to exist, $e$ must be coprime to the modulus $pq$. There is no solution to $de \equiv 1 \mod pq$ for $gcd(e, pq) > 1$