Chinese remainder theorem

views updated

Chinese remainder theorem Let m1, m2,…, mr

be positive integers that are relatively prime to one another, and let their product be m: m = m1m2mr

Let n, u1, u2,…, ur be integers; then there is exactly one integer, u, that satisfies n u < (m + n)

and uuj (modulo mj) for 1 ← j r

About this article

Chinese remainder theorem

Updated About encyclopedia.com content Print Article