Modular Arithmetic- Diophantine Equation

 Remainder function – (mod)

mod function is used to find the remainder when one number is divided by another.  If R is the remainder obtained when X is divided by Y then R=mod(X,Y)

 

Syntax of the mod function:

R = mod (X, Y)

 

Example 1: ‘mod’ function for scalar inputs

Code	Output
R = mod (15, 6)	R =    3

 

Solving linear Diophantine equation

The simplest linear Diophantine equation takes the form ax+by=c, where a, b and c are given integers. The solutions are described by the following theorem:
This Diophantine equation has a solution (where x and y are integers) if and only if c is a multiple of the greatest common divisor of a and b. Moreover, if f(x,y) is a solution, then the other solutions have the form (x+kv, y-ku), where k is an arbitrary integer, and u and v are the quotients of a and b (respectively) by the greatest common divisor of a and b.
Let ax+by=0, x,y in Z be a homogeneous linear Diophantine equation. If gcd(a,b)=d, then the complete family of solutions to the above equation is x=(b/d)k , and y=(-a/d)k, k in Z. 

To find the particular solution of the Diophantine equation:

clc

clear;

syms x y t

assume([x y], 'integer')        % assume ‘x’ and ‘y’ are integers

eqn = 50*x +20*y == 300 ;      % declare the equation

disp(eqn)

c = coeffs(lhs(eqn) ,[y,x]); %c(1)->Coefficient of x, c(2)->Coefficient of y

r=rem(rhs(eqn),gcd(c(1),c(2)));

if r~=0

    disp('No Solution')

else

    fprintf('%d is multiple of gcd(%d,%d)=%d, hence it has solution\n',rhs(eqn),c(1),c(2),gcd(c(1),c(2)))

    if rhs(eqn)~=0

        [xSol, ySol] = solve(eqn,[x y]);  % solve for ;x’ and ‘y’

        xComp=xSol+t*(c(2)/gcd(c(1),c(2)));

        yComp=ySol+t*(-c(1)/gcd(c(1),c(2)));

    else

        xSol=c(2)/gcd(c(1),c(2));

        ySol=-c(1)/gcd(c(1),c(2));

        xComp=xSol*t;

        yComp=ySol*t;

    end

    fprintf(' Solution is : x=%d, y=%d\n',xSol,ySol)

 

    fprintf('General Solution [x,y]:\n')

    fprintf('x=')

    disp(xComp)

    fprintf('y=')

    disp(yComp)

end

 

Output

50*x + 20*y == 300

300 is multiple of gcd(50,20)=10, hence it has solution

Solution is : x=-30, y=90

General Solution [x,y]:

x=2*t - 30

y=90 - 5*t

 

Exercise:

1. Find the particular solution of the following linear Diophantine Equations:

    a) 6x+9y=0             b) 2x+4y=21           c) 20x+16y=500

2. Find all the solutions (x, y) to the Diophantine equation 11x + 13y = 369 for which x and y are both positive.