# Proof that a Gauss sum associated with a quadratic character mod p is the same as a quadratic Gauss sum

In this note I want to quickly record a solution I have found to the following problem: If $p$ is an odd prime such that $p \nmid n$ and $\chi(r) = (r|p)$, prove that

$G(n, \chi) = \sum_{r \text{mod } p} (r|p) e^{2 \pi i n r/p} = \sum_{r = 1}^p e^{2 \pi i n r^2/p} = G(n ; p)$

My solution is as follows. We have

$G(n, \chi) = \sum_{r \text{mod } p} (r|p) e^{2 \pi i n r/p}$

$= \sum_{\substack{\text{quadratic}\\\text{residues }r}} e^{2 \pi i n r/p} - \sum_{\substack{\text{quadratic}\\\text{non-residues }s}} e^{2 \pi i n s/p}$

whereas

$G(n ; p) = \sum_{r = 1}^p e^{2 \pi i n r^2/p}$

$= \sum_{r = 1}^{p-1} e^{2 \pi i n r^2/p} + 1$

$= 2\sum_{\substack{\text{quadratic}\\\text{residues }r}} e^{2 \pi i n r/p} + 1$

(since $r$ mod $p$ will range over both quadratic residues and non-residues, so $r^2$ will range over the quadratic residues twice)

$= \sum_{\substack{\text{quadratic}\\\text{residues }r}} e^{2 \pi i n r/p}$

$+ \big \{ \sum_{\substack{\text{quadratic}\\ \text{residues }r}} e^{2 \pi i n r/p} + 1 \big \}$

Therefore $G(n, \chi) = G(n ; p)$ if and only if

$- \sum_{\substack{\text{quadratic}\\\text{non-residues }s}} e^{2 \pi i n s/p}$

$= \sum_{\substack{\text{quadratic}\\ \text{residues }r}} e^{2 \pi i n r/p} + 1$

$\iff$

$\sum_{\substack{\text{quadratic}\\ \text{residues }r}} e^{2 \pi i n r/p} + \sum_{\substack{\text{quadratic}\\ \text{non-residues }s}} e^{2 \pi i n s/p} = -1$

But this is true because

$\sum_{\substack{\text{quadratic}\\ \text{residues }r}} e^{2 \pi i n r/p} + \sum_{\substack{\text{quadratic}\\ \text{non-residues }s}} e^{2 \pi i n s/p} = \sum_{r=1}^{p-1} e^{2 \pi inr/p}$

This is a geometric sum of the form

$S = \sum_{r=1}^{p-1} x^r = x + x^2 + \cdots + x^{p-1}$

where

$x = e^{2 \pi in/p}$

Therefore

$xS = x^2 + x^3 + \cdots + x^p$

Subtracting the expression for $S$ from this we get

$(x - 1)S = x^p - x = 1 - x$

(the last equality is true because $x$ is a $p$-th root of unity)

$\iff$

$S = -1$

Therefore $G(n, \chi) = G(n ; p)$.

# Advanced Number Theory Note #16: A proof of the law of quadratic reciprocity using Gauss sums and quadratic characters

The prince of mathematicians (princeps mathematicorum), Carl Friedrich Gauss, arguably the greatest mathematician who ever lived, devoted a lot of attention to exploring alternative proofs of the law of quadratic reciprocity. As I mentioned in a previous note, this is actually a very deep result which has had a profound impact on modern mathematics. A rather good Wikipedia page about the quadratic reciprocity law has a section entitled connection with cyclotomy which makes clear its importance to the development of modern class field theory, and a history and alternative statements section catalogues its somewhat convoluted history.

In the present note I want to explore in detail one of the (many) approaches to proving the law of quadratic reciprocity, an approach which uses Gauss sums and Legendre symbols. (In a later note I will explore another proof using quadratic Gauss sums which involves contour integration techniques from complex analysis).

The proof consists of three key theorems, as follows:

Theorem I. This proves that $G(1, \chi)^2 = (-1|p)p$ when $\chi = (r|p)$.

Theorem II. This proves that $G(1, \chi)^{q-1} \equiv (q|p)$ (mod $q$) is equivalent to the law of quadratic reciprocity, using Theorem I.

Theorem III. This proves an identity for $G(1, \chi)^{q-1}$ from which the congruence in Theorem II follows, thus completing the overall proof of the quadratic reciprocity law.

In a previous note I stated a version of the law of quadratic reciprocity due to Legendre as follows: if $p$ and $q$ are distinct odd primes then

$(p|q) = \begin{cases} (q|p),& \text{if either } p \equiv 1 \ \text{(mod 4) } \text{or } q \equiv 1 \ \text{(mod 4)}\\ -(q|p), & \text{if } p \equiv q \equiv 3 \ \text{(mod 4)} \end{cases}$

For the purposes of the proof in the present note it is necessary to express the quadratic reciprocity law as

$(q|p) = (-1)^{(p - 1)(q - 1)/4}(p|q)$

These two formulations are completely equivalent. To see this, note that if $p \equiv 1$ (mod $4$) or $p \equiv 1$ (mod $4$), the exponent on $(-1)$ in the second formulation reduces to an even integer so we get $(q|p) = (p|q)$. On the other hand, if $p \equiv q \equiv 3$ (mod $4$), the exponent on $(-1)$ in the second formulation reduces to an odd integer, so we get $(q|p) = -(p|q)$.

Also note that the proof makes use of Gauss sums incorporating the Legendre symbol as the Dirichlet character in the summand, i.e., Gauss sums of the form

$G(n, \chi) = \sum_{r \text{mod } p} \chi(r) e^{2 \pi i n r/p}$

where $\chi(r) = (r|p)$, and the Legendre symbol in this context is referred to as the quadratic character mod p. Since the modulus is prime, the Dirichlet character here is primitive and we have that $G(n, \chi)$ is separable with

$G(n, \chi) = \overline{\chi(n)} G(1, \chi) = (n|p) G(1, \chi)$

for every $n$, because either $gcd(n, p) = 1$, or if $gcd(n, p) > 1$ we must have $p|n$ in which case $G(n, \chi) = 0$ because $e^{2 \pi i n r/p} = 1$ and $\sum_{r \text{mod } p} \chi(r) = 0$ (for non-principal characters the rows of the character tables sum to zero).

Theorem I. If $p$ is an odd prime and $\chi(r) = (r|p)$ then

$G(1, \chi)^2 = (-1|p) p$

Proof: We have

$G(1, \chi) = \sum_{r = 1}^{p - 1} (r|p) e^{2 \pi i r/p}$

and therefore

$G(1, \chi)^2 = \sum_{r = 1}^{p - 1} (r|p) e^{2 \pi i r/p} \times \sum_{s = 1}^{p - 1} (s|p) e^{2 \pi i s/p}$

$= \sum_{r = 1}^{p - 1} \sum_{s = 1}^{p - 1} (r|p) (s|p) e^{2 \pi i (r + s)/p}$

For each pair of values of $r$ and $s$ there is a unique $t$ mod $p$ such that

$s \equiv tr$ (mod $p$)

since this is a linear congruence with a unique solution. We also have that

$(r|p) (s|p) = (r|p) (tr|p)$

$= (r|p) (r|p) (t|p)$

$= (r^2|p) (t|p)$

$= (t|p)$

Therefore we can write

$G(1, \chi)^2 = \sum_{r = 1}^{p - 1} \sum_{tr = 1}^{p - 1} (t|p) e^{2 \pi i r (1 + t)/p}$

$= \sum_{r = 1}^{p - 1} \sum_{t = 1}^{p - 1} (t|p) e^{2 \pi i r (1 + t)/p}$

(where the index in the second summation has been reduced to $t$ since $t$ will range through all the least positive residues of $p$ independently of $r$)

$= \sum_{t = 1}^{p - 1} (t|p) \sum_{r = 1}^{p - 1} e^{2 \pi i r (1 + t)/p}$

The last sum on $r$ is a geometric sum of the form

$g(1 + t) = \sum_{r = 1}^{p - 1} x^r$

where

$x = e^{2 \pi i (1 + t)/p}$

so we have

$g(1 + t) = \begin{cases} \frac{x^p - x}{x - 1} & \text{if } x \neq 1\\ p - 1 & \text{if } x = 1 \end{cases}$

But it must be the case that $x^p = 1$ (because $x$ is a $p$th root of unity), and we also have that $x = 1$ if and only if $p|(1 + t)$, so we can write

$g(1 + t) = \begin{cases} -1 & \text{if } p \nmid (1 + t) \\ p - 1 & \text{if } p | (1 + t) \end{cases}$

Therefore

$G(1, \chi)^2 = - \sum_{t = 1}^{p - 2} (t|p) + (p - 1) (p - 1|p)$

(because the only value of $t$ for which $p|(1 + t)$ is $t = p - 1$, so we can pull this out of the summation and then for this value of $t$ the Legendre symbol $(t|p)$ becomes $(p - 1|p)$)

$= - \sum_{t = 1}^{p - 2} (t|p) - (p - 1|p) + p(p - 1|p)$

$= - \sum_{t = 1}^{p - 1} (t|p) + p(p - 1|p)$

$= - \sum_{t = 1}^{p - 1} (t|p) + p(-1|p)$

(since $(p - 1|p) = (-1|p)$)

$= (-1|p) p$

(because $\sum_{t = 1}^{p - 1} (t|p) = 0$ since $(t|p)$ is a Dirichlet character mod $p$ and the rows of Dirichlet character tables sum to zero). $\square$

Since $(-1|p) = \pm 1$, Theorem I tells us that $G(1, \chi)^2$ is an integer and it then follows that

$G(1, \chi)^{q - 1} = (G(1, \chi)^2)^{(q - 1)/2}$

is also an integer for every odd $q$. It turns out that the law of quadratic reciprocity is intimately related to the value of the integer $G(1, \chi)^{q - 1}$ mod $q$, which is what the next theorem shows.

Theorem II. Let $p$ and $q$ be distinct odd primes and let $\chi$ be the quadratic character (i.e., the Legendre symbol) mod $p$. Then the quadratic reciprocity law

$(q|p) = (-1)^{(p - 1)(q - 1)/4}(p|q)$

is equivalent to the congruence

$G(1, \chi)^{q - 1} \equiv (q|p)$ (mod $q$)

Proof: From the result proved in Theorem I we have that

