Roots of unity and nullity modulo 𝑛

Source abstract

For a fixed positive integer ℓ \ell , we consider the function of n n that counts the number of elements of order ℓ \ell in Z n ∗ \mathbb {Z}_n^* . We show that the average growth rate of this function is C ℓ ( log ⁡ n ) d ( ℓ ) − 1 C_\ell (\log n)^{d(\ell )-1} for an explicitly given constant C ℓ C_\ell , where d ( ℓ ) d(\ell ) is the number of divisors of ℓ \ell . From this we conclude that the average growth rate of the number of primitive Dirichlet characters modulo n n of order ℓ \ell is ( d ( ℓ ) − 1 ) C ℓ ( log ⁡ n ) d ( ℓ ) − 2 (d(\ell )-1)C_\ell (\log n)^{d(\ell )-2} for ℓ ≥ 2 \ell \ge 2 . We also consider the number of elements of Z n \mathbb {Z}_n whose ℓ \ell th power equals 0, showing that its average growth rate is D ℓ ( log ⁡ n ) ℓ − 1 D_\ell (\log n)^{\ell -1} for another explicit constant D ℓ D_\ell . Two techniques for evaluating sums of multiplicative functions, the Wirsing–Odoni and Selberg–Delange methods, are illustrated by the proofs of these results.