Use MATLAB to implement a brute-force implementation of the Chinese remainder theorem. Please carefully read and follow the descriptions of each problem. No input/print statements are allowed except in the Functions Tester. Also, the use of built-in functions that specifically address or solve major components of the problem are not allowed.

1. Pairwise Coprimality: Write a function that takes as a parameter a list or vector and returns true if the elements in the list are pairwise coprime and false otherwise. For example, suppose the passed list is {10, 7, 33, 13}. This list is pairwise coprime since GCD(10,7) = GCD(10,33) = GCD(10, 13) = GCD(7, 33) = GCD(7,13) = GCD(33, 13) = 1 so the function returns true. On the other hand, the list {2, 3, 6, 9} is not pairwise coprime since GCD(3,6) = 3 so the function returns false. Note that pairwise coprimality is stronger than coprimality in general since GCD(2,3,6,9) = 1 but as seen earlier {2, 3, 6, 9} is not pairwise coprime.

2. Congruence Classes: Write a function that takes as parameters three numbers. The first number is the congruence class. The second number is the modulus, i.e., the number we divide by, and the third number is the cutoff. For example, congruence(1,2,10) finds all members of the congruence class of 1 modulo 2 less than 10, which in this case is (starting from 1) {1, 3, 5, 7, 9}. As you can notice, any element divided by 2 will have remainder 1. Another example is congruence(0,3,14). In this case, we return {0, 3, 6, 9, 12}. One final example is congruence(3, 10, 100). In this case, we return {3, 13, 23, 33, 43, 53, 63, 73, 83, 93}.

3. Chinese Remainder Theorem The Chinese Remainder Theorem deals with modulo (think remainder ) arithmetic. For example, suppose we have the list of numbers {3, 4, 5}. These numbers are pairwise coprime. Now suppose we want to find a number X such that the following holds true:

The remainder of X 3 is 2.

The remainder of X 4 is 3.

The remainder of X 5 is 1.

We can calculate X, which is the purpose of the Chinese remainder theorem, by using the congruence classes function defined in Problem 2 with the cutoff set to 3*4*5 = 60. In this case, we have the following: 1

congruence(2,3,60) = {2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59}

congruence(3,4,60) = {3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59}

congruence(1,5,60) = {1, 6, 11, 16, 21, 26, 31, 36, 41, 46, 51, 56}

The X that solves this problem is 11, which happens to be the smallest intersection of the three sets. Note that 11 mod 3 is 2, 11 mod 4 is 3, and 11 mod 5 is 1. For this problem, you need to calculate X where the function parameters are the list of moduli and the list of remainders. In the above example, the function can be called in MATLAB as crt([3 4 5], [2 3 1]), which will return 11 given the example above. If the list of numbers passed are not pairwise coprime, return -1 (or some other sentinel value) to indicate that the Chinese remainder theorem is not applicable.

4. Functions Tester: Write a function that tests the above functions by asking the user for input and displaying the output to screen. Your function should display the following menu: 1) Determine whether a list of numbers are pairwise coprime. 2) List all elements of a congruence class A less than Y modulo n. 3) Find the number X that solves the Chinese Remainder Theorem for two lists of moduli and remainders. 4) Quit Your function should continuously display the menu until the quit option is selected.