$G(1, \chi)^{q - 1} = (G(1, \chi)^2)^{(q - 1)/2}$

$= (-1|p)^{(q - 1)/2} p^{(q - 1)/2}$

$= (-1)^{(p - 1)(q - 1)/4} p^{(q - 1)/2}$

where the last equality follows from property (e) of Legendre symbols in my previous note which implies

$(-1|p) = (-1)^{(p - 1)/2}$

By property (d) of Legendre symbols we also have

$p^{(q - 1)/2} \equiv (p|q)$ (mod $q$)

so we can write

$G(1, \chi)^{q - 1} \equiv (-1)^{(p - 1)(q - 1)/4} (p|q) = (q|p)$ (mod $q$)

where the last equality follows from the law of quadratic reciprocity.

Therefore if the law of quadratic reciprocity holds, then so does

$G(1, \chi)^{q - 1} \equiv (q|p)$ (mod $q$)

and vice versa. $\square$

The last stage of the proof is now to deduce the congruence in Theorem II from an identity for $G(1, \chi)^{q - 1}$ which is established in the next theorem.

Theorem III. If $p$ and $q$ are distinct odd primes and if $\chi$ is the quadratic character (i.e., Legendre symbol) mod $p$, we have

$G(1, \chi)^{q - 1} = (q|p) \sum_{r_1 mod \ p} \cdots \sum_{r_q mod \ p} (r_1 \cdots r_q |p)$

where the summation indices satisfy the restriction

$r_1 + \cdots + r_q \equiv q$ (mod $p$)

Proof: It is easy to show that the Gauss sum $G(n, \chi)$ is a periodic function of $n$ with period $p$ since

$G(n + p, \chi) = \sum_{m = 1}^{p} \chi(m) e^{2 \pi i m (n + p)/p}$

$= \sum_{m = 1}^{p} \chi(m) e^{2 \pi i m n/p} e^{2 \pi i m}$

$= \sum_{m = 1}^{p} \chi(m) e^{2 \pi i m n/p} = G(n, \chi)$

Since therefore

$G(n, \chi)^q = G(n + p, \chi)^q$

it follows that $G(n, \chi)^q$ is also a periodic function of $n$ with period $p$. Therefore we have a finite Fourier expansion

$G(n, \chi)^q = \sum_{m \ mod \ p} a_q(m) e^{2 \pi i m n/p}$

where the coefficients are given by

$a_q(m) = \frac{1}{p} \sum_{n \ mod \ p} G(n, \chi)^q e^{-2 \pi i m n/p}$

(see my previous note on finding the finite Fourier expansion of an arithmetical function). Simply from the general definition of $G(n, \chi)$ (using Legendre symbols as Dirichlet characters) we have

$G(n, \chi)^q = \sum_{r_1 mod \ p} (r_1|p) e^{2 \pi i n r_1/p} \cdots \sum_{r_q mod \ p} (r_q|p) e^{2 \pi i n r_q/p}$

$= \sum_{r_1 mod \ p} \cdots \sum_{r_q mod \ p} (r_1 \cdots r_q |p) e^{2 \pi i n (r_1 + \cdots + r_q)/p}$

so we can write the above Fourier expansion coefficients as

$a_q(m) = \frac{1}{p} \sum_{r_1 mod \ p} \cdots \sum_{r_q mod \ p} (r_1 \cdots r_q |p) \times \sum_{n \ mod \ p} e^{2 \pi i n (r_1 + \cdots + r_q - m)/p}$

The sum on $n$ is a geometric sum of the form

$g(r_1 + \cdots + r_q - m) = \sum_{n = 0}^{p - 1} x^n$

where

$x = e^{2 \pi i (r_1 + \cdots + r_q - m)/p}$

so we have

$g(r_1 + \cdots + r_q - m) = \begin{cases} \frac{x^p - 1}{x - 1} & \text{if } x \neq 1\\ p & \text{if } x = 1 \end{cases}$

$= \begin{cases} 0 & \text{if } x \neq 1\\ p & \text{if } x = 1 \end{cases}$

(since $x^p = 1$ because $x$ is a $p$th root of unity). Therefore in the expression for $a_q(m)$ the sum on $n$ vanishes unless $r_1 + \cdots + r_q \equiv m$ (mod $p$), in which case the sum is equal to $p$. Therefore we can write

$a_q(m) = \sum_{r_1 mod \ p} \cdots \sum_{r_q mod \ p} (r_1 \cdots r_q |p)$

where the summation indices satisfy the restriction

$r_1 + \cdots + r_q \equiv m$ (mod $p$)

Now we return to the original expression for $a_q(m)$, namely

$a_q(m) = \frac{1}{p} \sum_{n \ mod \ p} G(n, \chi)^q e^{-2 \pi i m n/p}$

and use this to obtain a different expression for $a_q(m)$. The separability of $G(n, \chi)$ means that

$G(n, \chi) = (n|p) G(1, \chi)$

We also have the result for odd $q$ that

$(n|p)^q = (n^q|p) = (n^{q-1}|p) (n|p) = (n|p)$

(since $q - 1$ is even). Therefore we find

$a_q(m) = \frac{1}{p} G(1, \chi)^q \sum_{n \ mod \ p} (n|p) e^{-2 \pi i m n/p}$

$= \frac{1}{p} G(1, \chi)^q G(-m, \chi)$

$= \frac{1}{p} G(1, \chi)^q (m|p) G(-1, \chi)$

$= (m|p) G(1, \chi)^{q - 1}$

where the last equality follows from the fact that

$G(1, \chi) G(-1, \chi) = G(1, \chi) (-1|p) G(1, \chi)$

$= G(1, \chi)^2 (-1|p)$

$= (-1|p) p (-1|p)$

$= ((-1)^2|p) p$

$= p$

Therefore

$(m|p) a_q(m) = (m|p) (m|p) G(1, \chi)^{q - 1}$

$= (m^2|p) G(1, \chi)^{q - 1}$

$= G(1, \chi)^{q - 1}$

Taking $m = q$ and the previously obtained expression for $a_q(m)$ we get the claimed result

$G(1, \chi)^{q - 1} = (q|p) \sum_{r_1 mod \ p} \cdots \sum_{r_q mod \ p} (r_1 \cdots r_q |p)$

where the summation indices satisfy the restriction

$r_1 + \cdots + r_q \equiv q$ (mod $p$). $\square$

We are now in a position to deduce the law of quadratic reciprocity from Theorems I, II and III. From the result obtained in Theorem II, it suffices to show that

$\sum_{r_1 mod \ p} \cdots \sum_{r_q mod \ p} (r_1 \cdots r_q |p) \equiv 1$ (mod $q$)

where the summation indices satisfy the restriction

$r_1 + \cdots + r_q \equiv q$ (mod $p$)

i.e., every term $(r_1 \cdots r_q |p)$ in the summand satisfies this restriction. One way in which this restriction is satisfied is when

$r_j \equiv 1$ (mod $p$)

for $j = 1, \dots, q$. In this case we have

$(r_1 \cdots r_q |p) = (1|p) = 1$

Every other possible way of satisfying the restriction involves

$r_j \not \equiv r_k$ (mod $p$)

for some $j \neq k$. For each of these ways, every cyclic permutation of $r_1, \ldots, r_q$ satisfying the restriction contributes the same summand $(r_1 \cdots r_q |p)$. Therefore for each of these ways of satisfying the restriction, each summand appears $q$ times and therefore contributes $0$ modulo $q$ to the sum. Therefore only the scenario $r_j \equiv 1$ (mod $p$) for $j = 1, \dots, q$ yields a non-zero contribution, so the sum is $1$ (mod $q$). This completes the proof of the law of quadratic reciprocity.

To clarify the last point, consider the following

Example: Take $p = 5$ and $q = 3$. Then the equations are

$\sum_{r_1 \ mod \ 5} \sum_{r_2 \ mod \ 5} \sum_{r_3 \ mod \ 5} (r_1 r_2 r_3|5) \equiv 1$ (mod $3$)

where the summation indices satisfy the restriction

$r_1 + r_2 + r_3 \equiv 3$ (mod $5$)

In the case when $r_1 \equiv r_2 \equiv r_3 \equiv 1$ (mod $5$) we have

$(r_1 r_2 r_3|5) \equiv (1|5) = 1$

so the first equation is satisfied.

Suppose we consider any other way of satisfying the restriction, say

$r_1 \equiv 1$, $r_2 \equiv 3$, $r_3 \equiv 4$ (mod $5$)

so that

$r_1 + r_2 + r_3 \equiv 8 \equiv 3$ (mod $5$)

Then the cyclic permutations

$r_1 \equiv 4$, $r_2 \equiv 1$, $r_3 \equiv 3$ (mod $5$)

and

$r_1 \equiv 3$, $r_2 \equiv 4$, $r_3 \equiv 1$ (mod $5$)

will also satisfy the restriction, and these contribute a total of

$3 (1 \cdot 3 \cdot 4|5) \equiv 0$ (mod $3$)

to the sum. Therefore only the first way of satisfying the restriction will contribute to the sum, so the sum must equal 1.

# Advanced Number Theory Note #15: The Legendre symbol (a|p) as a Dirichlet character mod p

The Legendre symbol was introduced by the great 19th Century mathematician Adrien-Marie Legendre (the charicature shown here is the only known contemporary likeness of him). It has proved to be very useful as a shorthand for stating a number’s quadratic character and also in calculations thereof.

If $p$ is an odd prime, then the Legendre symbol $(a|p) = 1$ if $a$ is a quadratic residue of $p$, $(a|p) = -1$ if $a$ is a quadratic non-residue of $p$, and $(a|p) = 0$ if $a \equiv 0$ (mod $p$).

The Legendre symbol has a number of well known properties which are useful for calculations and are summarised here for convenience:

The last property, the law of quadratic reciprocity, is actually a deep result which has been studied in depth and proved in numerous different ways by Gauss and others. Indeed, it was for the purpose of finding his own proof of this result that Legendre invented the Legendre symbol. In a later note I will explore in detail a proof of the law of quadratic reciprocity using Gauss sums and Legendre symbols. This proof hinges on the fact that the Legendre symbol $(a|p)$ is a Dirichlet character mod $p$. In the present short note I want to quickly show explicitly why this is the case by highlighting three key facts about Legendre symbols:

I. The Legendre symbol $(a|p)$ is a completely multiplicative function of $a$.

