Let τ(n; k, h) denote the number of divisors of n which are congruent to h (mod k), and τ(n; k) the number of divisors of n prime to k, so that
![](//static-cambridge-org.ezproxyberklee.flo.org/content/id/urn%3Acambridge.org%3Aid%3Aarticle%3AS0025579300003661/resource/name/S0025579300003661_eqnU1.gif?pub-status=live)
Let
![](//static-cambridge-org.ezproxyberklee.flo.org/content/id/urn%3Acambridge.org%3Aid%3Aarticle%3AS0025579300003661/resource/name/S0025579300003661_eqnU2.gif?pub-status=live)
Erdős [1] proved that, if ε and η are fixed arbitrary positive numbers, then for almost all integers n ≤ x, we have
![](//static-cambridge-org.ezproxyberklee.flo.org/content/id/urn%3Acambridge.org%3Aid%3Aarticle%3AS0025579300003661/resource/name/S0025579300003661_eqnU3.gif?pub-status=live)
provided
![](//static-cambridge-org.ezproxyberklee.flo.org/content/id/urn%3Acambridge.org%3Aid%3Aarticle%3AS0025579300003661/resource/name/S0025579300003661_eqnU4.gif?pub-status=live)
Hall and Sudbery [2] showed that it is sufficient that
![](//static-cambridge-org.ezproxyberklee.flo.org/content/id/urn%3Acambridge.org%3Aid%3Aarticle%3AS0025579300003661/resource/name/S0025579300003661_eqnU5.gif?pub-status=live)
and apart from the ε, this upper bound for k is best possible, for it is clear that k must not exceed the normal order of τ(n). For n ≤ x, Hardy and Ramanujan [3] showed that this normal order is (log x)log 2 = 2 log log x.