Explore BrainMass

Explore BrainMass

    Chinese Remainder Theorem : Proof and Problems

    Not what you're looking for? Search our solutions OR ask your own Custom question.

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    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.

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

    © BrainMass Inc. brainmass.com November 24, 2022, 11:57 am ad1c9bdddf


    Solution Preview

    Please see the attached file for the full solution.
    Thanks for using BrainMass.

    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.