II. The Legendre symbol $(a|p)$ is periodic with period $p$.

III. The Legendre symbol vanishes when $p|a$.

Fact III follows immediately from the definition of Legendre symbols, and II is true because we have

$a \equiv a +p$ (mod $p$)

and therefore (by property (a) above)

$(a|p) = (a + p|p)$

so the Legendre symbol is periodic with period $p$.

To prove I, observe that if $p|a$ or $p|b$ then $ab \equiv 0$ (mod $p$) so

$(ab|p) = (a|p) \cdot (b|p) = 0$

since at least one of $(a|p)$ or $(b|p)$ must be zero.

If $p \not| a$ and $p \not| b$, then $p \not| ab$ and we have (by property (d) above)

$(ab|p) \equiv (ab)^{(p-1)/2}$

$\equiv (a)^{(p-1)/2} \cdot (b)^{(p-1)/2}$

$\equiv (a|p) \cdot (b|p)$ (mod $p$)

Therefore

$(ab|p) - (a|p) \cdot (b|p)$

is divisible by $p$, and since this difference cannot actually equal a multiple of $p$ (the terms can only take the values $1$ or $-1$), the difference must be zero. The Legendre symbol is therefore completely multiplicative as claimed in I.

Since $(a|p)$ is a completely multiplicative function of $a$ which is periodic with period $p$ and vanishes when $p|a$, it follows that $(a|p)$ is a Dirichlet character $\chi(a)$ mod $p$ as claimed.

I will illustrate this with two examples. First, let $p = 7$. We have

$1^2 \equiv 1$ (mod $7$)

$2^2 \equiv 4$ (mod $7$)

$3^2 \equiv 2$ (mod $7$)

so the quadratic residues of $7$ are $1$, $2$ and $4$ and the quadratic non-residues are $3$, $5$ and $6$. The Legendre symbol $(a|7)$ therefore takes the values

$(1|7) = 1$

$(2|7) = 1$

$(3|7) = -1$

$(4|7) = 1$

$(5|7) = -1$

$(6|7) = -1$

These are exactly the values of the fourth character in the Dirichlet character table mod $7$:

Thus, $(a|7) = \chi_4(a)$ mod $7$.

For a second example, let $p = 11$. We have

$1^2 \equiv 1$ (mod $11$)

$2^2 \equiv 4$ (mod $11$)

$3^2 \equiv 9$ (mod $11$)

$4^2 \equiv 5$ (mod $11$)

$5^2 \equiv 3$ (mod $11$)

so the quadratic residues of $11$ are $1$, $3$ and $4$, $5$ and $9$ and the quadratic non-residues are $2$, $6$ and $7$, $8$, and $10$. The Legendre symbol $(a|11)$ therefore takes the values

$(1|11) = 1$

$(2|11) = -1$

$(3|11) = 1$

$(4|11) = 1$

$(5|11) = 1$

$(6|11) = -1$

$(7|11) = -1$

$(8|11) = -1$

$(9|11) = 1$

$(10|11) = -1$

These are exactly the values of the sixth character in the Dirichlet character table mod $11$:

Thus, $(a|11) = \chi_6(a)$ mod $11$.

# Advanced Number Theory Note #14: An inequality due to Pólya for the partial sums of primitive Dirichlet characters

The mathematician George Pólya, author of the famous book How to Solve it, found an inequality for sums of primitive Dirichlet characters which involves a number of key ideas relating to periodic arithmetical functions and Gauss sums. The inequality says that if $\chi$ is any primitive character mod $k$, then for all $x \geq 1$ we have

$\bigg| \sum_{m \leq x} \chi(m) \bigg| < \sqrt{k} \log k$

In this note I want to carefully go through the (rather tricky) proof of this inequality, using this as an opportunity to bring together a variety of ideas which have appeared in my last few blog posts on advanced number theory.

Looking back through my notes, a key theme that jumps out is that interesting things happen when we consider sums of (complex) roots of unity. To start with, the Möbius function $\mu(k)$ can be obtained as a sum of the primitive $k$th roots of unity:

$\mu(k) = \sum_{\substack{1 \le a \le k \\ gcd(a,k)=1}} e^{2\pi ia/k}$

I discussed this in detail in Advanced Number Theory Note #10. A generalisation of this is Ramanujan’s sum, which for some fixed integer $n$ is the sum of the $n$th powers of the primitive roots of unity:

$c_k(n) = \sum_{\substack{m\hspace{1 mm} mod \hspace{1 mm}k \\ gcd(m, k)=1}} e^{2\pi imn/k}$

I discussed Ramanujan’s sum in Advanced Number Theory Note #11 (also see references therein). Ramanujan’s sum reduces to the Möbius function when $n = 1$:

$\mu(k) = c_k(1)$

A further generalisation is the Gauss sum associated with a Dirichlet character $\chi$ mod $k$:

$G(n. k) = \sum_{m=1}^k \chi(m) e^{2 \pi imn/k}$

I discussed Gauss sums in detail in Advanced Number Theory Note #12. The Gauss sum reduces to Ramanujan’s sum when the Dirichlet character appearing in the sum is the principal character mod $k$, i.e.,

$G(n, \chi_1) = \sum_{\substack{m\hspace{1 mm} mod \hspace{1 mm}k \\ gcd(m, k)=1}} e^{2\pi imn/k} = c_k(n)$

Consideration of the separability of Gauss sums leads to the concepts of induced moduli and primitive Dirichlet characters which I discussed in detail in Advanced Number Theory Note #13. Key results here are that if $\chi$ is a primitive Dirichlet character mod $k$ then $G(n, \chi)$ is separable for every $n$, that is,

$G(n, \chi) = \overline{\chi}(n) G(1, \chi)$

for every $n$, and furthermore

$|G(1, \chi)|^2 = k$

All of these sums are periodic mod $k$ and another key idea in my previous notes is that every arithmetical function $f$ which is periodic mod $k$, that is, which is such that

$f(n + k) = f(n)$

has a finite Fourier expansion expressed as a linear combination of nth powers of kth roots of unity. I discussed this in detail in Advanced Number Theory Note #9. The key result in that note is Theorem 4 which says that $f$ can be written as

$f(m) = \sum_{n \hspace{1 mm} mod \hspace{1 mm} k}g(n) e^{2\pi imn/k}$

where $g$ is a uniquely determined arithmetical function which is also periodic mod $k$ and which is given by the formula

$g(n) = \frac{1}{k}\sum_{m \hspace{1 mm} mod \hspace{1 mm} k}f(m) e^{-2\pi imn/k}$

(the summations can be extended over any complete residue system mod $k$).

Turning now to the proof of Pólya’s inequality, we begin by noting that since any Dirichlet character $\chi$ mod $k$ is periodic mod $k$, it has a finite Fourier expansion of the form

$\chi(m) = \sum_{n=1}^k a_k(n) e^{2 \pi i mn/k}$

where the coefficients $a_k(n)$ are given by the formula

$a_k(n) = \frac{1}{k} \sum_{m=1}^k \chi(m) e^{-2 \pi i mn/k} = \frac{1}{k} G(-n, \chi)$

(the last equality follows from the definition of a Gauss sum). Now assume that $\chi$ is primitive. Then $G(-n, \chi)$ is separable for every $n$ so we have

$G(-n, \chi) = \overline{\chi}(-n) G(1, \chi)$

and the expression for $a_k(n)$ above can be written

$a_k(n) = \frac{G(1, \chi)}{k} \overline{\chi}(-n)$

Therefore the expression for the finite Fourier expansion of $\chi(m)$ above can be written as

$\chi(m) = \sum_{n=1}^k a_k(n) e^{2 \pi i mn/k} = \frac{G(1, \chi)}{k} \sum_{n=1}^k \overline{\chi}(-n) e^{2 \pi i mn/k} = \frac{G(1, \chi)}{k} \sum_{n=1}^k \overline{\chi}(n) e^{-2 \pi i mn/k}$

(The last equality can be justified on the basis that if $gcd(a, k) = 1$ we can replace the index of summation $n$ by $an$ to get $\sum_{n=1}^k \overline{\chi}(-an) e^{2 \pi i anm/k}$. When $a = -1$ we get the last expression on the right hand side).

What we have shown is that the finite Fourier expansion of a primitive Dirichlet character $\chi$ mod $k$ has the form

$\chi(m) = \frac{\tau_k(\chi)}{\sqrt{k}}\sum_{n=1}^k \overline{\chi}(n) e^{-2 \pi i mn/k}$

where

$\tau_k(\chi) = \frac{G(1, \chi)}{\sqrt{k}}$

The numbers $\tau_k(\chi)$ have absolute value $1$ by virtue of the fact noted above that for a separable Gauss sum we have $|G(1, \chi)|^2 = k$.

Summing the finite Fourier expansion for $\chi(m)$ over all $m \leq x$ we get

$\sum_{m \leq x} \chi(m) = \frac{\tau_k(\chi)}{\sqrt{k}}\sum_{n=1}^{k-1} \overline{\chi}(n) \sum_{m \leq x} e^{-2 \pi i mn/k}$

(The upper limit of the first summation on the right hand side can be taken to be $k-1$ rather than $k$ since for any Dirichlet character we have $\chi(k) = 0$).

Taking absolute values and multiplying through by $\sqrt{k}$ we get

$\sqrt{k} \bigg| \sum_{m \leq x} \chi(m) \bigg| \leq \sum_{n=1}^{k-1} \bigg| \sum_{m \leq x} e^{-2 \pi i mn/k} \bigg| \equiv \sum_{n=1}^{k-1} |f(n)|$

where

$f(n) \equiv \sum_{m \leq x} e^{-2 \pi i mn/k}$

(Note that the Dirichlet characters disappear upon taking absolute values because being $k$-th roots of unity they all lie on the unit circle and therefore have absolute value equal to $1$).

We now make use of the observation that

$f(k - n) = \sum_{m \leq x} e^{-2 \pi i m(k - n)/k} = \sum_{m \leq x} e^{-2 \pi i m} \cdot e^{2 \pi i mn/k}$

$= \sum_{m \leq x} e^{2 \pi i mn/k} = \overline{f(n)}$

and thus

$|f(k - n)| = |f(n)|$

To clarify the implications of this, consider some specific values for $k$. Suppose $k = 9$, an odd number. Then we have

