Smallest $x+y$ for integer equation $n = 5x + 3y$ in closed form

Question

What is the smallest value of $x + y$ that satisfies $n = 3x + 5y$, if such $(x, y)$ exists, in a closed form, where all variables are natural numbers? (Such solution does not exist for $n=1$, $n=2$, $n=4$ or $n=7$) I am given that $\left\lfloor \frac{n + 2 (2n\ \mathrm{mod}\ 5)}{5} \right\rfloor$ is the solution.

I was able to show that $y \in \{0, 1, 2, 3, 4\}$, as $3y \equiv n\ (\mathrm{mod}\ 5)$ and $\mathrm{gcd}(3, 5) = 1$. But I couldn’t figure out how to get $x$ in closed form.

Any help or suggestions are appreciated. Thanks!

Answer 1

The integer solutions of $n = 5x + 3y$ are given by $x=3t-n$, $y=-5t+2n$, with $t \in \mathbb Z$.

To minimize $x+y=-2t+n$, we need to maximize $t$.

Now:

• $x\ge0\ $ iff $\ 3t \ge n$.

• $y\ge0\ $ iff $\ 2n \ge 5t$.

• $x+y\ge0\ $ iff $\ n \ge 2t$.

These gives $ \frac{n}{3} \le t \le \frac{2n}{5} \le \frac{n}{2} $.

Therefore, $ t \le \left\lfloor\frac{2n}{5} \right\rfloor$ and so the smallest value of $x+y$ is $-2\left\lfloor\frac{2n}{5} \right\rfloor+n$.

Answer 2

So we have:

$$n=3x+5y\Rightarrow n=5x+5y-2x \Rightarrow 5(x+y)=n+2x \Rightarrow x+y=\frac {n+2x}{5}$$

$x$ and $y$ are both natural numbers. Hence their addition $x+y$ is too a natural number. So $ \frac {n+2x}{5}$ must be a natural number too. In order for that to happen must $(n+2x)\mathrm{mod} 5=0$ which only happens when $2x=kn\ \mathrm{mod}\ 5 \Rightarrow x= \frac{kn\ \mathrm{mod}\ 5}{2} $, where $k$ is a natural number that we don't know the value yet, and now $x+y = \frac { n + ( kn\ \mathrm{mod}\ 5 ) }{5}$. But as we know x is natural number. Which means that we must be sure that $n\ \mathrm{mod}\ 5$ is divided by 2. So from here we find out that $k=2$ and $ 2x=\left\lfloor 2n\ \mathrm{mod}\ 5 \right\rfloor $.

After all we have:

$x+y$ smallest value is $ \left\lfloor\frac {n+(2n\ \mathrm{mod}\ 5)}{5}\right\rfloor$, when $x= \left\lfloor \frac{2n\ \mathrm{mod}\ 5}{2} \right\rfloor$.