Linear Diophantine Equations

**delpin** · May 15th 2006, 04:02 AM

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

Thanks in advance

**CaptainBlack** · May 15th 2006, 05:04 AM

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 $3$ and rearrange to get:

$ 5y+9x-13=0 $

Now this gives:

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

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

$ 4 x=5\lambda+3 $

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

$ 4x=10\mu+8 $

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

$ x=5\kappa+2 $

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

$ y=-9 \kappa-1 $

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

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

is a solution.

RonL

**ThePerfectHacker** · May 15th 2006, 10:33 AM

Use the following theorem,
Given a diophatine equation with $\gcd(a,b) |c$
$ax+by=c$
and $x_0,y_0$ is a particular solution
Then all solutions and every solution is,
$x=x_0+\frac{b}{d}t$
$y=y_0-\frac{a}{d}t$
for an integer $t$
------
You have,
$15y+27x=39$
You can leave it the way it is but I suggest to divide by 3,
$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 $y=-1$ and $x=2$ work.
Also $\gcd(5,9)=1$ which divides 13.
Thus, all solutions are,
$y=-1+9t$
$x=2-5t$

Note it might look different from CaptainBlack's but they are both equivalent.

**delpin** · May 15th 2006, 12:21 PM

For your help... most appreciated

**Soroban** · May 28th 2006, 07:04 AM

Hello, delpin!

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

I'm looking for help on solving Linear Diophantine Equation: $15y + 27x \:= \:39$

First, reduce the equation: . $5y + 9x\:=\:13$

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

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

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

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

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

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

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

Thread: Linear Diophantine Equations

LinkBack

Thread Tools

Display