Exercise 12. Determine all pairs of strictly positive integers $(m, n)$ such that

$$
\mathrm{mn}-1 \mid \mathrm{n}^{3}-1
$$
Solution to Exercise 12 Note that the pairs $(1, n)$ and $(m, 1)$ are solutions for all strictly positive integers $m$ and $n$. We assume in the following that $m, n \geqslant 2$.

Note that the numbers $\mathrm{mn}-1, \mathrm{n}^{3}-1$ are strictly positive. The divisibility condition therefore implies that $m n-1 \leqslant n^{3}-1$, so $m \leqslant n^{2}$.

We start by bringing a bit of symmetry to the problem by noting that $\mathrm{mn}-1$ divides $(\mathrm{mn})^{3}-1^{3}$, so $m n-1$ divides $(m n)^{3}-1-m^{3}\left(n^{3}-1\right)=m^{3}-1$.

Now that the problem is completely symmetric in $m$ and $n$, we can assume without loss of generality that $m \geqslant n$. Since $m n-1$ divides $n^{3}-1$ and $m n-1$, it also divides $n^{3}-1-$ $(m n-1)=n\left(n^{2}-m\right)$. Since $m n-1$ and $n$ are coprime, by Gauss's lemma, $m n-1$ divides $n^{2}-m$. But then, if $n^{2}-m$ is non-zero, since $m \geqslant n$ and $m \geqslant 1$,

$$
0<\mathrm{n}^{2}-\mathrm{m}<\mathrm{mn}-1 \leqslant \mathrm{n}^{2}-\mathrm{m}
$$

which is impossible. Therefore, we have $n^{2}=m$. Conversely, the pair $\left(n^{2}, n\right)$ is indeed a solution $\left(n^{2}, n\right)$. Thus, the solution pairs are $\left\{(1, n),(n, 1),\left(n^{2}, n\right),\left(n, n^{2}\right)\right\}$.

## Alternative Solution:

As before, we reduce to the case where $n \geqslant 2$.

Let $(m, n)$ be a solution. Therefore, there is an integer $a$ such that $n^{3}-1=a(m n-1)$. Passing modulo $n$, we get $-1 \equiv-a(\bmod n)$, or $a \equiv 1(\bmod n)$. Write $a=k n+1$.

Substituting back, we get $n^{3}-1=(k n+1)(m n-1)=k m n^{2}+(m-k) n-1$, which simplifies to $\mathrm{n}^{2}=\mathrm{kmn}+\mathrm{m}-\mathrm{k}$.

Passing modulo $n$ again gives us $m \equiv k(\bmod n)$, so if $m=n p+r$ and $k=n q+r^{\prime}$ are the Euclidean divisions of $m$ and $k$ by $n$, we have $r=r^{\prime}$. We rewrite the equation as $n^{2}=$ $(n p+r)(n q+r) n+n p+r-(n q+r)$, which can be simplified again:

$$
n=p-q+n^{2} p q+n r(p+q)+r^{2}
$$

If $\mathrm{p} \geqslant 1$, then $\mathrm{n}=\mathrm{p}-\mathrm{q}+\mathrm{n}^{2} \mathrm{pq}+\mathrm{nr}(\mathrm{p}+\mathrm{q})+\mathrm{r}^{2} \geqslant \mathrm{n}^{2} \mathrm{q}-\mathrm{q}=\mathrm{q}\left(\mathrm{n}^{2}-1\right)$. Thus, if $\mathrm{q} \geqslant 1$, we need $n \geqslant n^{2}-1$, which is impossible since $n \geqslant 2$.

We have just shown that at least one of the numbers $p$ and $q$ must be zero.

If $p=0$ and $q \geqslant 1$, we have $n=q(n r-1)+r^{2}$. Since $r=m \geqslant 1, n r-1 \geqslant 1$ so $q(n r-1) \geqslant n r-1$ so $\mathrm{n}=\mathrm{q}(\mathrm{nr}-1)+\mathrm{r}^{2} \geqslant(\mathrm{nr}-1)+1=\mathrm{nr} \geqslant \mathrm{n}$. All these inequalities are therefore equalities, which implies $\mathrm{q}=\mathrm{r}=1$. We thus get $\mathrm{m}=1$.

If $q=0$ and $p \geqslant 1$, we have $n=p(n r+1)+r^{2}$. Thus, if $r \geqslant 1$, we have $n \geqslant n+2$, so $r=0$, then $n=r$ and finally $m=n^{2}$.

If $\mathrm{p}=\mathrm{q}=0$, we have $n=\mathrm{r}^{2}$ and $\mathrm{m}=\mathrm{r}$.

Thus, the solutions are the pairs $(1, n)$ and $\left(n^{2}, n\right)$ for all $n \geqslant 1$, as well as the pairs $\left(r, r^{2}\right)$ with $r \geqslant 1$. We verify conversely that all these pairs are solutions, and that $n=1$ gives the same solutions (since a priori these are only the solutions with $\mathrm{n} \geqslant 2$ ).

Graders' Comment: The exercise is generally well done. Many students forget to handle the special cases of their reasoning, but in such a problem it is precisely the special/degenerate cases that provide the solutions.