Please use basic MATLAB functions and processes to implement the code for the fo

Question

Please use basic MATLAB functions and processes to implement the code for the following problems. Please read instructions carefully and include well detailed comments so that I can follow each step. Thank you in advance.

Problems n this lab, we wi use MATLAB to implement a "brute-force" implementation of the Chi nese remainder theorem. Please carefully read and follow the descriptions o each problem. No input print statements are allowed ercept in the Functions Tester. Also, the use of built-in func tions that specifically address or solve major components of the problem are not allowed. When in doubt, please ask the instructor. 1. Pairwise Coprimality (25 points Write a function that takes as a parameter a list or vector and returns true if the element t are pairwise coprime and false otherwise. For example, su pose the passed list s 110,7, 33, 13. This t 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 12,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 see earlier (2, 3, 6, 9) is not pairwise coprime. 2. Congruence Classes (25 points) three numbers. The first number is the congruence Write a function that takes as parameters class. The second number is the modulus the number we divide by, and the third number is the cutoff For exan e, congruence (1,2,10) ds 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 otice. any element divided by 2 will have remainder 1. Another example is congruence(0 this case, we return 0,3, 6, 9, 12). One final example is congruenc 10, 100 In this case we return 13, 13, 23, 33, 43, 53, 63, 73,83,93) 3. Chinese Remainder Theorem (25 points) The Chinese Remainder Theorem deals with modulo (think remainder) arithmetic. For ex ample, suppose we have the list of numbers 3, 4, 5). These numbers are pairwise coprime Now supp ose we want to find a number X such that the following holds true: The remainder of is 2 The remainder of is 3 The remainder of is 1. We can calculate X, which is the purpose of the Chi ese remainder theorem. by using the congruence classes function defined in Problem 2 with the cutoff set to 3 4 5 600. In this case, we have the following: 12, 5,8, 11,14, 17, 20, 23, 26, 29, 32,35,38, 41,44, 47, 50, 53, 56, 59) congruence (2,3,60 {3,7,11, 15, 19,23,27,31,35, 39,43,47, 51, 55, 59) congruence (3,4,60 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 modul and the of remainders n the above example, the function can be called in MATLAB as crt( 3 4 5], [2 3 ij), which will return 11 given the example above. If the list of numbers passed are not pairwise coprime, return -1 (or er sentinel value) to indicate that the Chinese some oth remainder theorem is not applicable Functions Tester (25 point 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 co nce 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

Explanation / Answer

function [val] = pairCoPrime(x)
    val = true;
    for i=1:numel(x)-1
        for j=i+1:numel(x) %nested loop for each possible pair of elements
            if gcd(x(i),x(j))~=1 %if gcd is not 1, put flag as false
                val = false;
            end  
        end
    end
end

function [results] = congruence(cls, md, co)
    x = mod(cls,md); %determine class
    results = [];
    for i=cls:co
        if mod(i,md)==x
            results = [results, i]; %add elemet if it belongs to same class
        end
    end
end

function [result] = crt(x,y)
  
    if pairCoPrime(x)==false
        result = -1; %x is not co prime
        return;
    end
  
    if numel(x) ~= numel(y)
        result = -2; %x and y are un equal
        return;
    end
    co = prod(x);
    ins = congruence(y(1),x(1),co);
    for i=2:numel(x)
        ins = intersect(ins, congruence(y(i),x(i),co)); %performs intersection
    end
    if numel(ins)>0
        result = ins(1); %selects the 1st element
    else
        result = -4; %indicates no element
    end
end

%script for main

ch = 0
while (ch ~= 4)
    fprintf('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 ');
    ch = input('Enter your choice: ');
    switch ch
        case 1
            x = input('Enter numbers: ');
            if pairCoPrime(x)
                fprintf('They are co-prime ');
            else
                fprintf('They are no co-prime ');
            end
        case 2
            A = input('Enter A: ');
            n = input('Enter n: ');
            Y = input('Enter Y: ');
            fprintf ('Elements are: %d ', congruence(A,n,Y));
        case 3
            x = input('Enter set 1: ');
            y = input('Enter set 2: ');
            fprintf('Result is: %d ',crt(x,y));
    end
end

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---