Character sums and Pólya-Vinogradov inequality

In this post, we consider character sums, which are one of the central objects in the discrete Fourier analysis of the integers modulo $q$. We will prove the Pólya-Vinogradov estimate, which we will observe to be the best possible estimate up to a logarithmic factor, despite being easy to prove. Character sums arise in many problems in number theory, and we utilize them to prove classical bounds for the least quadratic nonresidue and primitive root modulo $q$. We also show that the generalized Riemann hypothesis reduces the bounds for the least quadratic nonresidue and primitive root considerably.

Primitive roots and their applications

In this post we prove the existence of primitive roots modulo prime powers, using elementary number theory and presenting numerous problems in which primitive roots can be applied. This post is suitable for instance for olympiad training.

Introduction

When doing modular arithmetic modulo $n$, whose prime factorization is $p_1^{\alpha_1}...p_k^{\alpha_k},$ it is sensible to consider each of the moduli $p_i^{\alpha_i}$ separately. Indeed, the Chinese remainder theorem guarantees that if we solve a congruence equation modulo each of these prime powers, we can recover the original solution $\pmod n$. This is not only numerically a lot more effective, but also shows that any polynomial congruence problem in $\mathbb{Z}_n$ (the integers $\pmod n$) is reduced to understanding the structure of $\mathbb{Z}_{p^{\alpha}}$ for prime powers (we will encounter this fact many times).

The basic operations are easy to perform in $\mathbb{Z}_{p^{\alpha}}$. Three of them are no harder than in the ordinary integers, and division is also quite easy in $\mathbb{Z}_{p^{\alpha}}$ since the congruence $ax\equiv b \pmod{p^{\alpha}}$ has a unique solution, denoted by $x\equiv \frac{b}{a} \pmod{p^{\alpha}}$, if and only if $a$ and $p$ are coprime. This solution is given by Euclid's algorithm in an effective way. Therefore, it is natural to ask what is an effective way to take roots modulo a prime power or to solve exponential congruences.

The answer lies in exploiting the existence of a primitive root $g$ modulo $p^{\alpha}$, which is an integer such that its powers $g^k$ are noncongruent for $0\leq k<\varphi(p^{\alpha})$ ($\varphi(\cdot)$ is Euler's totient function). By Euler's theorem, $g^{\varphi(q)}\equiv 1 \pmod q$, so a primitive root is an integer whose powers repeat themselves as rarely as possible. Clearly every residue class coprime to $p$ is given by a power of $g$, so if $x\equiv g^{y}\pmod{p^{\alpha}},$ the equation $x^k\equiv a \pmod{p^{\alpha}}$ becomes $g^{ky}\equiv a \pmod{p^{\alpha}}$. In order to solve this new equation, we just need to determine which power of $g$ is congruent to $a$ (the answer is unique modulo $\varphi(p^{\alpha})$), and then perform a division, which is easy. Similarly, if we write $a\equiv g^m \pmod{p^{\alpha}}$, the equation $a^x \equiv b \pmod{p^{\alpha}}$ reduces to $g^{mx}\equiv b \pmod{p^{\alpha}}$, which can be solved in the same way as the former congruence. Hence, primitive roots work much in the same way as logarithms do in $\mathbb{R}$, but they are much more interesting, since they are by no means trivial despite their usefulness.

To appreciate primitive roots, it is good to know that before calculators people computed using logarithm tables. This is because all the basic operations are reduced to easier ones by taking logarithms, so one only needs a table of the values of the logarithm. However, in modular arithmetic, calculators have not replaced discrete logarithms, which are based on primitive roots, since the numbers that one computes with can be enormous (for example, one may want to compute $2^n\pmod m$, where $n$ is some number greater than one million, say), while the results are of reasonable size, namely smaller than the modulus. The fact that computing discrete logarithms, or equivalently finding primitive roots, is hard is the basis of many cryptosystems that are used for secure data transfer.