Share
Explore BrainMass

Chinese Remainder Theorem : Proof and Problems

I would appreciate it if someone could provide the solutions to QB5 of the attatched exam paper.
Please see the attached file for the fully formatted problems.

B5.
(a) (1) State and prove the Chinese Remainder Theorem.
(ii) Find the 2 smallest positive integer solutions of the simultaneous set of congruence equations:
2x=3 (mod 5)
3x=4 (mod 7)
x=5 (mod8)
(b) Let p be a prime and a a positive integer. How many solutions are there to the equation x2 ? x O(mod pr')?
(c) Let n and in be coprirne integers. Show ? x 0 (mod nrn) if and only if x2 ? x 0 (mod n) and ? x 0 (mod m).
(d) How many solutions are there to the equation x2 ? x 0 (mod N)
where N has collected prime factorization N = .

Attachments

Solution Summary

The Chinese Remainder Theorem is Proven and Problems are solved. The solution is detailed and well presented. The solution was given a rating of "5" by the student who originally posted the question.

$2.19