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$
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$
  • $\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 '15 at 17:17
  • $\begingroup$ you are welcome :) $\endgroup$ – Shobhit Jan 26 '15 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 '15 at 17:25
  • $\begingroup$ look at the edited answer:) $\endgroup$ – Shobhit Jan 26 '15 at 18:37

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.