
# 5.1 Linear Diophantine Equations

Thinking out loud

Mary went to a park and saw vehicles with $$2$$ wheels and $$4$$ wheels. She counted the wheels. When she came home she told her mom that she has seen the vehicles and it was total of $$28$$ wheels.Then her mom asked how many vehicles with $$2$$ wheels and how many vehicles with $$4$$ wheels?

Diophantine Equations

Diophantine equations are a polynomial equation with 2 or more unknowns.

Linear Diophantine equations is an equation with 2 or more monomial integers, and the integers are each to only a degree of 1.

Example $$\PageIndex{1}$$:

Linear Diophantine equations take the form of  $$ax+by=c, x, y \in \mathbb{Z}$$ , and a, b, c, are constants. x and y are variables unknowns.

Homogeneous linear diophantine equations are $$ax+by=0.$$

Example of a homogeneous linear diophantine equation:

$$5x-3y=0$$

$$x= 3$$ and $$y=5$$

$$x=6$$ and $$y=10$$

$$x=3k$$ and $$y=5k, k \in \mathbb{Z}$$.

$$5(3k)-3(5k),$$

$$15k-15k = 0.$$

**** NOTE****, In a homogeneous linear diophantine equation, the minute the equation is addition, one of the integers is required to be a negative.

$$5x+3y=0$$

$$x= -3k, k\in\mathbb{Z}$$

$$y= 5k, k \in\mathbb{Z}$$.

Example $$\PageIndex{2}$$:

Homogeneous Linear Diophantine Equation Theorem:

If the GCD of a and b = d, then the complete family of solutions to ax+by=0 is:

x=b/d(k)

y=a/d(k), for k, (\in\mathbb{Z}\).

4x+6y=0, GCD of 6 and 4 is 2.

x= -6k/GCD of 6 and 4, for k, (\in\mathbb{Z}\)

-6k/2=-3k,  therefore x=-3k, for k,  (\in\mathbb{Z}\).

y= 4k/GCD of 6 and 4, for k,  (\in\mathbb{Z}\)

4k/2= 2k, therefore y=2k, for k,  (\in\mathbb{Z}\).

Example $$\PageIndex{3}$$:

Linear Diophantine Equations: ax+by=c. C cannot equal 0, x,y,  (\in\mathbb{Z}\).

Use the following steps to solve non homogeneous linear diophantine equations.

SOLVE the LDE 5x+3y=4:

Step 1: Determine the GCD of 5 and 3 (a and b). The GCD of 5 and 3 is 1.

Step 2: Check that the GCD of a and b is divisible by c.

NOTE: If YES, continue on to step 3.

If NO, STOP here as there is no solution.

We know that 1/4, there for we will continue on to Step 3.

Step 3: Find the general solution to ax+by=0.

5x+3y=0

x=-3k and y= 5k, k ,(\in\mathbb{Z}\).

Step 4: Find a particular solution to ax+by=c.

5(5)+3(-7)=4

x=5 and y=-7.

Step 5:

Let u=x-5, and v=y+7. (The opposite integer of Step 4, so if it's positive in step 4 it will be negative in step 5 and vice versa)

Then 5u+3v= 5(x-5)+3(y+7)

= 5x-25+3y+21

=5x+3y-4

= 4-4 (This happens because the first equation is 5x+3y=4)

=0.

Step 6: Solve 5u+3v=0

u=-3m, m,(\in\mathbb{Z}\)

v=5m, m, (\in\mathbb{Z}\).

Step 7:

x-5=-3m, m, (\in\mathbb{Z}\)

y+7=5m, m, (\in\mathbb{Z}\).

Hence x=-3m+5, y=5m-7, m (\in\mathbb{Z}\).

PRACTICAL USES

• Cryptography
• Designing different combinations of a variety of elements.