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$
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.