It is clear that the same method will work for this.

It seems that if $m$ is a prime then $b(n,m)=1$ iff $n=(m^k-1)/(m-1)$ for $k\in\mathbb{N}$.

@ASP I think that the best idea is to check the papers cited in Badziahin's paper and the papers which cite it.

You should consult the paper of D. Badziahin (Finding special factors of values of polynomials at integer points, Int. J. of Numb. Theor., V. 13(1), 2017), where slightly more general problem was considered, i.e., the existence, for a given polynomial $P$, divisors $d$ of $P(n)$ such that $d\equiv 1\pmod{n}$.

A similar problem stated by Erdos and Graham was investigated in: M. Ulas, A. Schinzel, A note on Erdos–Straus and Erdos-Graham divisibility problems (with an Appendix by Andrzej Schinzel), Int. J. Number Theory vol. 9 (3) (2013), 583-599.

@Gautam My parametrization is invertible over $\mathbb{Q}$ but not necessarily modulo $N$. Indeed, the inverse is given by $u=y/(x-1), v=z/(x-1)$ (here $z=(x^2+y^2-x)/N$) and can be computed modulo $N$ provided that $x-1$ is coprime to $N$.

@Gautam Of course you are right. I was to quick. I edited the answer and believe that everything is clear now.