1
$\begingroup$

What is asked?

As the title suggests I'm trying to solve a very simple Linear Diophantine Equation: $$12x + 18y = 54$$

Also find an expression for all integer solutions

What have I done?

  • Firstly, I know that $ax+by = c$ has a solution $\iff$ gcd$(a,b \space | \space c)$
  • Secondly, I need to compute the gcd $ (18,12) = 6 $

$$18 = 1 \cdot 12 + 6$$ $$12 = 2 \cdot 6 + 0$$

Therefore, gcd(18,12) = 6

  • Does 6 | 54? Yes. Therefore the equation has integral solutions.
  • Okay, all good so far. But it's the next stage that sort of stumps me.

So we can rearrange to get: $$6 = 18 - (1 \cdot 12)$$

Now do I multiply through 9? Whats the next step? I also need to do a generalised form for all integers.

I have seen this thread How to find solutions of linear Diophantine ax + by = c?, and it is very helpful but every time I come up with a value for $x$ and $y$ it always makes the LHS = 0. But it obviously needs to = 54.

$$\text{Thank you!}$$

$\endgroup$
  • 1
    $\begingroup$ When I was young, I tried to find two points , then represent the solution as linear equation $\endgroup$ – openspace May 3 '16 at 7:03
  • 1
    $\begingroup$ Yes you multpily by $9$. You arrive at $-12\cdot9+18\cdot9=54$ from where $(x,y)=(-9,9)$ $\endgroup$ – Aritra Das May 3 '16 at 7:06
1
$\begingroup$

Another way is to simplify to $$2x+3y=9$$ Modulo 3, $$2x\equiv 0\pmod 3\implies x\equiv 0 \pmod 3\implies x:=3m$$ and modulo 2 $$y \equiv 1 \pmod 2 \implies y:=2n+1$$ $$6m+3(2n+1)=9=6(m+n)+3\implies m+n=1\implies m=1-n$$ Hence, $$x=3-3n,y=2n+1$$ for all integral $n$ is the family of solutions.

$\endgroup$
1
$\begingroup$

You've pretty much got it, you just need to equate coefficients with the Diophantine equation, so the multiplier of 12 becomes $x$ and likewise, the multiplier of 18 becomes $y$

    $6=1\times18-1\times12$
    $54=9\times18-9\times12$ (multiplying by 9)

$ \Rightarrow x=-9, y=9$ (equating coefficients)
that's your solution

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.