Find $n$ such that there are $11$ non-negative integral solutions to $12x+13y =n$

Question

What should be the value of $n$, so that $12x+13y = n$ has 11 non-negative integer solutions?

As it is a Diophantine equation, so we check whether the solution exists? it exists if $gcd(12,13)|n$ that is $1|n$ and hence integer solutions to $12x+13y = n$ exist.

To find the solutions explicitly, we write $1 $ as the linear combinations of $12$ and $13$ that is $1 = 12(1) + 13(-1)$, next we write $n = 12(n) + 13(-n)$ so that the integer solutions to $12x+13y = n$ is $x = n + t(12)$ and $y = -n + t(13)$. To check for non-negative integral solutions, $x \geq 0$ and $y \geq 0$ so that $t \geq -\frac{n^2}{12}$ and $t \geq \frac{n^2}{13}$ so $t \geq \frac{n^2}{13}$. But now I am struggling how to relate this to the 11 number of non-negative integral solutions?.Any help?

Answer 1

If $(x,y)$ and $(x',y')$ are two of the eleven solutions, then $x'=x+13t$, $y'=y-12t$ for some integer $t$. Hence the $11$ solutions will be of the form $x=x_0+13t$, $y=y_0-12t$ with $t$ ranging over $11$ consecutive integers, wlog over the integers $\{0,1,\ldots,10\}$. As $t=-1$ does not lead to a solution, we conclude $x_0-13<0$. As $t=11$ does not lead to a solution, we conclude $y_0-11\cdot 12<0$, i.e. $x_0<13$ and $y_0<132$. On the other hand $t=0$ and $t=10$ do lead to solutions, so $x_0\ge0$ and $y_0\ge120$. For any choice of $x_0\in\{0,1,\ldots, 12\}$ and $y_0\in\{120,121,\ldots, 131\}$, letting $n=12x_0+13y_0$ will lead to exactly $11$ non-negative integer solutions (and for no other $n$).

Answer 2

Note that from the following hint

$$-1\cdot 12+1\cdot 13=1 \implies (-1+k \cdot 13)\cdot 12+(1-k\cdot 12)\cdot 13=1$$

we have

$$-n\cdot 12+n\cdot 13=n \implies (-n+k \cdot 13)\cdot 12+(n-k\cdot 12)\cdot 13=1$$

and we need

• $-n+k \cdot 13\ge 0$

• $n-k\cdot 12\ge 0$

that is

$$\frac n{13}\le k\le\frac n{12}$$

which leads to $n=10\cdot 12\cdot13$ with

$$12x+13y=10\cdot 12\cdot13$$

which has the following solutions

$$x=13k \quad y=120-12k \quad k=0,1,2,\ldots,10$$

Answer 3

$12x + 13y = n$

$12(-n)+13(n)=n$ implies $x(t)=-n+13t$ and $y(t)=n-12t$

$x(t) \ge 0 \implies t \ge \dfrac{n}{13}$

$y(t) \ge 0 \implies t \le \dfrac{n}{12}$

So $\dfrac{n}{13} \le t \le \dfrac{n}{12}$

The existence of $11$ solutions implies $$\text{$\dfrac{n}{13} \le t_0$ and $t_0 + 10 \le \dfrac{n}{12}$} \tag{1}$$

That is, $$\dfrac{n}{13} \le t_0 \le \dfrac{n-120}{12}\tag{2}$$ for some integer $t_0$.

We find $12n \le 156t_0 \le 13n - 1560$

Or $$0 \le 1560t_0-12n \le n - 1560 \tag{3}$$

So $n \ge 1560$.

For $n = 1560$, condition $(3)$ becomes $0 \le 1560t_0-12n \le 0$. So $t_0 = 120$.

It follows that $12x+13y = 1560$ has solutions,

$\{(0, 120), (13, 108), (26, 96), (39, 84), (52, 72), (65, 60), (78, 48), (91, 36), (104, 24), (117, 12), (130, 0)\}$

That is to say, $n = 1560$.