6. Find all pairs of natural numbers $m$ and $n$, such that $m+1$ is divisible by $n$ and $n^{2}-n+1$ is divisible by $m$.
Answer: $(m, n)=(1,1),(1,2)$ and $(3,2)$.

Solution. If $n=1$, then $m=1$, and this pair obviously works. We will assume that $n \geqslant 2$. Let $m+1=k n$. The numbers $m$ and $n$ are coprime, since if $d$ is their common divisor, then $1=(m+1)-m=k n-m$ is divisible by $d$. Moreover, $m \leqslant n^{2}-n+1 \leqslant n^{2}-1$, so $k n=m+1 \leqslant n^{2}$ and $k \leqslant n$. Note that

$$
n(n+k-1)=n^{2}-n+k n=\left(n^{2}-n+1\right)+(k n-1)
$$

is divisible by $m$. Then $n+k-1$ is also divisible by $m$. Therefore, $m \leqslant n+k-1 \leqslant$ $2 n-1$. Thus, $m+1$ does not exceed $2 n$ and is divisible by $n$. Therefore, $m+1=n$ or $m+1=2 n$. In the first case, $n^{2}-n+1=(m+1)^{2}-(m+1)+1=m^{2}+m+1$, and from the divisibility of $n^{2}-n+1$ by $m$ it follows that $m=1$ and $n=2$. This pair works for us. In the second case, $m \geqslant 3$ and $n^{2}-n+1=\left(\frac{m+1}{2}\right)^{2}-\left(\frac{m+1}{2}\right)+1=\frac{m^{2}+3}{4}$. From the divisibility of $n^{2}-n+1$ by $m$ we get that $m^{2}+3$ is also divisible by $m$ and, therefore, $m=3$ and $n=2$. This pair also works for us.