Euclid’s Algorithm & Linear Congruences

 GCD of two numbers  using Euclid’s algorithm

clc

clear;

prompt1 = "Enter the first number: ";

m = input(prompt1); %Get the first number

prompt2 = "Enter the second number: ";

n = input(prompt2); %Get the first number

ans=euclid(m,n); %Call the recursive function euclid

if ans==-1

   fprintf('Enter the numeric values\n')

elseif ans==-2

   fprintf('Enter the integral values\n')

elseif ans==-3

   fprintf('Enter the positive values\n')

else

   fprintf('%d\n',ans)

end

 

function [res] = euclid(m,n)

    % Are m and n the right types?

    if ~isnumeric(m) || ~isnumeric(n)

        res = -1;

        return

    end

    % Are m and n integer-like?

    if m ~= int64(m) || n ~= int64(n)

        res = -2;

        return;

    end

    % Are m and n greater than zero?

    if m <= 0 || n <= 0

        res = -3;

        return

    end

    % Swap m and n if m less than n

    % to allow the algorithm to function properly

    if m < n

        tmp = m;

        m = n;

        n = tmp;

    end

    % Result of modulus is zero so we have found the gcd

    if mod(m,n) == 0

        fprintf('GCD(%d,%d)=>',m,n);

        res = n;

    else

        fprintf('GCD(%d,%d)=>',m,n);

        res = euclid(n,mod(m,n));  % Euclid's algorithm

    end

   

end

 Output

Enter the first number: 18

Enter the second number: 480

GCD(480,18)=>GCD(18,12)=>GCD(12,6)=>6

 

Exercise

Find GCD of the following: 1) (24,30),    2) (128,96)

 

Solution of a linear congruence

clc

clear;

prompt1 = "To solve Linear Congruence ax =c(mod m)\n Enter a: ";

a = input(prompt1);

prompt2 = "Enter c: ";

c = input(prompt2);

prompt3 = "Enter m: ";

m = input(prompt3);

[g,u0,v0] = EuclidMatrix(m,a);

    if ( mod(c,g) ) ~= 0

        disp('No solutions.')

        solutions = [];

        return

    end

       

 disp([ num2str(m) 'x + ' num2str(a) 'y = ' num2str(g)  ])

 disp(['Number of Solutions: (' num2str(u0) ')' num2str(m)...

      ' + (' num2str(v0) ')' num2str(a) ' = ' num2str(g) ]);

   

 u = u0 -  (a / g);

 v = v0 +  (m / g);

 x = v * (c / g);

 y = u * (c / g);

 S = @(k) x + k * (m/g);

 solutions = mod(S(0:g-1),m);

 fprintf('solution=%f\n',solutions)

   

    % Euclidean Algorithm, Beazout's Coefficients are stored in matrix

    function [g,u,v] = EuclidMatrix(a,b)

        M = [ 1 0; 0 1 ];

        n = 0;

        while (b ~= 0)

            q = floor(a/b);

            M = M * [ q 1; 1 0];

            t = a;

            a = b;

            b = t - q * b;

            n = n + 1;

        end

        g = a;

        u = ( -1 )^n * M(2,2);

        v = (-1)^(n+1) * M(1,2);

        disp([ num2str(u) 'x + ' num2str(v) 'y = ' num2str(g)  ])

    end

 

Output

To solve Linear Congruence ax =c(mod m)

 Enter a: 15

Enter c: 6

Enter m: 7

-2x + 1y = 1

7x + 15y = 1

Number of Solutions: (-2)7 + (1)15 = 1

solution=6.000000

 

Exercise:

Solve the following congruences

1) 2x≡51(mod 8) 2) 4x≡26(mod 7) 3) 25x≡15(mod 29)

4) 9x≡42(mod 6) 5) 6x≡15(mod 21)