Divisors in residue classes

Abstract:

In this paper the following result is proved. Let r, s and n be integers satisfying $0 \leqslant r < s < n$, $s > {n^{1/3}}$, $\gcd (r,s) = 1$. Then there exist at most 11 positive divisors of n that are congruent to r modulo s. Moreover, there exists an efficient algorithm for determining all these divisors. The bound 11 is obtained by means of a combinatorial model related to coding theory. It is not known whether 11 is best possible; in any case it cannot be replaced by 5. Nor is it known whether similar results are true for significantly smaller values of $\log s/\log n$. The algorithm treated in the paper has applications in computational number theory.