$\sum_{n=1}^{k-1} |f(n)| = \sum_{n=1}^{8} |f(n)|$

$= |f(1)| + |f(2)| + |f(3)| + |f(4)| + |f(5)| + |f(6)| + |f(7)| + |f(8)|$

but since $|f(k - n)| = |f(n)|$ we have

$|f(8)| = |f(1)|$

$|f(7)| = |f(2)|$

$|f(6)| = |f(3)|$

$|f(5)| = |f(4)|$

Therefore when $k = 9$ we get

$\sum_{n=1}^{k-1} |f(n)| = \sum_{n=1}^{8} |f(n)| = 2 \sum_{n < 9/2} |f(n)|$

Now consider the case when $k$ is an even number, say $k = 10$. We then have

$\sum_{n=1}^{k-1} |f(n)| = \sum_{n=1}^{9} |f(n)|$

$= |f(1)| + |f(2)| + |f(3)| + |f(4)| + |f(5)| + |f(6)| + |f(7)| + |f(8)| + f(9)$

$= 2(|f(1)| + |f(2)| + |f(3)| + |f(4)|) + |f(5)|$

$= 2 \sum_{n < 10/2} |f(n)| + \big| f\big( \frac{10}{2} \big) \big|$

In general, then, we have

$\sum_{n=1}^{k-1} |f(n)| = 2 \sum_{n < k/2} |f(n)| + \big| f\big( \frac{k}{2} \big) \big|$

where the last term on the right appears only if $k$ is even.

Going back to our previous expression involving the finite Fourier expansion for $\chi(m)$ we can now write

$\sqrt{k} \bigg| \sum_{m \leq x} \chi(m) \bigg| \leq \sum_{n=1}^{k-1} \bigg| \sum_{m \leq x} e^{-2 \pi i mn/k} \bigg| \equiv \sum_{n=1}^{k-1} |f(n)|$

$= 2 \sum_{n < k/2} |f(n)| + \big| f\big( \frac{k}{2} \big) \big|$

We now make further progress by observing that $f(n)$ is in fact the sum of a geometric sequence:

$f(n) = \sum_{m=1}^r y^m = \frac{y^{r+1} - y}{y - 1} = y \frac{y^r - 1}{y - 1}$

where $r = [x]$. Writing $z = e^{- \pi i n/k}$, we have $y = z^2$ and thus

$f(n) = y \frac{y^r - 1}{y - 1} = z^2 \frac{z^{2r} - 1}{z^2 - 1}$

$= \frac{z^{2(r+1)} - z^2}{z^2 - 1}$

$= z^{r+1}\frac{z^{r+1} - z^{2- r - 1}}{z^2 - 1}$

$= z^{r+1}\frac{z^{r+1} - z^{1 - r}}{z^2 - 1}$

$= z^{r+1}\frac{z^r - z^{-r}}{z - z^{-1}}$

Now taking absolute values we obtain

$|f(n)| = \big| \frac{z^r - z^{-r}}{z - z^{-1}} \big|$

$= \frac{\big| \sin \frac{\pi r n}{k} \big|}{\big| \sin \frac{\pi n}{k} \big|}$

$\leq \frac{1}{\sin \frac{\pi n}{k}}$

where I have used the fact that

$\sin x = \frac{e^{ix} - e^{-ix}}{2i}$

Now we use the inequality

$\sin t \geq \frac{2}{\pi} t$

which is valid for $0 \leq t \leq \pi/2$ (as can easily be seen using a sketch). Using this with $t = \pi n/k$ we get

$|f(n)| \leq \frac{1}{\frac{2}{\pi}\frac{\pi n}{k}} = \frac{k}{2n}$

Going back to our previous expression involving the finite Fourier expansion for $\chi(m)$ we can now write

$\sqrt{k} \bigg| \sum_{m \leq x} \chi(m) \bigg| \leq \sum_{n=1}^{k-1} \bigg| \sum_{m \leq x} e^{-2 \pi i mn/k} \bigg| \equiv \sum_{n=1}^{k-1} |f(n)|$

$= 2 \sum_{n < k/2} |f(n)| + \big| f\big( \frac{k}{2} \big) \big|$

$\leq 2 \sum_{n < k/2} \frac{k}{2n} + \big| f\big( \frac{k}{2} \big) \big|$

$\leq k \sum_{n < k/2} \frac{1}{n} + 1$

(since $|f(k/2)| \leq 1$)

$= k \bigg \{\sum_{n < k/2} \frac{1}{n} + \frac{1}{k} \bigg \}$

$< k \sum_{n \leq k} \frac{1}{n}$

$< k \int_1^k \frac{1}{n} dn$

$= k \log k$

Pólya’s inequality now follows upon dividing through by $\sqrt{k}$.

# Dirichlet character tables up to mod 21

