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 came across some transformation modulo p, while solving MIT algorithms course assignment, that I couldn't get. We have n bits long binary number A. I have a value of x1 mod p (p - random prime number in [2, n^2]), where x1 is m (m < n) bits long binary number, which includes bits A[0, m-1]. Now, I want to find a value of x2 mod p, where x2 is m long binary number, which includes bits A[1, m].

I in the solution I found the following transformation:

A[1, m] = 2(A[0, m-1]- 2^(m-1)) + A[m]

Taking both sides of this equation modulo p, we get

A[1, m] mod p = ( 2 ( (A[0, m-1] mod p) - (2^(m-1) mod p) ) + A[m] ) mod p

Regarding this transformation, I have a doubt, is this right to do the following:

(2(a - b) + c) mod p = (2 (a mod p - b mod p) + c) mod p ?

What laws allow to do that?

share|improve this question
Yes. Modular arithmetic works exactly like ordinary arithmetic in that sense. This is a straightforward exercise in the definition. –  Qiaochu Yuan May 16 '11 at 7:12
I've found the facts: –  fspirit May 16 '11 at 13:46
add comment

Your Answer


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

Browse other questions tagged or ask your own question.