Find the least possible natural n such that $8x + 13y = n$ will have exactly 9 solutions in natural numbers

Question

Well, to approach this, we firstly should understand what is $gcd$ of 8 and 13. It is 1, so we do not require $n$ to have any divisibility properties. Means that we did not shorten our first range at all. Of course we can do some "binary search" over natural numbers and shorten our search range like that but is there a mathematical way to solve it?

Note: there is no 0 in natural numbers

Answer 1

Hint: The general solution of $8x + 13y = n$ is $x=13t+5n$, $y=-8t-3n$ with $t \in \mathbb Z$. The requirement that $x,y \in \mathbb N$ imposes limits on $t$. To count how many $t \in \mathbb Z$ are possible, it is important to know whether $0 \in \mathbb N$.

Here is the solution had in mind:

$x\ge1$ and $y\ge1$ iff $t \in [\frac{1-5n}{13},\frac{-1-3n}{8}]$. This interval has length $L=\frac{n-21}{104}$. Let $N$ be the number of integers in the interval. Then

• If $L \le 7$, then $N\le 8$

• If $L > 9$, then $N>9$

• If $L = 8$, then $N=9$ iff one of the extremes of the interval is an integer

• If $L =9$, then $N=9$ iff none of the extremes of the interval is an integer

Now $L=8$ iff $n=853$ and in this case the interval is $[-328,-320]$. So $N=9$ for $n=853$, which is the smallest solution.

Answer 2

There is an interesting theorem (alas not much known) attributed to Popoviciu, which tells that the number of solutions $ p_{\left\{ {a,b} \right\}} (n)$ in the first quadrant of the diophantine line $ax+by=n$ is $$ \eqalign{ & p_{\left\{ {a,b} \right\}} (n) = \left| {\,\left\{ \matrix{ 0 \le x,y,a,b,n \in \mathbb Z \hfill \cr \gcd (a,b) = 1 \hfill \cr ax + by = n \hfill \cr} \right.\;} \right| = \cr & = {n \over {ab}} - \left\{ {{{b^{\,\left( { - 1} \right)} n} \over a}} \right\} - \left\{ {{{a^{\,\left( { - 1} \right)} n} \over b}} \right\} + 1 \cr} $$ where $$ \eqalign{ & \left\{ x \right\} = x - \left\lfloor x \right\rfloor \cr & b^{\,\left( { - 1} \right)} b \equiv 1\;\left( {\bmod a} \right) \quad a^{\,\left( { - 1} \right)} a \equiv 1\;\left( {\bmod b} \right) \cr} $$

In our case this gives $$ \eqalign{ & 13^{\,\left( { - 1} \right)} 13 \equiv 1\;\left( {\bmod 8} \right) \quad \Rightarrow \quad 13^{\,\left( { - 1} \right)} = 5 \cr & 8^{\,\left( { - 1} \right)} 8 \equiv 1\;\left( {\bmod 13} \right) \quad \Rightarrow \quad 8^{\,\left( { - 1} \right)} = 5 \cr} $$ and therefore $$ \eqalign{ & p_{\left\{ {8,13} \right\}} (n) = {n \over {8 \cdot 13}} - \left\{ {{{5n} \over 8}} \right\} - \left\{ {{{5n} \over {13}}} \right\} + 1 = 9\quad \Rightarrow \cr & \Rightarrow \quad n = 8^{\,2} \cdot 13 = 832 \cr} $$

The line equation becomes $$ 8x + 13y = 8^{\,2} \cdot 13\quad \Rightarrow \quad {x \over {13}} + {y \over 8} = 8 $$ with the nine solutions being $$ \left( {0,64} \right),\left( {13,56} \right), \cdots ,\left( {104,0} \right) $$

If you want to consider only positive integral solutions $1 \le x,y \in \mathbb Z$ then it is just a matter to make a shift $$ \eqalign{ & ax + by = n\quad \Rightarrow \cr & \Rightarrow \quad a\left( {\left( {x + 1} \right) - 1} \right) + b\left( {\left( {y + 1} \right) - 1} \right) = n\quad \Rightarrow \cr & \Rightarrow \quad a\left( {x + 1} \right) + b\left( {y + 1} \right) = n + a + b = m \cr} $$ so that the new minimum $n$ becomes $853$.