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

Printable View

- May 15th 2006, 04:02 AMdelpinLinear 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

Thanks in advance - May 15th 2006, 05:04 AMCaptainBlackQuote:

Originally Posted by**delpin**

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 AMThePerfectHacker
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 PMdelpinThank you
For your help... most appreciated

- May 28th 2006, 07:04 AMSoroban
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$

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