Chinese Remainder Theorem in C++

The goal of this assignment is to implement the Chinese Remainder Theorem in C++. It is pretty straightforward. I am totally comfortable with the math part of this assignment so If you have any questions or run into any problems while coding it, I'll be glad to work with you. Chinese Remainder Theorem: A system of linear congruences modulo pairwise relatively prime integers has a unique solution modulo the product of these modulli. Let m1, m2,.....mn be pairwise relatively prime positive integers. Then the system x= a1 (mod m1) "The equal sign represents congruency not x=a2 (mod m2) equality." x=an (mod mn) has a unique solution modulo m= m1*m2*.....mn. (That is there is a solution x with 0 <= x <= m and all other solutions are congruent modulo m to this solution. INPUT: our program would ask the user to enter positive integers a, b and nonzero m and n ( m and n are the modulli)Then the program would check that m and n are relatively prime that is their Greatest common divisor is 1, if it is then it will proceed. The program must also be able to detect invalid input and should display an error message if the input is invalid. OUTPUT: The program would output the unique solution 'x' to the system of congruences that the user has input. ## Deliverables Here is an example of how the Chinese remainder theorem works: Suppose we have a system of congruencies. x=2 (mod 3) "Again equal represents congruencies" x=3 (mod 5) x=2(mod 7) To solve this system of congruencies, first let m=3.5.7=105 M1= m/3 =35 M2=m/5 =21 M3=m/7 =15 We see that 2 is an inverse of M1=35 (modulo 3) since 35.2=1 (mod 3) Similarly 1 is an inverse of M2=21 (modulo 5) since 21.1= 1 (mod 5) Again 1 is an inverse of M3 =15 (modulo 7) since 15.1=1 (mod 7) The solution to this system are those x such that x=[login to view URL] + [login to view URL] + a3. M3. y3 = 2.35.2 + 3.21.1 + 2.15.1 233= 23 (mod 105) So 23 is the smallest positive integer that is a simultaneous solution. ## Platform The program must compile on a g++ compiler. THE DUE DATE IS THURSDAY FEB. 26TH 04. Again If you have any questions regarding the Chinese remainder theorem, or congruencies or modulli or greatest common divisors or any general questions regarding the assignment, please feel free to contact me.