3

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

math-traveler
  • 983
  • 3
  • 9
  • 1
    Hint: If $(a,b)$ and $(c,d)$ are solutions then $a-c$ is divisible by $13$ and $b-d$ is divisible by $8$. You should specify whether you are allowing $0$ to be a natural number or not. – lulu Sep 19 '20 at 14:19
  • @lulu I am not sure that I had to point that. By defaut there is no 0 in set of natural numbers – math-traveler Sep 19 '20 at 14:32
  • 1
    There is no "default". People simply don't agree as to the definition of the natural numbers...some authors include $0$ and some don't. If you want to exclude it, you should specify that. – lulu Sep 19 '20 at 14:33

2 Answers2

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.

lhf
  • 216,483
  • I guess it has something to do with extended Euclid's algorithm. But could you, please, descibe a bit more detailed how did you get these equations? – math-traveler Sep 19 '20 at 14:34
  • @math-traveler, exactly. The extended Euclid's algorithm gives $8 \cdot 5 + (-3) \cdot 13 =1$. – lhf Sep 19 '20 at 14:35
  • And how do we understand what the limits are? I mean it is obvious that $13t + 5n \geq 1$ and $-8t - 3n \geq 1$. I tried to draw it on graph but it didn't help much, Maybe analytical approach should be preffered? – math-traveler Sep 19 '20 at 15:01
  • 1
    Do we have to require $\frac{-1-3x}{8} - \frac{-1 - 5x}{13} \geq 9$ ? – math-traveler Sep 19 '20 at 15:15
  • Oh, seems like I finally figured it out. Thank you for hints!) – math-traveler Sep 19 '20 at 16:09
1

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

G Cab
  • 35,272
  • Oh, it is really cool that there is special theorem for that. Could you, please, explain how do you find inverse element so fast? – math-traveler Sep 19 '20 at 16:22
  • 1
    @math-traveler: for small numbers like these the modular inverse can be found quite easily with a few guesses, otherwise you shall resort to extended Euclidean algorithm. – G Cab Sep 19 '20 at 16:47