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

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.

• One quick rewrite is to say that $mn\mid (8m+1)(8n+1)$, not that the result is much easier to use... – abiessu Apr 11 at 13:49
• You forgot $(1,1)$, and there is also $(9,73)$. – Christian Blatter Apr 11 at 15:00
• Yes, you are right. All solutions given satisfy that one of the integers, suppose is $m$ satisfy $8m+1$ is a square or $8m+1 = n$. I suppose it is general property in all solutions but I don't know how to proceed. – mguzyay Apr 11 at 15:12

## 4 Answers

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

Proceed as follows:

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

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

From $$m 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)$$.

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

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, m=?$$

Case$$\#3:$$

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

$$n=\dfrac{13}{5a-64}\implies a\in, 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, m=?$$