Here is the whole thing: Part 1. Pairwise Coprimality (25 points) Write a functi
ID: 3809738 • Letter: H
Question
Here is the whole thing:
Part 1. Pairwise Coprimality (25 points)
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 paimoise 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.
Part 2. Congruence Classes (25 points)
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 ali 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,1Q. In this case, we return {0,3,6, 9,72}. One final example s congruence(S, 10, 100). In this case, we return {3, 13, 23,33,43,53,63,73,83,93}.
Part 3. Chinese Remainder Theorem (25 points)
The Chinese Remainder Theorem deals with modulo (thlnk rema'inder) 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:
a. The remainder of X/3 is 2.
b. The remainder of X/4 is 3.
c. 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:
. congruence(2,3,60):{2,5,8,11,14,17,20,23,26,,29,32,35,38,,41,M,47,50,53,56,59}
. congruence(3,4,60) : {3, 7, 71, 15, lg, 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.
Part 4/ Functions Tester (25 points)
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 I that solves the Chinese Renainder Theorem for two lists of moduli a.ad remainders.
4) Quit
Your function should continuously display the menu until the quit option is selected.
Explanation / Answer
1)Solution of Question1
fun[value] = CoPrime_pairwise(n)
value = true;
for j=1:numelements(n)-1 % applying first for loop statement
for k=k+1:numelements(n) % applying second for loop statements
if gcd(n(j),n(k))~=1 %if value is not true,set the value as false
value = false;
end
end
end
end