Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

1 Answer 1

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

 
discard

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.