0
$\begingroup$

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.

$\endgroup$

1 Answer 1

0
$\begingroup$

I suspect my reasoning is flawed, but I believe the solution is simple.

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 $

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .