In the Diophantine equation, 5x + 17y = c

Question

In the Diophantine equation, 5x + 17y = c where c is the smallest value of the equation where x and y are both positive integers and every number larger than c can also be written in the form of 5x + 17y where x and y are positive. How can I find the value of c?

Edit: apologize for not making it clear. This c needs to be the number where any number greater than c can be denoted with 5x + 17y and x, y are positive integers. For example, you cannot denote 51 with x, y both being positive, then c must be a number larger than 51.

Answer 1

17=5k+2, 34=5k+4, 51=5k+1, 68=5k+3, 85=5k+0

90 is the first number of the form of 5k that could be written in a form of $5a+17b$, where $a$ and $b$ are positive integers

So c=86 since all integers larger or equal to 86 you can get by adding a multiple of 5 to one of {17,34,51,68,85}. And 85 can't be written in that form.

Answer 2

This is a variation of the Frobenius coin problem.

Your question can be phrased as:

Consider the expression $5x + 17y$, where $x$ and $y$ are positive integers. What is the smallest number $c$ such that this expression does take on $c$ and all greater values?

The Frobenius coin problem, on the other hand, asks:

Consider the expression $5a + 17b$, where $a$ and $b$ are nonnegative integers. What is the largest number $d$ such that this expression does not take on $d$, but does take on all greater values?

First, let's solve the Frobenius coin problem, then let's modify the solution to fit the original question.

Wikipedia gives a formula for the answer to the Frobenius coin problem: it's $d = 5 \cdot 17 - 5 - 17$, or $d = 63$.

The first difference is that the original question states that $x$ and $y$ are positive, instead of stating that $a$ and $b$ are nonnegative. But if $x = a + 1$ and $y = b + 1$, then these requirements end up being equivalent. So the original expression, $5x + 17y$, is equivalent to $5(a + 1) + 17(b + 1)$, or $5a + 17b + 22$.

We're almost ready to conclude that the answer is $c = d + 22 = 85$. But there's one more thing we need to take care of.

The original question asks for the smallest number $c$ such that $c$ and all greater numbers are values of the expression. The Frobenius coin problem gives us a number which is one less than that. So we need to add $1$, giving $c = 86$ as the final answer.

Answer 3

There is no solution for $c=85$

Consider the $(x,y,c)$ solutions $$(7,4,86)$$ $$(14,1,87)$$ $$(4,4,88)$$ $$(11,2,89)$$ $$(1,4,90)$$

Each of the five consecutive $c$ can be increased by $5$ by increasing $x$ by $1$, to give the next five values, and then repeat as needed.

Your answer is $c=86$

Answer 4

A gentle approach:

We know by Bezout that we can solve $5m + 17n = 1$.

And therefore if we have $5x + 17 y = c$ we can always do $5(x + m) + 17(y + n) = c + 1$.

However it's pretty clear that if $5m + 17n =1$ that one of $m$ or $n$ is positive and the other negative. So to go from $5(x+m) + 17(y +n) = c+1$ we must decrease one value and it may be that we decrease it to less than $0$.

However if we have a $5m + 17n =1$ where $m > 0$ and $n < 0$ we can also have $5(m -17) + 17(n+5) = 1$ and by subtracting enough enough multiples of $17$ from $m$ and adding enough multiples of $5$ to $n$ we will eventually get a $5u + 17w = 1$ where $u < 0$ and $w > 0$

So we can go from $5x + 17y = c$ to either $5(x+m) + 17(y+n)=c+1$ or $5(x + u) + 17(y+w) = c+1$. That way if $y$ isn't large enough to add the negative $n$ to we can instead add the positive $w$ and instead add the negative $m$ to $x$.

[We should take a brief moment to point out that be subtracting/adding multiples of $17$ from $m$ and adding/subtracting multiples of $5$ from $n$ we can safely assume $5m + 17n = 1; 1\le m < 17; -1 \ge n< -5$ and $5u + 17w =1; -1\ge u< -17; 1\le w < 5$.]

[This also allows us to assume $u + 17 = m$ and $w -5 = n$.]

[Note $m = 7; n =-2$ and $u=-10; w = 3$ and $1 = 5*7-2*17 = 5*(-10) + 17*3 $. But We don't actually have to solve those to answer the question.]

It $c$ is large enough, we can rest easy knowing that either $x > |u|$ or $y > |n|$ and so we can always slip from $c$ to $c+1$ without having to resort to negative values.

But if $c$ is not large enough, it could be possible that both $x \le |u|$ and $y\le |n|$ and then both $5(x+m) + 17(y+n)=c+1$ and $5(x + u) + 17(y+w) = c+1$ would result in negative values.

So how large is "large enough"?

Note if $c = 5*17 = 85$ then we have (among more extreme values) $x = 17; y = 0;5x + 17y = 85$ and $x = 0;y=5;5x + 17y=85$ as solutions. But we can't increase them both to positive values as that require decreasing one to a zero or negative value. So $c = 85$ is not large enough.

But if $c \ge86$ that is large enough.

We can get $c = 86 = 5(17+u) + 17(0 + w) = 5(0+m) + 17(5+n) $.

And if $5x + 17y = c \ge 86 = 85 +1 = 85 + 5u + 17w = 85 +5n + 17m$. Then either $x > |u|$ and we can afford to add $u$ to $x$ to get $c+1$., or $y> |n|$ and we can afford to add $n$ to $y$ to get $c + 1$ (or both).

So the answer is $c = 86$.

=== old answer ===

The trick is to realize that if $5x + 17y = c$ is one way to get $c$ then $5(x \pm 17) + 17(y \mp 5) =c$ is another way to get $c$. Via induction $y' = y\pm 7k$ and $x' = x \mp 5k$ for all $k\in \mathbb Z$ are solutions and because $5,17$ are relatively prime they are the only solutions[*].

So if $5x + 17y = c$ we can assume without loss of generality that $0< x \le 17$.

That means $y$ is positive if and only if $c > 5x$.

Now we do know that $5x + 17y = c$ will have integer solutions for all integers $c$ [!] but $y$ might be $0$ or negative if we solve so that $0 < x \le 17$. But if $c \ge 36$ we are good because $c > 86 = 17*5 \ge 5x$.

And $c$ must be at least $36$ because $c = 85 = 5*17 + 17*0 = 5*0 + 17*5$ can not be solved with only positive integers. (If we increase $x$ we must decrease $y$ and vice versa.)

[*]. If $5w + 17 u = c$ and $w = x + d$ for some integer $d\ne 0$ then $5w + 17u = 5(x+d) + 17u = 5x + 17y$ so $5d = 17(y-u)$. So $17|5d$ but $17$ and $5$ are prime so $17|d$. Let $d = 17k$ then $5k =y-u$. So $w = x + 5k; u = y - 17k$

[!] . By Bezout we know there are solutions to $5m + 17n = 1$. So $x = mc; y = nc$ will be a solution to $5x + 17y = c$.

POST-SCRIPT: So you might be wondering. If we have $5x + 7y = c$ how do we solve for $5w + 7u = c+1$.

Solve for $5m + 17n = 1$. Use Euclid's algorithm or just do it by trial and error. $2*17 = 34$ so $5*7 + 17(-2)$ work. That is $m > 0 > n$. To get a second $n > 0 > m$ we can add $5$ to $-2$ and subtract $17$ from $7$. $5(7-17) + 17(-2 + 5) = 5*(-10) + 17*3 = 1$.

So if $5x + 7y=c$ then $5(x-10|x+7) + 7(y+3|y-2)= c+1$. If $c \ge 86$ this will always work. If $x \le 10$ then $y >2$ and if $y \le 2$ then $x > 10$.