Find all pairs $(m, n)$ of positive integers such that $m$ divides $8n+1$ and $n$ divides $8m+1$

Question

I've found the pairs $(1,3),(1,9),(3,25)$ and $(13,21)$ up to order. But I have no idea how to prove that there are not other solutions. Any hints...? I've been trying for a few days but all I came up with is that seems that $8m+1$ or $8n+1$ is a square.

Answer 1

Here is a solution based on the @abiessu's suggestion.

If $m\mid 8n+1$ and $n\mid 8m+1$, then $mn\mid (8m+1)(8n+1)$. In view of $$ (8m+1)(8n+1) = 64mn+8m+8n+1, $$ this implies $mn\mid(8m+8n+1)$. As a result, $mn\le 8m+8n+1$; equivalently, $(m-8)(n-8)\le 65$.

It follows that either $\max\{m,n\}\le 73$, or $\min\{m,n\}\le 8$. In either case we are left with a finite number of pairs to check; this is obvious in the first case where $\max\{m,n\}\le 73$, while in the first case, for each $m\le 8$ we must check only those $n$ dividing $8m+1$. Checking all these pairs, there are six solutions with $m\le n$ altogether: $$ (1,1),\ (1,3),\ (1,9),\ (3,25),\ (9,73),\ \text{and}\ (13,21). $$

Answer 2

Proceed as follows:

If $m=n$, it is easy to check that $(1,1)$ is the only solution.

Assume WLOG that $1\leq m<n$ and let $p$ and $q$ be positive integers such that \begin{align*} 8n+1 &= pm\\ 8m+1 &= qn. \end{align*}

From $m<n$ we get $qn=8m+1<8n+1$. Hence, $n(8-q)+1>0$. Since $n>1$, this is only possible when $q\leq 8$. So all is left is to consider cases $q\in\{1, 2, \dots, 8\}$.

When $q=1$, we have $$8m+1=n.$$ Plugging this $n$ into $8n+1=pm$, we have $$64m+9=pm$$ or $$m(p-64)=9.$$ Because $m,p$ are positive integers, there are only a few possibilities here, namely, $m=1, m=3$ or $m=9$. Each of which gives solutions $(1, 9), (3, 25)$ and $(9, 73)$ and the corresponding pairs swapped, i.e., $(9, 1), (25, 3)$ and $(73, 9)$.

Do the same for the other cases of $q$ and you will get a few more solutions, $(1, 3), (3, 1), (13, 21), (21, 13)$.

Answer 3

Solving $$jm=8n+1,\quad kn=8m+1$$ for $m$ and $n$ gives $$m={k+8\over jk-64},\qquad n={j+8\over j k-64}\ .\tag{1}$$ Since $m$, $n$, $j$, $k$ should all be $\geq1$ this at once enforces $jk\geq65$. But we can say more: $k+8\geq jk-64$ and $j+8\geq jk-64$ enforce $$jk\leq 64+8+\min\{j,k\}\leq80\ .$$ In this way we have shown that $65\leq jk\leq 80$, so that only a finite number of pairs$(j,k)$ have to be tested whether the pairs $(m,n)$ resulting from $(1)$ are pairs of natural numbers. Doing this search with a computer leads to the pairs $m\leq n$ given by $$(1,1), \quad(1,3),\quad(1,9),\quad(3,25),\quad(9,73),\quad(13,21)\ .$$

Answer 4

Let $8m+1=an, 8n+1=bm$

where $a,b$ are positive integers and are clearly odd and WLOG $a\ge b$

$$\dfrac m{a+8}=\dfrac n{b+8}=\dfrac1{ab-64}$$

Now $ab-64$ must be $\le b+8\le a+8$

$\iff72\ge b(a-1)$ which is $\ge b(b-1)$

$\iff0\ge b^2-b-72=(b-9)(b+8)\implies b\le9$

and $ab-64\ge1\iff ab\ge65$

Case$\#1:$

If $b=1;a\ge65$ and $m=1+\dfrac{72}{a-64}$

$n=\dfrac9{a-64}\implies a\in[65,67,73]$

Case$\#2:$

If $b=3;a\ge65/3>21$

$n=\dfrac{11}{3a-64}\implies a\in[25], m=?$

Case$\#3:$

If $b=5;a\ge65/5=13$

$n=\dfrac{13}{5a-64}\implies a\in[13], m=?$

Case$\#4:$

If $b=7;a\ge65/7>9\implies a\ge10$

$n=\dfrac{15}{7a-64}\implies a\in\emptyset$

Case$\#5:$

If $b=9;a\ge65/9>8\implies a\ge9$

$n=\dfrac{17}{9a-64}\implies a\in[9], m=?$