I have written about Dirichlet characters in previous notes (see Advanced Number Theory Note #13 and the references therein). For reference purposes, I will set out the first twenty Dirichlet character tables in the present note and demonstrate in detail the calculation of the first ten tables. Recall that there are $\varphi(k)$ distinct Dirichlet characters $\chi$ modulo $k$, each of which is completely multiplicative and periodic with period $k$. Each character value $\chi(n)$ is a (complex) root of unity if $gcd(n, k) = 1$ whereas $\chi(n) = 0$ whenever $gcd(n, k) > 1$. We also have $\chi(1) = 1$ for all Dirichlet characters. These facts uniquely determine each Dirichlet character table.

k = 2

We have $\varphi(2) = 1$ so there is only one Dirichlet character in this case (the principal one), with values $\chi_1(1) = 1$ and $\chi_1(2) = 0$.

k = 3

We have $\varphi(3) = 2$ so there are two Dirichlet characters in this case. One of them will be the principal character which takes the values $\chi_1(1) = 1$, $\chi_1(2) = 1$ and $\chi_1(3) = 0$. To work out the second Dirichlet character we consider the two roots of unity

$\omega = e^{2 \pi i/2} = e^{\pi i} = -1$

and

$\omega^2 = 1$

Note that the set of least positive residues mod $3$ is generated by $2$:

$2 \equiv 2$ mod($3$)

$2^2 \equiv 1$ mod($3$)

Therefore the non-principal Dirichlet character will be completely determined by the values of $\chi(2)$. If we set

$\chi_2(2) = \omega = -1$

then

$\chi_2(1) = \chi_2(2^2) = \chi_2^2(2) = \omega^2 = 1$

(though this calculation is superfluous here since $\chi_2(1) = 1$ anyway. This is a fundamental property of Dirichlet characters arising from the fact that they are completely multiplicative). We also have $\chi_2(3) = 0$. This completes the second character. (From now on we will omit the statements of the zero values of the Dirichlet characters, which as stated earlier arise whenever $gcd(n, k) > 1$).

k = 4

We have $\varphi(4) = 2$ so there are two Dirichlet characters in this case. One of them will be the principal character. (From now on we will always denote the principal character by $\chi_1$). To work out the second Dirichlet character we again consider the two roots of unity

$\omega = e^{2 \pi i/2} = e^{\pi i} = -1$

and

$\omega^2 = 1$

Note that the set of least positive residues mod $4$ is generated by $3$:

$3 \equiv 3$ mod($4$)

$3^2 \equiv 1$ mod($4$)

Therefore the non-principal Dirichlet character will be completely determined by the values of $\chi(3)$. If we set

$\chi_2(3) = \omega = -1$

then

$\chi_2(1) = \chi_2(3^2) = \chi_2^2(3) = \omega^2 = 1$

(though again this second calculation is superfluous since $\chi_2(1) = 1$ anyway). This completes the second character.

k = 5

We have $\varphi(5) = 4$ so there are four Dirichlet characters in this case. We consider the four roots of unity

$\omega = e^{2 \pi i/4} = e^{\pi i/2} = i$

$\omega^2 = e^{4 \pi i/4} = e^{\pi i} = -1$

$\omega^3 = e^{6 \pi i/4} = e^{3 \pi i/2} = -i$

$\omega^4 = e^{8 \pi i/4} = e^{2 \pi i} = 1$

Note that the set of least positive residues mod $5$ is generated by $2$:

$2 \equiv 2$ mod($5$)

$2^2 \equiv 4$ mod($5$)

$2^3 \equiv 3$ mod($5$)

$2^4 \equiv 1$ mod($5$)

Therefore the non-principal Dirichlet characters will be completely determined by the values of $\chi(2)$. If we set

$\chi_2(2) = \omega = i$

then

$\chi_2(3) = \chi_2(2^3) = \chi_2^3(2) = -i$

$\chi_2(4) = \chi_2(2^2) = \chi_2^2(2) = -1$

(and we have $\chi_2(1) = 1$). This completes the second character.

To compute the third character we can set

$\chi_3(2) = \omega^2 = -1$

then

$\chi_3(3) = \chi_3(2^3) = \chi_3^3(2) = -1$

$\chi_3(4) = \chi_3(2^2) = \chi_3^2(2) = 1$

(and we have $\chi_3(1) = 1$). This completes the third character.

To compute the fourth character we set

$\chi_4(2) = \omega^3 = -i$

then

$\chi_4(3) = \chi_4(2^3) = \chi_4^3(2) = i$

$\chi_4(4) = \chi_4(2^2) = \chi_4^2(2) = -1$

(and we have $\chi_4(1) = 1$). This completes the fourth character.

k = 6

We have $\varphi(6) = 2$ so there are two Dirichlet characters in this case. We consider the two roots of unity

$\omega = e^{2 \pi i/2} = e^{\pi i} = -1$

and

$\omega^2 = 1$

Note that the set of least positive residues mod $6$ is generated by $5$:

$5 \equiv 5$ mod($6$)

$5^2 \equiv 1$ mod($6$)

Therefore the non-principal Dirichlet character will be completely determined by the values of $\chi(5)$. If we set

$\chi_2(5) = \omega = -1$

then

$\chi_2(1) = \chi_2(5^2) = \chi_2^2(5) = \omega^2 = 1$

(though again this second calculation is superfluous since $\chi_2(1) = 1$ anyway). This completes the second character.

k = 7

We have $\varphi(7) = 6$ so there are six Dirichlet characters in this case. We consider the six roots of unity

$\omega = e^{2 \pi i/6} = e^{\pi i/3}$

$\omega^2 = e^{2 \pi i/3}$

$\omega^3 = e^{3 \pi i/3} = e^{\pi i} = -1$

$\omega^4 = \omega \cdot \omega^3 = -\omega$

$\omega^5 = \omega \cdot \omega^4 = -\omega^2$

$\omega^6 = e^{6 \pi i/3} = e^{2\pi i} = 1$

Note that the set of least positive residues mod $7$ is generated by $3$:

$3 \equiv 3$ mod($7$)

$3^2 \equiv 2$ mod($7$)

$3^3 \equiv 6$ mod($7$)

$3^4 \equiv 4$ mod($7$)

$3^5 \equiv 5$ mod($7$)

$3^6 \equiv 1$ mod($7$)

Therefore the non-principal Dirichlet characters will be completely determined by the values of $\chi(3)$. If we set

$\chi_2(3) = \omega$

then

$\chi_2(2) = \chi_2(3^2) = \chi_2^2(3) = \omega^2$

$\chi_2(4) = \chi_2(3^4) = \chi_2^4(3) = \omega^4 = -\omega$

$\chi_2(5) = \chi_2(3^5) = \chi_2^5(3) = \omega^5 = -\omega^2$

$\chi_2(6) = \chi_2(3^3) = \chi_2^3(3) = \omega^3 = -1$

(and we have $\chi_2(1) = 1$). This completes the second character.

To compute the third character we can set

$\chi_3(3) = \omega^2$

then

$\chi_3(2) = \chi_3(3^2) = \chi_3^2(3) = \omega^4 = -\omega$

$\chi_3(4) = \chi_3(3^4) = \chi_3^4(3) = \omega^8 = \omega^2$

$\chi_3(5) = \chi_3(3^5) = \chi_3^5(3) = \omega^{10} = -\omega$

$\chi_3(6) = \chi_3(3^3) = \chi_3^3(3) = \omega^6 = 1$

(and we have $\chi_3(1) = 1$). This completes the third character.

To compute the fourth character we can set

$\chi_4(3) = \omega^3 = -1$

then

$\chi_4(2) = \chi_4(3^2) = \chi_4^2(3) = 1$

$\chi_4(4) = \chi_4(3^4) = \chi_4^4(3) = 1$

$\chi_4(5) = \chi_4(3^5) = \chi_4^5(3) = -1$

$\chi_4(6) = \chi_4(3^3) = \chi_4^3(3) = -1$

(and we have $\chi_4(1) = 1$). This completes the fourth character.

To compute the fifth character we can set

$\chi_5(3) = \omega^4 = -\omega$

then

$\chi_5(2) = \chi_5(3^2) = \chi_5^2(3) = \omega^2$

$\chi_5(4) = \chi_5(3^4) = \chi_5^4(3) = \omega^4 = -\omega$

$\chi_5(5) = \chi_5(3^5) = \chi_5^5(3) = \chi_5^4(3) \cdot \chi_5(3) = \omega^2$

$\chi_5(6) = \chi_5(3^3) = \chi_5^3(3) = -\omega^3 = 1$

(and we have $\chi_5(1) = 1$). This completes the fifth character.

Finally, to compute the sixth character we set

$\chi_6(3) = \omega^5 = -\omega^2$

then

$\chi_6(2) = \chi_6(3^2) = \chi_6^2(3) = \omega^4 = -\omega$

$\chi_6(4) = \chi_6(3^4) = \chi_6^4(3) = \omega^8 = \omega^2$

$\chi_6(5) = \chi_6(3^5) = \chi_6^5(3) = -\omega^{10} = \omega$

$\chi_6(6) = \chi_6(3^3) = \chi_6^3(3) = -\omega^6 = -1$

(and we have $\chi_6(1) = 1$). This completes the sixth character.

k = 8

We have $\varphi(8) = 4$ so there are four Dirichlet characters in this case. We consider the four roots of unity

$\omega = e^{2 \pi i/4} = e^{\pi i/2} = i$

$\omega^2 = e^{4 \pi i/4} = e^{\pi i} = -1$

$\omega^3 = e^{6 \pi i/4} = e^{3 \pi i/2} = -i$

$\omega^4 = e^{8 \pi i/4} = e^{2 \pi i} = 1$

In this case, none of the four elements of the set of least positive residues mod $8$ generates the entire set. However, the characters must satisfy the following relations, which restrict the choices:

$\chi(3) \cdot \chi(5) = \chi(15) = \chi(7)$

$\chi(3) \cdot \chi(7) = \chi(21) = \chi(5)$

$\chi(5) \cdot \chi(7) = \chi(35) = \chi(3)$

Each character’s values must be chosen in such a way that these three relations hold.

To compute the second character, suppose we begin by trying to set

$\chi_2(3) = \omega = i$

and

$\chi_2(5) = \omega^2 = -1$

Then we must have

$\chi_2(7) = \chi_2(3) \cdot \chi_2(5) = -i$

but then

$\chi_2(3) \cdot \chi_2(7) = 1 \neq \chi_2(5)$

so this does not work. If instead we try to set

$\chi_2(5) = -i$

then we must have

$\chi_2(7) = \chi_2(3) \cdot \chi_2(5) = 1$

but then

$\chi_2(3) \cdot \chi_2(7) = i \neq \chi_2(5)$

so this does not work either. Computations like these show that $\pm i$ cannot appear in any of the characters mod $8$. All the characters must be formed from $\pm 1$. (Fundamentally, this is due to the fact that the group of least positive residues mod $8$ can be subdivided into four cyclic subgroups of order 2, each of which has characters whose values are the two roots of unity, $1$ and $-1$).

To compute the second character we can set

$\chi_2(3) = 1$

and

$\chi_2(5) = -1$

then we must have

$\chi_2(7) = -1$

and this works.

To compute the third character we can set

$\chi_3(3) = -1$

and

$\chi_3(5) = -1$

then we must have

$\chi_3(7) = 1$

and this works too.

Finally, to compute the fourth character we can set

$\chi_4(3) = -1$

and

$\chi_4(5) = 1$

then we must have

$\chi_4(7) = -1$

and this works too.

k = 9

We have $\varphi(9) = 6$ so there are six Dirichlet characters in this case. We consider the six roots of unity

$\omega = e^{2 \pi i/6} = e^{\pi i/3}$

$\omega^2 = e^{2 \pi i/3}$

$\omega^3 = e^{3 \pi i/3} = e^{\pi i} = -1$

$\omega^4 = \omega \cdot \omega^3 = -\omega$

$\omega^5 = \omega \cdot \omega^4 = -\omega^2$

$\omega^6 = e^{6 \pi i/3} = e^{2\pi i} = 1$

Note that the set of least positive residues mod $9$ is generated by $2$:

$2 \equiv 2$ mod($9$)

$2^2 \equiv 4$ mod($9$)

$2^3 \equiv 8$ mod($9$)

$2^4 \equiv 7$ mod($9$)

$2^5 \equiv 5$ mod($9$)

$2^6 \equiv 1$ mod($9$)

Therefore the non-principal Dirichlet characters will be completely determined by the values of $\chi(2)$. If we set

$\chi_2(2) = \omega$

then

$\chi_2(4) = \chi_2(2^2) = \chi_2^2(2) = \omega^2$

$\chi_2(5) = \chi_2(2^5) = \chi_2^5(2) = \omega^5 = -\omega^2$

$\chi_2(7) = \chi_2(2^4) = \chi_2^4(2) = \omega^4 = -\omega$

$\chi_2(8) = \chi_2(2^3) = \chi_2^3(2) = \omega^3 = -1$

(and we have $\chi_2(1) = 1$). This completes the second character.

To compute the third character we can set

$\chi_3(2) = \omega^2$

then

$\chi_3(4) = \chi_3(2^2) = \chi_3^2(2) = \omega^4 = -\omega$

$\chi_3(5) = \chi_3(2^5) = \chi_3^5(2) = \omega^{10} = \omega^6 \cdot \omega^4 = -\omega$

$\chi_3(7) = \chi_3(2^4) = \chi_3^4(2) = \omega^8 = \omega^6 \cdot \omega^2 = \omega^2$

$\chi_3(8) = \chi_3(2^3) = \chi_3^3(2) = \omega^6 = 1$

(and we have $\chi_3(1) = 1$). This completes the third character.

To compute the fourth character we can set

$\chi_4(2) = \omega^3 = -1$

then

$\chi_4(4) = \chi_4(2^2) = \chi_4^2(2) = 1$

$\chi_4(5) = \chi_4(2^5) = \chi_4^5(2) = -1$

$\chi_4(7) = \chi_4(2^4) = \chi_4^4(2) = 1$

$\chi_4(8) = \chi_4(2^3) = \chi_4^3(2) = -1$

(and we have $\chi_4(1) = 1$). This completes the fourth character.

To compute the fifth character we can set

$\chi_5(2) = \omega^4 = -\omega$

then

$\chi_5(4) = \chi_5(2^2) = \chi_5^2(2) = \omega^2$

$\chi_5(5) = \chi_5(2^5) = \chi_5^5(2) = -\omega^5 = -\omega^3 \cdot \omega^2 = \omega^2$

$\chi_5(7) = \chi_5(2^4) = \chi_5^4(2) = \omega^4 = \omega^3 \cdot \omega = -\omega$

$\chi_5(8) = \chi_5(2^3) = \chi_5^3(2) = -\omega^3 = 1$

(and we have $\chi_5(1) = 1$). This completes the fifth character.

Finally, to compute the sixth character we can set

$\chi_6(2) = \omega^5 = -\omega^2$

then

$\chi_6(4) = \chi_6(2^2) = \chi_6^2(2) = \omega^4 = -\omega$

$\chi_6(5) = \chi_6(2^5) = \chi_6^5(2) = -\omega^{10} = -\omega^6 \cdot \omega^4 = \omega$

$\chi_6(7) = \chi_6(2^4) = \chi_6^4(2) = \omega^8 = \omega^6 \cdot \omega^2 = \omega^2$

$\chi_6(8) = \chi_6(2^3) = \chi_6^3(2) = -\omega^6 = -1$

(and we have $\chi_6(1) = 1$). This completes the sixth character.

k = 10

We have $\varphi(10) = 4$ so there are four Dirichlet characters in this case. We consider the four roots of unity

$\omega = e^{2 \pi i/4} = e^{\pi i/2} = i$

$\omega^2 = e^{4 \pi i/4} = e^{\pi i} = -1$

$\omega^3 = e^{6 \pi i/4} = e^{3 \pi i/2} = -i$

$\omega^4 = e^{8 \pi i/4} = e^{2 \pi i} = 1$

Note that the set of least positive residues mod $10$ is generated by $3$:

$3 \equiv 3$ mod($10$)

$3^2 \equiv 9$ mod($10$)

$3^3 \equiv 7$ mod($10$)

$3^4 \equiv 1$ mod($10$)

Therefore the non-principal Dirichlet characters will be completely determined by the values of $\chi(3)$. If we set

$\chi_2(3) = \omega = i$

then

$\chi_2(7) = \chi_2(3^3) = \chi_2^3(3) = -i$

$\chi_2(9) = \chi_2(3^2) = \chi_2^2(3) = -1$

(and we have $\chi_2(1) = 1$). This completes the second character.

To compute the third character we can set

$\chi_3(3) = \omega^2 = -1$

then

$\chi_3(7) = \chi_3(3^3) = \chi_3^3(3) = -1$

$\chi_3(9) = \chi_3(3^2) = \chi_3^2(3) = 1$

(and we have $\chi_3(1) = 1$). This completes the third character.

Finally, to compute the fourth character we set

$\chi_4(3) = \omega^3 = -i$

then

$\chi_4(7) = \chi_4(3^3) = \chi_4^3(3) = i$

$\chi_4(9) = \chi_4(3^2) = \chi_4^2(3) = -1$

(and we have $\chi_4(1) = 1$). This completes the fourth character.

k = 11

We have $\varphi(11) = 10$ so there are ten Dirichlet characters in this case. We consider the ten roots of unity

$\omega = e^{2 \pi i/10} = e^{\pi i/5}$

$\omega^2 = e^{2 \pi i/5}$

$\omega^3 = e^{3 \pi i/5}$

$\omega^4 = e^{4 \pi i/5}$

$\omega^5 = e^{5 \pi i/5} = e^{\pi i} = -1$

$\omega^6 = -\omega$

$\omega^7 = -\omega^2$

$\omega^8 = -\omega^3$

$\omega^9 = -\omega^4$

$\omega^{10} = -\omega^5 = 1$

Note that the set of least positive residues mod $11$ is generated by $2$:

$2 \equiv 2$ mod($11$)

$2^2 \equiv 4$ mod($11$)

$2^3 \equiv 8$ mod($11$)

$2^4 \equiv 5$ mod($11$)

$2^5 \equiv 10$ mod($11$)

$2^6 \equiv 9$ mod($11$)

$2^7 \equiv 7$ mod($11$)

$2^8 \equiv 3$ mod($11$)

$2^9 \equiv 6$ mod($11$)

$2^{10} \equiv 1$ mod($11$)

Therefore the non-principal Dirichlet characters will be completely determined by the values of $\chi(2)$. If we set

$\chi_2(2) = \omega$

then

$\chi_2(3) = \chi_2(2^8) = \chi_2^8(2) = \omega^8 = -\omega^3$

$\chi_2(4) = \chi_2(2^2) = \chi_2^2(2) = \omega^2$

$\chi_2(5) = \chi_2(2^4) = \chi_2^4(2) = \omega^4$

$\chi_2(6) = \chi_2(2^9) = \chi_2^9(2) = \omega^9 = -\omega^4$

$\chi_2(7) = \chi_2(2^7) = \chi_2^7(2) = \omega^7 = -\omega^2$

$\chi_2(8) = \chi_2(2^3) = \chi_2^3(2) = \omega^3$

$\chi_2(9) = \chi_2(2^6) = \chi_2^6(2) = \omega^6 = -\omega$

$\chi_2(10) = \chi_2(2^5) = \chi_2^5(2) = \omega^5 = -1$

(and we have $\chi_2(1) = 1$). This completes the second character.

To compute the third character we can set

$\chi_3(2) = \omega^2$

then

$\chi_3(3) = \chi_3(2^8) = \chi_3^8(2) = \omega^{16} = -\omega$

$\chi_3(4) = \chi_3(2^2) = \chi_3^2(2) = \omega^4$

$\chi_3(5) = \chi_3(2^4) = \chi_3^4(2) = \omega^8 = -\omega^3$

$\chi_3(6) = \chi_3(2^9) = \chi_3^9(2) = \omega^{18} = -\omega^3$

$\chi_3(7) = \chi_3(2^7) = \chi_3^7(2) = \omega^{14} = \omega^4$

$\chi_3(8) = \chi_3(2^3) = \chi_3^3(2) = \omega^6 = -\omega$

$\chi_3(9) = \chi_3(2^6) = \chi_3^6(2) = \omega^{12} = \omega^2$

$\chi_3(10) = \chi_3(2^5) = \chi_3^5(2) = \omega^{10} = 1$

(and we have $\chi_3(1) = 1$). This completes the third character.

To compute the fourth character we can set

$\chi_4(2) = \omega^3$

then

$\chi_4(3) = \chi_4(2^8) = \chi_4^8(2) = \omega^{24} = \omega^4$

$\chi_4(4) = \chi_4(2^2) = \chi_4^2(2) = \omega^6 = -\omega$

$\chi_4(5) = \chi_4(2^4) = \chi_4^4(2) = \omega^{12} = \omega^2$

$\chi_4(6) = \chi_4(2^9) = \chi_4^9(2) = \omega^{27} = -\omega^2$

$\chi_4(7) = \chi_4(2^7) = \chi_4^7(2) = \omega^{21} = \omega$

$\chi_4(8) = \chi_4(2^3) = \chi_4^3(2) = \omega^9 = -\omega^4$

$\chi_4(9) = \chi_4(2^6) = \chi_4^6(2) = \omega^{18} = -\omega^3$

$\chi_4(10) = \chi_4(2^5) = \chi_4^5(2) = \omega^{15} = -1$

(and we have $\chi_4(1) = 1$). This completes the fourth character.

To compute the fifth character we can set

$\chi_5(2) = \omega^4$

then

$\chi_5(3) = \chi_5(2^8) = \chi_5^8(2) = \omega^{32} = \omega^2$

$\chi_5(4) = \chi_5(2^2) = \chi_5^2(2) = \omega^8 = -\omega^3$

$\chi_5(5) = \chi_5(2^4) = \chi_5^4(2) = \omega^{16} = -\omega$

$\chi_5(6) = \chi_5(2^9) = \chi_5^9(2) = \omega^{36} = -\omega$

$\chi_5(7) = \chi_5(2^7) = \chi_5^7(2) = \omega^{28} = -\omega^3$

$\chi_5(8) = \chi_5(2^3) = \chi_5^3(2) = \omega^{12} = \omega^2$

$\chi_5(9) = \chi_5(2^6) = \chi_5^6(2) = \omega^{24} = \omega^4$

$\chi_5(10) = \chi_5(2^5) = \chi_5^5(2) = \omega^{20} = 1$

(and we have $\chi_5(1) = 1$). This completes the fifth character.

To compute the sixth character we can set

$\chi_6(2) = \omega^5 = -1$

then

$\chi_6(3) = \chi_6(2^8) = \chi_6^8(2) = 1$

$\chi_6(4) = \chi_6(2^2) = \chi_6^2(2) = 1$

$\chi_6(5) = \chi_6(2^4) = \chi_6^4(2) = 1$

$\chi_6(6) = \chi_6(2^9) = \chi_6^9(2) = -1$

$\chi_6(7) = \chi_6(2^7) = \chi_6^7(2) = -1$

$\chi_6(8) = \chi_6(2^3) = \chi_6^3(2) = -1$

$\chi_6(9) = \chi_6(2^6) = \chi_6^6(2) = 1$

$\chi_6(10) = \chi_6(2^5) = \chi_6^5(2) = -1$

(and we have $\chi_6(1) = 1$). This completes the sixth character.

To compute the seventh character we can set

$\chi_7(2) = \omega^6 = -\omega$

then

$\chi_7(3) = \chi_7(2^8) = \chi_7^8(2) = \omega^8 = -\omega^3$

$\chi_7(4) = \chi_7(2^2) = \chi_7^2(2) = \omega^2$

$\chi_7(5) = \chi_7(2^4) = \chi_7^4(2) = \omega^4$

$\chi_7(6) = \chi_7(2^9) = \chi_7^9(2) = -\omega^9 = \omega^4$

$\chi_7(7) = \chi_7(2^7) = \chi_7^7(2) = -\omega^7 = \omega^2$

$\chi_7(8) = \chi_7(2^3) = \chi_7^3(2) = -\omega^3$

$\chi_7(9) = \chi_7(2^6) = \chi_7^6(2) = \omega^6 = -\omega$

$\chi_7(10) = \chi_7(2^5) = \chi_7^5(2) = -\omega^5 = 1$

(and we have $\chi_7(1) = 1$). This completes the seventh character.

To compute the eighth character we can set

$\chi_8(2) = \omega^7 = -\omega^2$

then

$\chi_8(3) = \chi_8(2^8) = \chi_8^8(2) = \omega^{16} = -\omega$

$\chi_8(4) = \chi_8(2^2) = \chi_8^2(2) = \omega^4$

$\chi_8(5) = \chi_8(2^4) = \chi_8^4(2) = \omega^8 = -\omega^3$

$\chi_8(6) = \chi_8(2^9) = \chi_8^9(2) = -\omega^{18} = \omega^3$

$\chi_8(7) = \chi_8(2^7) = \chi_8^7(2) = -\omega^{14} = -\omega^4$

$\chi_8(8) = \chi_8(2^3) = \chi_8^3(2) = -\omega^6 = \omega$

$\chi_8(9) = \chi_8(2^6) = \chi_8^6(2) = \omega^{12} = \omega^2$

$\chi_8(10) = \chi_8(2^5) = \chi_8^5(2) = -\omega^{10} = -1$

(and we have $\chi_8(1) = 1$). This completes the eighth character.

To compute the ninth character we can set

$\chi_9(2) = \omega^8 = -\omega^3$

then

$\chi_9(3) = \chi_9(2^8) = \chi_9^8(2) = \omega^{24} = \omega^4$

$\chi_9(4) = \chi_9(2^2) = \chi_9^2(2) = \omega^6 = -\omega$

$\chi_9(5) = \chi_9(2^4) = \chi_9^4(2) = \omega^{12} = \omega^2$

$\chi_9(6) = \chi_9(2^9) = \chi_9^9(2) = -\omega^{27} = \omega^2$

$\chi_9(7) = \chi_9(2^7) = \chi_9^7(2) = -\omega^{21} = -\omega$

$\chi_9(8) = \chi_9(2^3) = \chi_9^3(2) = -\omega^9 = \omega^4$

$\chi_9(9) = \chi_9(2^6) = \chi_9^6(2) = \omega^{18} = -\omega^3$

$\chi_9(10) = \chi_9(2^5) = \chi_9^5(2) = -\omega^{15} = 1$

(and we have $\chi_9(1) = 1$). This completes the ninth character.

Finally, to compute the tenth character we set

$\chi_{10}(2) = \omega^9 = -\omega^4$

then

$\chi_{10}(3) = \chi_{10}(2^8) = \chi_{10}^8(2) = \omega^{32} = \omega^2$

$\chi_{10}(4) = \chi_{10}(2^2) = \chi_{10}^2(2) = \omega^8 = -\omega^3$

$\chi_{10}(5) = \chi_{10}(2^4) = \chi_{10}^4(2) = \omega^{16} = -\omega$

$\chi_{10}(6) = \chi_{10}(2^9) = \chi_{10}^9(2) = -\omega^{36} = \omega$

$\chi_{10}(7) = \chi_{10}(2^7) = \chi_{10}^7(2) = -\omega^{28} = \omega^3$

$\chi_{10}(8) = \chi_{10}(2^3) = \chi_{10}^3(2) = -\omega^{12} = -\omega^2$

$\chi_{10}(9) = \chi_{10}(2^6) = \chi_{10}^6(2) = \omega^{24} = \omega^4$

$\chi_{10}(10) = \chi_{10}(2^5) = \chi_{10}^5(2) = -\omega^{20} = -1$

(and we have $\chi_{10}(1) = 1$). This completes the tenth character.

The remaining ten Dirichlet character tables which follow in this note can be calculated analogously (the details are not shown).

k = 12

k = 13

k = 14

k = 15

k = 16

k = 17

k = 18

k = 19

k = 20

k = 21

# Note on Generalized Convolution in Number Theory

In Tom Apostol’s famous Introduction to Analytic Number Theory there is a section about generalized convolutions which sometimes causes confusion (see Apostol, Chapter 2, p.39 and also my Advanced Number Theory Note #3). In this short note I want to quickly try to clarify this bit.

Let $F$ denote a real or complex-valued function defined on the positive real axis such that $F(x) = 0$ for $0 < x < 1$.

$\alpha$ is any arithmetical function.

Generalized convolution is then defined by

$(\alpha \circ F)(x)= \sum_{n \leq x} \alpha(n)F(\frac{x}{n})$

Apostol says:

“If $F(x) = 0$ for all nonintegral values of $x$, the restriction of $F$ to integers is an arithmetical function and we find that $(\alpha \circ F)(m) =(\alpha \ast F)(m)$.”

Here $(\alpha \ast \beta)(n) = \sum_{d | n} \alpha(n)\beta(\frac{n}{d})$.

The question that sometimes arises in some form or other in relation to this is: why does $F(x)$ have to be $0$ for all nonintegral values of $x$ for this to work? Is the point that we want $F(\frac{x}{n})$ to be $0$ when $\frac{x}{n}$ is not an integer?

The answer is yes. For example, to isolate $F$, take $\alpha$ to be the unit function $u$. Then the generalized convolution for integer $m \geq 1$ is

$(u \circ F)(m) = \sum_{n \leq m} F(\frac{m}{n})$

If $F(\frac{m}{n}) = 0$ whenever $\frac{m}{n}$ is not an integer, the above sum reduces to

$\sum_{n | m} F(\frac{m}{n}) = (u \ast F)(m)$

I think Apostol could have simply said “If $F(x) = 0$ for all nonintegral values of $x$, we find that $(\alpha \circ F)(m) = (\alpha \ast F)(m)$ for all integers $m \geq 1$…”

# Advanced Number Theory Note #13: A study of primitive Dirichlet characters

In this (rather long) note, intended mainly as a technical memo for myself, I want to explore in detail the concept of a primitive Dirichlet character mod k, and the role of induced moduli in determining primitive and non-primitive Dirichlet characters. (I plan to expand further on some aspects of primitive characters in a couple of subsequent notes). As usual I will try herein to illustrate key ideas with concrete examples.

Dirichlet characters form a group and satisfy other strong properties, such as being completely multiplicative, which make them mathematically interesting in their own right as well as useful. (See my Note about them). For example, one of their most important roles is in Dirichlet L-functions which in turn are used in the proof of the prime number theorem, something I will explore in great detail in future notes. Primitive Dirichlet characters in particular are important because all Dirichlet characters can be viewed as extensions of primitive ones. The primitive Dirichlet characters are the irreducible ones from which the others are made, somewhat analogously to how prime numbers are the irreducible integers from which other integers are made.

Primitive Dirichlet characters are defined using the concept of an induced modulus which I have already used in a couple of earlier notes. In one previous note I tried to formulate an intuitively simple proof of a result concerning Dirichlet characters with two induced moduli. The concept of an induced modulus was also central to the separability of Gauss sums which I explored in Advanced Number Theory Note #12. I briefly mentioned its relevance in the preamble to Theorem 4 there, and the basic definition of an induced modulus is actually contained in equation (3) in Theorem 4 of that note.

Definition of induced modulus. Let $\chi$ be a Dirichlet character mod $k$ and let $d$ be any positive divisor of $k$. The number $d$ is called an induced modulus for $\chi$ if we have

$\chi(a) = 1$    whenever    $gcd(a, k) = 1$    and    $a \equiv 1$   (mod $d$)            (1)

Example: Suppose $\chi$ is the nonprincipal character mod 6. The reduced residue classes mod 6 are $\{1, 5\}$ so there are two Dirichlet characters mod 6. One is the principal character taking the value 1 for both 1 and 5. The other is the nonprincipal character $\chi$ which must have the square roots of unity as its values, so $\chi(1) = 1$, $\chi(5) = -1$. The proper divisors of $k = 6$ are $1$, $2$, $3$. Now consider any $a$ satisfying $gcd(a, 6) = 1$ and $a \equiv 1$ (mod 3). Then we must necessarily have $a \equiv 1$ (mod 6), so $\chi(a) = \chi(1) = 1$. Thus, $d = 3$ is an induced modulus of $\chi$. But note that neither $d = 1$ nor $d = 2$ are induced moduli. A counterexample for both is the case $a = 5$. We have $5 \equiv 1$ (mod 1) and $gcd(5, 6) = 1$, but $\chi(5) = -1 \neq 1$. Similarly, we have $5 \equiv 1$ (mod 2) and $gcd(5, 6) = 1$, but $\chi(5) = -1 \neq 1$. Thus, the nonprincipal character mod 6 has only one induced modulus smaller than 6. END

In the above example the divisor 1 of 6 was found not to be an induced modulus of the nonprincipal character mod 6. The following theorem shows that there is only one character for each mod k such that 1 is an induced modulus, and that is the principal character.

Theorem 1. Let $\chi$ be a Dirichlet character mod $k$. Then 1 is an induced modulus for $\chi$ if and only if $\chi$ is the principal character $\chi_1$.

Proof: Suppose first that $\chi = \chi_1$. Then $\chi(a) = 1$ for all $a$ which are relatively prime to $k$. But since all such integers $a$ also satisfy $a \equiv 1$ (mod 1), the number 1 is an induced modulus. Conversely, suppose that the number 1 is an induced modulus. Then $\chi(a) = 1$ whenever $gcd(a, k) = 1$ and so it must be the case that $\chi = \chi_1$ since both $\chi$ and $\chi_1$ vanish when the argument is not coprime with $k$. QED

Observe that for any Dirichlet character mod $k$ the modulus $k$ itself is an induced modulus, because $k$ is a divisor of $k$ and $\chi(a) = 1$ whenever $gcd(a, k) = 1$ and $a \equiv 1$ (mod $k$). The Dirichlet character is called primitive when it has no other induced moduli. Formally:

Definition of primitive characters. A Dirichlet character $\chi$ mod $k$ is said to be primitive mod $k$ if it has no induced modulus $d < k$. Thus, a primitive Dirichlet character mod $k$ will be such that, for every proper divisor $d$ of $k$, there is some integer $a \equiv 1$ (mod $d$) such that $gcd(a, k) = 1$ and $\chi(a) \neq 1$.

Note that for any modulus $k > 1$, the principal character $\chi_1$ will not be primitive since it will have $1 < k$ as an induced modulus. However, as the next theorem shows, if the modulus $k$ is a prime number, then every nonprincipal character mod $k$ is primitive.

Theorem 2. Every nonprincipal character $\chi$ modulo a prime $p$ is a primitive character mod $p$.

Proof: The only proper divisor of $p$ is 1, but since $\chi$ is not a principal character the number 1 cannot be an induced modulus, so $\chi$ must be primitive since it has no induced modulus $< p$. QED

The next theorem establishes an important and useful property of Dirichlet characters, namely that $d$ is an induced modulus for $\chi$ mod $k$ if and only if $\chi$ is periodic mod $d$ on those integers relatively prime to $k$. This can sometimes be used to identify induced moduli very quickly by looking at the pattern of a Dirichlet character’s values (see examples below).

Theorem 3. Let $\chi$ be a Dirichlet character mod $k$ and assume $d|k$ with $d > 0$. Then $d$ is an induced modulus for $\chi$ if and only if

$\chi(a) = \chi(b)$    whenever    $gcd(a, k) = gcd(b, k) = 1$    and    $a \equiv b$     (mod $d$)       (2)

Proof: Observe first that if (2) holds, then simply setting $b = 1$ gives equation (1), so $d$ must be an induced modulus if (2) holds. Going the other way, suppose that $d$ is an induced modulus. We will prove that then (2) must hold. Choose $a$ and $b$ such that

$gcd(a, k) = gcd(b, k) = 1$    and    $a \equiv b$   (mod $d$)

The following argument then shows $\chi(a) = \chi(b)$. Let $a\prime$ be the reciprocal of $a$ mod $k$, so that

$aa\prime \equiv 1$   (mod $k$)

This reciprocal exists because $gcd(a, k) = 1$. And note that also $gcd(a\prime, k) = 1$, so then we must have $gcd(aa\prime, k) = 1$. Since $d|k$, we can deduce immediately that

$aa\prime \equiv 1$ (mod $d$)

and therefore it must be the case that $\chi(aa\prime) = 1$ since $d$ is an induced modulus. But since $a \equiv b$ (mod $d$) we deduce that

$aa\prime \equiv ba\prime = 1$ (mod $d$)

and therefore

$\chi(aa\prime) = \chi(ba\prime)$

so

$\chi(a)\chi(a\prime) = \chi(b)\chi(a\prime)$

But $\chi(a\prime) \neq 0$ since $\chi(a)\chi(a\prime) = 1$, so we can cancel $\chi(a\prime)$ to deduce that $\chi(a) = \chi(b)$ which is what we needed to prove. QED

The following examples illustrate the situation.

Example: The following table shows the values of one of the Dirichlet characters $\chi$ mod 9.

We can see straight away that this table is periodic modulo 3 so by Theorem 3 it must be the case that 3 is an induced modulus for $\chi$. In fact, $\chi$ acts like the following Dirichlet character $\psi$

in the sense that $\chi(n) = \psi(n)$ for all $n$. Here, $\psi$ is a primitive Dirichlet character and $\chi$ is a non-primitive character called an extension of $\psi$.

Whenever $\chi$ is an extension of a character $\psi$ modulo $d$, then $d$ will be an induced modulus for $\chi$ because we will necessarily have $\chi(a) = \chi(b)$ whenever $gcd(a, k) = gcd(b, k) = 1$ and $a = b$ (mod $d$). In the above case we have for example $\chi(8) = \chi(2)$ with $gcd(8, 9) = gcd(2, 9) = 1$ and $8 = 2$ (mod $3$). END

Example: Here is an example showing that it is possible for a character $\chi$ mod $k$ to have an induced modulus $d < k$ without $\chi$ being an extension of any character $\psi$ mod $d$. The case is the one considered in the first example above, where $\chi$ is the (only) nonprincipal character mod 6.

As seen earlier, in this case the number 3 is an induced modulus because $\chi(n) = 1$ whenever $gcd(n, 6) = 1$ and $n \equiv 1$ (mod $3$). (There is only one such $n$ in this case, namely $n = 1$). However, $\chi$ is not an extension of any character $\psi$ modulo 3, because the only characters modulo 3 are the nonprincipal one shown above and the principal character

Since $\chi(2) = 0$, we see immediately that $\chi$ cannot be an extension of either $\psi$ or $\psi_1$. END

Example: There are four reduced residue classes mod 8, namely 1, 3, 5, 7, and thus four Dirichlet characters mod 8 as follows.

We look for induced moduli among the proper divisors of 8 other than 1, namely 2, 4. We see immediately that $\chi_2(5) \neq 1$, $\chi_3(7) \neq 1$ and $\chi_4(5) \neq 1$ are counterexamples for 2 being an induced modulus in the cases $\chi_2$, $\chi_3$ and $\chi_4$. Also $\chi_2(5) \neq 1$ and $\chi_4(5) \neq 1$ are counterexamples for 4 being an induced modulus in the cases $\chi_2$ and $\chi_4$. However, it is immediately apparent that $\chi_3$ is periodic mod 4, so 4 must be an induced modulus for $\chi_3$. END

Example: There are four reduced residue classes mod 12, namely 1, 5, 7, 11, and thus four Dirichlet characters mod 12 as follows.

Again we look for induced moduli among the proper divisors of 12 other than 1, namely 2, 3, 4, 6. We see immediately that $\chi_2(5) \neq 1$, $\chi_3(7) \neq 1$ and $\chi_4(5) \neq 1$ are counterexamples for 2 being an induced modulus in the cases $\chi_2$, $\chi_3$ and $\chi_4$.
Also $\chi_2(5) \neq 1$ and $\chi_4(5) \neq 1$ are counterexamples for 4 being an induced modulus in the cases $\chi_2$ and $\chi_4$. However, whenever $gcd(a, 12) = 1$ and $a \equiv 1$ (mod $4$) we have $\chi_3(a) = 1$ so 4 is an induced modulus for $\chi_3$.
$\chi_2(7) \neq 1$ and $\chi_3(7) \neq 1$ are counterexamples for 3 and 6 being induced moduli in the cases $\chi_2$, $\chi_3$. However, whenever $gcd(a, 12) = 1$ and $a \equiv 1$ (mod $3$) we have $\chi_4(a) = 1$ so 3 is an induced modulus for $\chi_4$. We also see that $\chi_4$ is periodic mod 6, so it follows from Theorem 3 that 6 must be an induced modulus for $\chi_4$. END

The above examples also help to clarify the following theorem.

Theorem 4. Let $\chi$ be a Dirichlet character modulo $k$, and assume $d|k$ and $d > 0$. Then the following two statements are equivalent:
(a). $d$ is an induced modulus for $\chi$
(b). There is a character $\psi$ modulo $d$ such that

$\chi(n) = \psi(n)\chi_1(n)$    for all   $n$                (3)

where $\chi_1$ is the principal character modulo $k$.

Example: In examples above we saw that 4 is an induced modulus for $\chi_3$ mod 8 as well as $\chi_3$ mod 12. Therefore there must be a character $\psi$ modulo 4 such that

$\chi_3(n) = \psi(n)\chi_1(n)$      for all   $n$

in both cases. This character is the only nonprincipal character mod 4, which takes the values $\psi(1) = 1$ and $\psi(3) = -1$.

Similarly, we saw that 3 is an induced modulus for $\chi_4$ mod 12, so there must be a character $\psi$ modulo 3 such that

$\chi_4(n) = \psi(n)\chi_1(n)$      for all   $n$

This character is the only nonprincipal character mod 3, which takes the values $\psi(1) = 1$ and $\psi(2) = -1$.

Finally, we saw that 6 is an induced modulus for $\chi_4$ mod 12, so there must be a character $\psi$ modulo 6 such that

$\chi_4(n) = \psi(n)\chi_1(n)$      for all   $n$

This character is the only nonprincipal character mod 6, which takes the values $\psi(1) = 1$ and $\psi(5) = -1$. END

Proof of Theorem 4: First, we assume (b) holds and then show that (a) must be true. If (b) holds we can choose any $n$ satisfying $gcd(n, k) = 1$ and $n \equiv 1$ (mod $d$) and for this $n$ we will then have $\chi_1(n) = 1$ and also $\psi(n) = 1$ (because by assumption $\psi$ is a character mod $d$, and $n \equiv 1$ (mod $d$)). Therefore we will have $\chi(n) = 1$ for any such $n$ and so $d$ is an induced modulus, which proves (a).

Going the other way, we now assume that (a) holds and try to find a character $\psi$ modulo $d$ for which equation (3) above holds. We can obtain the desired character by defining $\psi(n)$ as follows. If $gcd(n, d) > 1$, let $\psi(n) = 0$. In this case we also have $gcd(n, k) > 1$ (because $d|k$) so equation (3) holds because both sides are zero.

If $gcd(n, d) = 1$ then there exists an integer $m$ such that

$m \equiv n$ (mod $d$) and $gcd(m, k) = 1$

[This can be proved immediately with Dirichlet’s theorem on primes in arithmetic progressions. (See my Facebook Note for a detailed discussion of Dirichlet’s theorem and its proof). The arithmetic progression $xd + n$ contains infinitely many primes. Simply choose one that does not divide $k$ and call it $m$].

Having chosen $m$, which is unique modulo $d$, we then define

$\psi(n) = \chi(m) = \chi(n + xd)$

The number $\psi$ is then a well defined character mod $d$. It takes equal nonzero values at numbers which are congruent mod $d$ and coprime with $d$, and takes the value zero by definition at numbers which are not coprime with $d$.

We now verify that equation (3) holds for all $n$. If $gcd(n, k) = 1$, then it must also be the case that $gcd(n, d) = 1$, so $\psi(n) = \chi(m)$ for some $m \equiv n$ (mod $d$). So we have $gcd(n, k) = 1$, $gcd(m, k) = 1$, and $m \equiv n$ (mod $d$) and since $d$ is an induced modulus by (a) it then follows from Theorem 3 above that

$\chi(n) = \chi(m) = \psi(n) = \psi(n)\chi_1(n)$

where the last equality holds since $\chi_1(n) = 1$ for all $n$. This confirms that (b) holds in the case $gcd(n, k) = 1$.

If $gcd(n, k) > 1$, then $\chi(n) = \chi_1(n) = 0$ and both sides of (3) are zero. This confirms that (b) holds in the case $gcd(n, k) > 1$, so (b) holds for all $n$ if (a) is true. QED

It is useful to introduce the following terminology at this stage.

Definition. Let $\chi$ be a Dirichlet character mod $k$. The smallest induced modulus $d$ for $\chi$ is called the conductor of $\chi$.

The following theorem finally establishes the role that primitive Dirichlet characters play as the building blocks of Dirichlet characters generally.

Theorem 5. Every Dirichlet character $\chi$ mod $k$ can be expressed as a product

$\chi(n) = \psi(n)\chi_1(n)$      for all    $n$                      (4)

where $\chi_1$ is the principal character mod $k$ and $\psi$ is a primitive character modulo the conductor of $\chi$.

Proof: Let $d$ be the conductor of $\chi$. We already know from Theorem 4 that $\chi$ can be expressed as a product of the form (4), where $\psi$ is a character mod $d$. To prove Theorem 5 we therefore only need to prove the additional claim that $\psi$ is primitive mod $d$.

The proof will be by contradiction, assuming that $\psi$ is not primitive mod $d$. If $\psi$ is not primitive mod $d$ there is a proper divisor $q$ of $d$ which is an induced modulus for $\psi$. In equation (4) choose any $n$ such that

$gcd(n, k) = 1$      and      $n \equiv 1$   (mod $q$)

Then we will also have $gcd(n, q) = 1$ (since $q|k$) and since $q$ is an induced modulus for $\psi$ we must have $\psi(n) = 1$. But then equation (4) says

$\chi(n) = \psi(n)\chi_1(n) = \psi(n) = 1$      for all     $n$

so $q$ is also an induced modulus for $\chi$ which is smaller than $d$. This is a contradiction since $d$ is supposed to be the conductor of $\chi$. Therefore the assumption that $\psi$ is not primitive mod $d$ in (4) must be false. QED