# Linear Diophantine Equations

• May 15th 2006, 04:02 AM
delpin
Linear Diophantine Equations
Hi
I'm looking for help on solving Linear Diophantine Equation
15y + 27x = 39

partial solution

y = (39-27x)/15

y = (39 - 12x - 15x)/15

y = (39 - 12x)/15 - x

Next step? I'm unsure

• May 15th 2006, 05:04 AM
CaptainBlack
Quote:

Originally Posted by delpin
Hi
I'm looking for help on solving Linear Diophantine Equation
15y + 27x = 39

I'm not sure this is how you are expected to solve this, or even if this
is the simplest method; but:

First divide through by $\displaystyle 3$ and rearrange to get:

$\displaystyle 5y+9x-13=0$

Now this gives:

$\displaystyle 4 x -3 \equiv 0 \mod\ 5$

So there exists an integer $\displaystyle \lambda$ such that:

$\displaystyle 4 x=5\lambda+3$

Now the LHS (left hand side) is even, so $\displaystyle \lambda$ must be odd.
So let $\displaystyle \lambda=2\mu+1$, then:

$\displaystyle 4x=10\mu+8$

But the LHS is divisible by $\displaystyle 4$ so the RHS must also be divisible by
$\displaystyle 4$ so $\displaystyle \mu$ must be even., so we may write it as $\displaystyle \mu=2\kappa$, and then:

$\displaystyle x=5\kappa+2$

Now substituting this back into $\displaystyle 5y+9x-13=0$ gives:

$\displaystyle y=-9 \kappa-1$

So we see that for any $\displaystyle \kappa \in \mathbb{Z}$:

$\displaystyle x=5\kappa+2$
$\displaystyle y=-9 \kappa-1$

is a solution.

RonL
• May 15th 2006, 10:33 AM
ThePerfectHacker
Use the following theorem,
Given a diophatine equation with $\displaystyle \gcd(a,b) |c$
$\displaystyle ax+by=c$
and $\displaystyle x_0,y_0$ is a particular solution
Then all solutions and every solution is,
$\displaystyle x=x_0+\frac{b}{d}t$
$\displaystyle y=y_0-\frac{a}{d}t$
for an integer $\displaystyle t$
------
You have,
$\displaystyle 15y+27x=39$
You can leave it the way it is but I suggest to divide by 3,
$\displaystyle 5y+9x=13$
You need to find a specific solution. Which can be done with trail and error. (Otherwise you can use the Euclidean Algorithm or Coutinued fractions to get a particular solution).
We can easily see that $\displaystyle y=-1$ and $\displaystyle x=2$ work.
Also $\displaystyle \gcd(5,9)=1$ which divides 13.
Thus, all solutions are,
$\displaystyle y=-1+9t$
$\displaystyle x=2-5t$

Note it might look different from CaptainBlack's but they are both equivalent.
• May 15th 2006, 12:21 PM
delpin
Thank you
• May 28th 2006, 07:04 AM
Soroban
Hello, delpin!

This is basically Captain Black's and Hacker's solutions ... in baby-talk.

Quote:

I'm looking for help on solving Linear Diophantine Equation: $\displaystyle 15y + 27x \:= \:39$
First, reduce the equation: .$\displaystyle 5y + 9x\:=\:13$

We have: .$\displaystyle 9x - 13\;= \;-5y$

. . Then: .$\displaystyle 9x \;\equiv \;13 \pmod{5}\quad\Rightarrow\quad 4x\;\equiv\;3 \pmod{5}$

Multiply both sides by 4:
. . $\displaystyle 16x\;\equiv \;12 \pmod{5}\quad\Rightarrow\quad x\;\equiv\;2 \pmod{5}$

Hence: .$\displaystyle x\:=\:2 + 5n$ for some integer $\displaystyle n.$

Substitute into the original equation: .$\displaystyle 5y + 9(2 + 5n)\:=\:13$

. . and we get: .$\displaystyle y\:=\:-(1 + 9n)$

The solutions are: .$\displaystyle \begin{Bmatrix}x\:=\:2 + 5n \\ y\:=\:-(1 + 9n)\end{Bmatrix}$ for any integer $\displaystyle n.$