For an integer $n$ I would like to find all integers $m$ with $n/2<m<n$ and $$ \frac{mn+1}{n-m} $$ an integer, that is, $$ mn\equiv-1\pmod{n-m}. $$
How can I find these $m$? I could just check each $m$ in the range, but that is slow -- $\Omega(n)$ -- for $n$ large, and I'd like to do this for many $n$.
Of course with a fixed modulus this would be easy -- just compute $-1/n$ with the extended Euclidean algorithm.
Sorry, this ends up being pretty easy: find the divisors $d$ of $n^2+1$ which are less than $n/2$ and let $m=n-d$ for each.