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
I'm not sure this is how you are expected to solve this, or even if thisOriginally 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
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.
Hello, delpin!
This is basically Captain Black's and Hacker's solutions ... in baby-talk.
First, reduce the equation: .$\displaystyle 5y + 9x\:=\:13$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.$