# 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 = .

https://brainmass.com/math/discrete-math/chinese-remainder-theorem-proof-problems-32055

#### Solution Preview

Please see the attached file for the full solution.

Thanks for using BrainMass.

QB5:

a. Proof:

1. Chinese Remainder Theorem: Suppose are positive integers relatively prime to each other, then for any integers with , must have a unique solution. This solution is

where and ,

Proof: Since are relatively ...

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