Suppose that the naturals m,..., mk are pairwise relatively prime and that for each i from...

Transcribed Image Text:

Suppose that the naturals m,..., mk are pairwise relatively prime and that for each i from 1 through k, the natural x satisfies x = x; (mod mi) and the natural y satisfies y = yi (mod mi). Explain why for each i, xy satisfies xy = xyi (mod m;) and x + y satisfies (x + y) = (xi + Yi) (mod mi). Now suppose that 21,, z; are some naturals and that we have an arithmetic expression in the zi's (a combination of them using sums and products) whose result is guaranteed to be less than M, the product of the mi's. Explain how we can compute the exact result of this arithmetic expression using the Chinese Remainder Theorem only once, no matter how large j is. Suppose that the naturals m,..., mk are pairwise relatively prime and that for each i from 1 through k, the natural x satisfies x = x; (mod mi) and the natural y satisfies y = yi (mod mi). Explain why for each i, xy satisfies xy = xyi (mod m;) and x + y satisfies (x + y) = (xi + Yi) (mod mi). Now suppose that 21,, z; are some naturals and that we have an arithmetic expression in the zi's (a combination of them using sums and products) whose result is guaranteed to be less than M, the product of the mi's. Explain how we can compute the exact result of this arithmetic expression using the Chinese Remainder Theorem only once, no matter how large j is.

Answer rating: 100% (QA)

Lets assume k 1 In this case we have a single positive integer m1 We need to prove that for any integer a1 there exists an integer r such that 1 r m1 ... View the full answer