# Is there a theorem based on substitution to convert a congruency to an equality?

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)?

• Have you created a few examples and test cases to see? – Matthew Conroy Jan 2 '11 at 21:40
• i guess that would be a good thing to start with – dhatch387 Jan 2 '11 at 21:42
• hm. it seems like my train of thought here is totally inaccurate... – dhatch387 Jan 2 '11 at 21:47

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\:$.