2
$\begingroup$

I have to solve this Diophantine equation: $6x+9y=1050$, where $x,y \in\mathbb{N}$. I am not sure as to how to solve this for only the whole numbers, but I think I'm doing it right. I used the extended Euclidean algorithm to get these 2 equations and the $GCF(9,6)$:

$GCF(9,6) = 3$

$3 = 9(1)+6(-1)$

$0 = 9(-2) + 6(3)$

So in order to get the solutions to this equation, I divided the $1050$ with $GCF$ and got $\frac{1050}{3} = 350$ and then inserted it into the equation:

$1050 = 6\cdot350\cdot(-1)+9\cdot350\cdot(-1)$

Therefore, $x = -350$ and $y=350$. But the problem is, I have to solve for $x,y \in\mathbb{N}$, which $x$ is clearly not.

Now I did this step I've found, but I'm unsure if I did this correctly, am I doing this right? Here we go; I multiplied the $0 = 9(-2) + 6(3)$ with $k$ and got: $0 = 9(-2k) + 6(3k)$

I also multiplied the $3 = 9(1) + 6(-1)$ with $350$ and got: $1050 = 9(350)+6(-350)$

then I put them together: $1050 = 9(350-2k) + 6(-350 + 3k)$

And this is where I find the solutions to $x,y$;

$x = -350+3k$ and $y = 350-2k$

Does that mean these two solutions are correct for $x,y \in \mathbb{N}$? Also side question, how can I find the solution, where the sum of $x+y$ is the smallest? I'd appreciate any help whatsoever!

$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Yes those are correct, you just need a bound for $k$ which can be calculated using

$x \ge 1, y\ge 1$ or $3k-350 \ge 1, 350-2k \ge 1$

also, $2x+3y=350 \implies 2(x+y)=350 -y$, to find the minimum value of $x+y$ calculate maximum value of $y$

Can you take it from here?

$\endgroup$
4
  • $\begingroup$ Thanks! This is the step I was missing. One note; we actually said that we can use $0$ as a whole number in discrete structure classes, so I have to check $x\ge0$.. $\endgroup$
    – peroxy
    Jan 26, 2015 at 17:17
  • $\begingroup$ you are welcome :) $\endgroup$
    – Shobhit
    Jan 26, 2015 at 17:19
  • $\begingroup$ So I found out that there are $60$ solutions, $116 \le k \le 175$. Do you know how I can find the right solution, where the sum of $x+y$ is the smallest? $\endgroup$
    – peroxy
    Jan 26, 2015 at 17:25
  • $\begingroup$ look at the edited answer:) $\endgroup$
    – Shobhit
    Jan 26, 2015 at 18:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .