# 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.