# 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 $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
• May 15th 2006, 10:33 AM
ThePerfectHacker
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.
• 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: $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.$