# How to understand RSA Proofs of correctness at Wikipedia

$m^{ed}$ ≡ $m$ $\pmod{q}$
$m^{ed}$ ≡ $m$ $\pmod{p}$
then $m^{ed}$ ≡ $m$ $\pmod{pq}$

Question:
if $m^{ed}$ ≡ $m$ $\pmod{q}$,then $q$|$m^{ed}$- $m$
if $m^{ed}$ ≡ $m$ $\pmod{p}$,then $p$|$m^{ed}$- $m$
that is to say, $m^{ed}$- $m$ is the common multiple of both $p$ and $q$

At this time, if there is $lcm(p,q)=pq$, then $m^{ed}$ ≡ $m$ $\pmod{pq}$.
However, I am not sure $lcm(p,q)=pq$ holds true or not, so how can I prove $m^{ed}$ ≡ $m$ $\pmod{pq}$?

• Congratulation for wanting a rigorous proof. Hint (the best you should get from this website for homework): it is common to assume (or explicitly require) that $p$ and $q$ are distinct, and primes; see last phrase in first paragraph here. Nitpick: you used = where you meant ≡ (twice), and did not use $\TeX$ and its operator \pmod to its full power. – fgrieu Sep 21 '15 at 16:45
• Got it! Both $p$ and $q$ are primes, so $pq$ is very lcm (the least common multiple) of $p$ and $q$, then $pq$ | $m^{ed} -m$ Namely, $m^{ed} ≡ m$ $\pmod{pq}$ Am I right? – Matt Elson Sep 22 '15 at 2:11
• Yes, you solved the problem you had. Note: You can write $m^{ed}\equiv m\pmod{pq}$ as $m^{ed}\equiv m\pmod{pq}$, and $\operatorname{lcm}(p,q)=pq$ as $\operatorname{lcm}(p,q)=pq$ – fgrieu Sep 22 '15 at 5:47

If $m^{ed} \equiv m \pmod{q}$, then $q\;|\;(m^{ed}-m)$;
if $m^{ed} \equiv m \pmod{p}$, then $p\;|\;(m^{ed}-m)$;
thus $m^{ed}-m$ is a multiple of both $p$ and $q$;
thus $m^{ed}-m$ is a multiple of $\operatorname{lcm}(p,q)$.

Because both $p$ and $q$ are distinct primes, $\operatorname{lcm}(p,q)=pq$ holds;
Thus, $m^{ed}-m$ is a multiple of $pq$.

So $(pq)\;|\;(m^{ed} - m)$ clearly holds.
Thus finally, $m^{ed} \equiv m \pmod{pq}$.

• This is the end of the proof; for a full proof, you need to establish that $m^{ed} \equiv m \pmod{q}$ and $m^{ed} \equiv m \pmod{p}$ hold. Hint: use Fermat's little theorem, and whatever relation between $e$ and $d$ you are starting from, like $ed\equiv1\pmod{\varphi(pq)}$ or $ed\equiv1\pmod{\lambda(pq)}$. – fgrieu Sep 22 '15 at 17:26