Seems a little straightforward. In $\mathbb{Z}_8$, $mn=-1$ has solutions $\{m,n\}=\{1,7\},\{3,5\}$ and in both cases $m+n=0$. In $\mathbb{Z}_3$, $mn=-1$ has solution $\{m,n\}=\{1,2\}$ and again $m+n=0$, so $24|m+n$.

Let $ m = 24k_1 + r_1$ and $ n = 24k_2 + r_2$ $ 0 \le r_1,r_2 <24$ Since $ 24|mn + 1 \rightarrow mn \equiv r_1r_2 \equiv 23$ ( mod $ 24$). Since $ 23$ is prime and $ r_1$ and $ r_2$ are integers then $ r_1 = 1$ and $ r_2 = 23$ (or $ r_1 = 23$ and $ r_2 = 1$). So $ m + n = 24k_1 + r_1 + 24k_2 + r_2 = 24(k_1 + k_2) + 1 + 23 = 24(k_1 + k_2 + 1)$ Quote: Seems a little straightforward. yeah it is

Wichking wrote: Since $ 23$ is prime and $ r_1$ and $ r_2$ are integers then $ r_1 = 1$ and $ r_2 = 23$ (or $ r_1 = 23$ and $ r_2 = 1$). you are wrong...if $ r_1=7 , r_2=17$ then $ r_1r_2\equiv23 (\mod 24)$

you are correct in fact there are 4 such pairs $ (1,23)$ $ (5,19)$ $ (7,17)$ $ (11,13)$ (we can show that these are the only such pairs and their sum is always 24)... but that makes my solution even more ugly

$24$ divides $mn+1$ and we see $m,n$ are both odd numbers of the form $2k_1 +1,2k_2+1$. We observe $m+n+mn+1 =(m+1)(n+1)$ =>$(2k_1+2)(2k_2+2) =4(k_1+1)(k_2+1) $ If $24$ divides $4(k_1+1)(k_2+1)$ then $6$ divides $(k_1+1)(k_2+1)$........($1$) =>$2$ divides $(k_1+1)$ or $(k_2+1)$ or both……..($2$) $24$ divides $(4k_1k_2+2(k_1+k_2)+2)$ which means $12$ divides $(2k_1k_2+k_1+k_2+1)$ $2$ divides $k_1+k_2+1$ so $k_1,k_2$ cannot both be odd or even. Either of them would be odd. Therefore $2$ divides $k_1+1$ or$k_2+1$ proving ($2$). $3$ divides $2k_1k_2+k_1+k_2+1$  $3$ divides $-k_1k_2+k_1+k_2+1=-k_1(k_2-1) +k_2+1$ If $3$ does not divide $k_2$ then $3$ divides $k_2-1$ or $k_2+1$. If $3$ divides $k_2-1$ then $3$ divides $k_2+1$ a contradiction. Therefore $3$ divides $k_2+1$. If $3$ divides $k_2$ then $3$ Divides $k_1+1$. $2$ divides $k_1+1$ or $k_2+1$ and $3$ divides $k_1+1$ or $k_2+1$ $6$ divides $(k_1+1)(k_2+1)$ Thus proving ($1$ )

A related problem: If $mn+1$ is divided by k,then $m+n$ is divided by k. Find the maximimu of $k$.($k_{max}=24$)

My solution: here

mod3, mod8

Since mod $3$ is easy I'll only check mod $8$. Note that $\gcd(2,mn)=1$, so we can write $n\equiv -\frac 1m \pmod 8$. We need to prove $m-\frac 1m\equiv 0 \pmod 8$, which is obvious by casework.