Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 0 down vote accepted

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

share|cite|improve this answer
but I could say that M ≡ M' (mod N)? – dhatch387 Jan 2 '11 at 22:19
Yes, see my link to the congruence product rule. – Bill Dubuque Jan 2 '11 at 22:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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