1
$\begingroup$

I am working on my own version of a proof of RSA and have come do a conclusion based on these simplified statements.
Given: N = pq
X ≡ 1 (mod p)
X ≡ 1 (mod q)
X ≡ 1 (mod N) by chinese remainder theorem

I have the original expression: MX ≡ M' (mod N)

When substituting X ≡ 1 (mod N) into this equation, is it correct to say that M = M' (removing the modulus) or must I say M ≡ M' (mod N)?

  • 0
    hm. it seems like my train of thought here is totally inaccurate...2011-01-02

1 Answers 1

0

HINT $\ $ No,$\ $ e.g.$\ $ let $\rm\ M'\: =\: M + N\:.\ $ But the inference that $\rm\ M'\equiv M\ (mod\ N)\ $ is correct since it's a special case of the congruence product rule, viz. $\rm\ X\equiv 1\ \Rightarrow\ M\:X \equiv M\cdot 1 \equiv M\:,\:$ i.e. $\rm\ M'\equiv M\:$.

  • 0
    Yes, see my link to the congruence product rule.2011-01-02