I want to make a following proof but I got some difficulties with it. Would be super if you people have any tips / advises.


Let (N,e) be our public key and (N,s) our private key with $N=pq$ and $ggT(\varphi(n),e)=1$, as well as $es\equiv 1\mod N$.

I want to show that since Lemma of Bézout shows, that there are $a,b\in \mathbb{N}$ so that $ap-bq=1$, the message of $x=ap\mod N$ is equal to the encrypted message $y=x^e \mod N$.

My Plan:

I started by using the Chinese remainder theorem. To show $x\overset{!}{=}y=x^e\mod N$ we need to show, that $x\overset{!}{=}x^e\mod p$ and $x\overset{!}{=}x^e\mod q$. I could also use the Chinese remainder theorem on $x=ap\mod N$.

So I need to show, that $ap \mod p=(ap)^e\mod p$. Since ap is a multiple of p, it should be $ap\equiv 0\mod p$ and so $(ap)^e=0\mod p$. It follows that $ap\mod p=(ap)^e\mod = p= 0 \mod p$.

I now need to show, that $ap\mod q=(ap)^e\mod q$. This is the part I am struggling with. I know that $ap-bq=1$ but I have no glue how this is going to help me. I was thinking about something like $ap=(bq+1)\mod q$ but i am not sure if this works / what to do next.

  • $\begingroup$ Your last thought is entirely correct. It implies that $ap \equiv 1 \pmod q \implies (ap)^e \equiv 1 \pmod q$. $\endgroup$
    – user114966
    Commented Jan 22, 2021 at 12:19
  • 1
    $\begingroup$ Oh my god, how could i oversee that ... Of course $q|bq$ and so we have $ap\equiv1\mod q$ $\endgroup$ Commented Jan 22, 2021 at 14:25
  • $\begingroup$ Can you be more specific about what your question is? We are a question-and-answer site, so we require you to articulate a specific question -- asking whether we have any reactions to some work-in-progress isn't within the scope of this site. $\endgroup$
    – D.W.
    Commented Jan 23, 2021 at 3:36
  • $\begingroup$ I am sorry about this. I wanted to know how to show, that $ap\equiv_p (ap)^e$. Dmitry already gave me the input needed and now i answered the question, so that other people can look it up. $\endgroup$ Commented Jan 23, 2021 at 10:20

1 Answer 1


You can show that $ap\mod q =(ap)^e\mod q$ by using the fact, that $ap-bq=1\Longleftrightarrow ap=bq+1$.

You know that $q|bq$ and therefor $ap\mod q = bq+1\mod q \equiv 1\mod q$.

This implicates that $(ap)^e\mod q = (bq+1)^e\mod q \equiv 1\mod q$. Therefor $ap\mod q \equiv (ap)^e\mod q.$

Now with the chinsese remainder theorem we know that $ap\equiv_N(ap)^e$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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