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

Gauss 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 pth 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 pth 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

Legendre 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:

LegendreProperties

QuadraticCharacterOf2

QuadraticReciprocity

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:

mod 07

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:

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

Polya 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 kth 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 nth 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

dI 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

mod 02

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

mod 03

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

mod 04

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

mod 05

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

mod 06

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

mod 07

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

mod 08

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

mod 09

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

mod 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

mod 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

mod 12

k = 13

mod 13

k = 14

mod 14

k = 15

mod 15

k = 16

mod 16

k = 17

mod 17

k = 18

mod 18

k = 19

mod 19

k = 20

mod 20

k = 21

mod 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

Image

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.

Image

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

Image

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.

Image

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

Image

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.

Image

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.

Image

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