1
$\begingroup$

Given $$5x+7y=c$$What is the largest value of c for which there exists exactly 3 solutions (x,y)? I've tried researching how to find the exact number of positive integer solutions for linear diophantine equations but didn't find it much help. How would I solve this type of problem?

I believe the answer is supposed to be 140.

$\endgroup$
  • $\begingroup$ You mean: For which $c$ are there exactly three non-negative (x,y) solutions? $\endgroup$ – imranfat Oct 15 '15 at 3:13
  • $\begingroup$ I believe the question is asking for the highest value of c possible for three non negative solutions. $\endgroup$ – Jonathan Oct 15 '15 at 3:16
  • $\begingroup$ $140$ sounds too high: $(x,y) = (0,20), (7,15), (14,10), (21, 5), (28,0)$. Maybe you mean positive rather than nonnegative? $\endgroup$ – Erick Wong Oct 15 '15 at 3:47
  • $\begingroup$ This was a question from a math contest, so I was just trying to remember from my head. I think you are right. It was probably positive. $\endgroup$ – Jonathan Oct 15 '15 at 3:49
1
$\begingroup$

To get the answer of 140 you must mean positive integers rather than non-negative. If you really mean non-negative the analysis would be similar but use $\geq$ and $\leq$ rather than $>$ and $<$.

A solution to $5x+7y=1$ is (-4,3) so a solution to $5x+7y=c$ is (-4c,3c) so the general solution is $(-4c+7n,-3c+5n)$. We want positive solutions so we need $-4c+7n>0$ and $-3c+5n>0$ or in other words: $$\frac{4c}{7}<n<\frac{3c}{5}$$ For the largest c such as we get only 3 solutions consider what is required to get 4 solutions: $$\frac{4c}{7}<n<n_2<n_3<n_4<\frac{3c}{5}$$ For only 4 solutions these will be sequential. I.e. $n_4=n+3$ $$\frac{4c}{7}<n<\frac{3c}{5}-3$$ So we want to find the largest $c$ which doesn't have unique integer solution to the inequality (as we don't want to get 4 solutions).

For no unique solution and maximal $c$ we want the two sides of the inequality to be consecutive integers. $$\frac{4c}{7}=\frac{3c}{5}-3-1$$ $$20c=21c-140$$ $$c=140$$

$\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.