Asymptotic upper bound on number of solutions to $ab \equiv n \pmod m$

Question

Does anyone know a rough upper bound on the number of solutions to $ab \equiv n \pmod m$ when $n$ and $m$ are given and $a<m$, $b<m$, $n<m$? Specifically, I want to know how the number of solutions grows asymptotically in terms of $m$.

Answer 1

Well if you assume $a = b$ then you are looking for the number of quadratic residues of this expression $\bmod(m)$. If you assume $a \neq b$ then you would require that the greatest common divisor of $a$ and $m$ divides $n$, and in that case you would have $d$ unique solutions, where $d$ is $(a,m)$.

This is a lot of things to consider, and I suggest picking a modulus and finding the quadratic residues first, and then considering the amount of coprime integers (Euler's phi function). I do not know if there will be asymptotic behavior with this because of the irregularity of the phi function. A prime modulus will yield many more solutions than a composite modulus, and of course we do not have a general form for predicting when a prime occurs.

Answer 2

You said in comments that you're most interested in the case where $m=2^k$, let's handle that first.

When $n=0$, the number of solutions is $2^{k-1}(k+2)$ which goes as $\Theta(m\log m)$. Namely, when $a=0$ then $b$ can be arbitrary, contributing $2^k$ solutions. If $a$ is nonzero, then suppose it has $j$ trailing zeroes. This fixes $j+1$ bits of $a$, and the $k-j$ least significant bits of $b$ must also be zeroes, but the remaining $k-1$ bits in total can be chosen freely, contributing $2^{k-1}k$ solutions all in all.

On the other hand, when $n$ is odd, there are exactly $2^{k-1}$ solutions, since $a$ can be chosen as an arbitrary odd number (which is invertible modulo $m$) and then $b$ must be $na^{-1}$.

Finally, when $n$ is even but nonzero, let's assume it has $j<k$ trailing zeroes. Those trailing zeroes have to be distributed between $a$ and $b$, and when we have done that there are $2k-j-2$ more bits to select. Of course, they can't be chosen arbitrarily, because most choices would give wrong values for the top $k-j-1$ bits of $ab$, but each value of $ab$ with exactly $j$ trailing zeroes will be hit equally many times (again, because odd numbers are invertible modulo powers of two), so we can just divide them out. So the number of solutions in this case becomes $$ \frac{2^{2k-j-2}(j+1)}{2^{k-j-1}} = 2^{k-1}(j+1) = \frac{j+1}{2}m $$ which agrees with the case for odd $n$ (where $j=0$).

So the number of solutions goes as $\Theta(m)$ for every fixed positive $n$.

---

What if $m$ is not a power of 2?

If $m$ is a power of a different prime, $m=p^k$ with $k\ge 1$, then the above analysis still applies with the difference that there is now more than one possibility for the rightmost nonzero $p$-ary digit. In this case we get $\frac{(j+1)(p-1)}{p}m = (j+1)(1-\frac1p)m$ solutions.

When $m$ is the power of different primes, we can split into separate problems for each of them and combine solutions using the Chinese Remainder Theorem. Then the number of solutions is $$ \bigl(\prod_{p\mid m}(j_p+1)(1-\frac1p)\bigr) m = \bigl(\prod_{p\mid n}j_p+1\bigr) \phi(m) $$ which is still $O(m)$ for fixed $n$. Once we reach primes larger than $n$, the $j_p+1$ factors are all $1$, so there's a finite upper bound for the factor on the $m$.

(There are some additional corrections to make for primes that divide $n$, such that $n\equiv 0\pmod{p^{k_p}}$, in which case we should use $k_p+2$ instead of $j_p+1$ in the product, but there is a bounded set of primes this can happen for and only when $k_p\le j_p$, so $\prod_{p\mid n}(j_p+1\text{ or }k_p+2)$ is bounded for fixed $n$).

On the other hand, for unrestricted $m$ there is no linear lower bound on the number of solutions. Because the sum of the reciprocals of the primes diverges, the product of the $1-\frac1p$ factors can be come arbitrarily small for $m$ with many different prime factors. The nicest asymptotic lower bound (still for fixed $n$) would be something like $\Omega(m/\log m)$.