Divisors in residue classes, constructively
Divisors in residue classes, constructively
Let $r,s,n$ be integers satisfying $0 \leq r < s < n$, $s \geq n^{\alpha }$, $\alpha > 1/4$, and let $\gcd (r,s)=1$. Lenstra showed that the number of integer divisors of $n$ equivalent to $r \pmod s$ is upper bounded by $O((\alpha -1/4)^{-2})$. We re-examine this problem, showing how …