Quadratic residues ask whether a finite-field element is a square. Higher power residues ask the same question for cubes, fourth powers and general k-th powers. Multiplicative characters turn those membership questions into roots-of-unity values, and Jacobi sums compress the resulting residue patterns into exact algebraic integers.
This is where modular arithmetic begins to meet cyclotomic arithmetic directly. A quadratic character takes values ±1. A quartic character naturally takes values among 1,i,−1,−i. Cubic characters take values in the cube roots of unity. Their sums therefore live not merely in Z but in Gaussian, Eisenstein or more general cyclotomic integer rings.
This is Guide 32 in the Bukit Timah Tutor Computational Number Theory series. It closes Batch 08 by extending Guide 5: Quadratic Residues, Guide 29: Primitive Roots and Cyclotomic Polynomials and Guide 30: Gaussian Integers.
1. The k-th power map
Let G be a cyclic group of order N. Consider
φ_k:G→G, φ_k(x)=x^k.
If g generates G, then
φ_k(g^t)=g^(kt).
The kernel consists of exponents t satisfying
kt≡0 (mod N).
Therefore
|ker φ_k|=gcd(k,N).
2. Number of k-th powers
By the homomorphism theorem, the image has size
N/gcd(k,N).
Thus only that fraction of nonzero group elements are k-th powers.
For F_p*, N=p−1.
If gcd(k,p−1)=1, the map x→x^k is a permutation of F_p*: every nonzero element has a unique k-th root.
3. Membership criterion
Let d=gcd(k,N). An element a in a cyclic group of order N is a k-th power exactly when
a^(N/d)=1.
Proof: if a=g^s, then a lies in the image of x→x^k exactly when the congruence
kt≡s (mod N)
is solvable, which occurs exactly when d divides s. That is equivalent to
g^(sN/d)=1.
4. How many k-th roots?
If a is a nonzero k-th power, then the equation
x^k=a
has exactly
d=gcd(k,N)
solutions in G.
If a is not in the image, it has zero solutions.
This clean zero-or-d rule is one reason cyclic-group representation is so useful.
5. Quartic residues modulo 17
F17* has order16. For k=4,
d=gcd(4,16)=4.
Therefore the nonzero fourth powers form a subgroup of size
16/4=4.
The membership criterion is
a^4=1 (mod17).
The quartic residues are
{1,4,13,16}.
6. Explicit fourth roots
For example,
6²=36≡2 (mod17) 6⁴≡4 (mod17).
Thus 4 is a quartic residue.
Because d=4, the equation
x⁴=4 (mod17)
has exactly four nonzero solutions.
A complete root-finding algorithm can use a primitive root: write 4=g^s and solve 4t≡s mod16.
7. Cubic residues modulo 13
F13* has order12. For k=3,
d=gcd(3,12)=3.
The image has four elements, and the membership test is
a^4=1 (mod13).
The nonzero cubic residues are
{1,5,8,12}.
Every member has exactly three cube roots.
8. Primitive roots turn residue membership into exponent divisibility
Let g generate F_p*. Write
a=g^s.
Then a is a k-th power exactly when
gcd(k,p−1) | s.
So higher power residuosity is a subgroup-membership problem in exponent space.
This connects the subject directly to discrete logarithms: if the log s is known, residuosity is immediate. Character methods can test membership without recovering the full discrete logarithm.
9. Multiplicative characters
A multiplicative character χ on F_p* is a group homomorphism from F_p* into complex roots of unity.
If g is primitive and χ has order m dividing p−1, choose
χ(g)=ζ_m=e^(2πi/m).
Then
χ(g^t)=ζ_m^t.
Extend nontrivial characters to zero by setting χ(0)=0.
10. Quadratic character as the first case
For m=2, ζ_2=−1. The resulting character is the Legendre symbol:
χ(a)=(a/p).
Squares map to1 and nonsquares map to−1.
Thus the familiar quadratic-residue indicator is simply an order-two multiplicative character.
11. Quartic character modulo 5
F5* is cyclic of order4 with primitive root2.
Define χ by
χ(2)=i.
The powers of2 modulo5 are
2^0=1, 2^1=2, 2^2=4, 2^3=3.
Therefore
χ(1)=1, χ(2)=i, χ(4)=−1, χ(3)=−i, χ(0)=0.
12. Character kernels detect power subgroups
When m divides p−1, the kernel of an order-m character consists of the m-th powers in F_p*.
Indeed, writing a=g^t,
χ(a)=1
exactly when t≡0 mod m.
Thus a quartic character can distinguish residue classes more finely than the Legendre symbol.
13. Orthogonality
For a nontrivial multiplicative character χ on F_p*,
Σ_(a in F_p*) χ(a)=0.
This follows because multiplying the summation variable by an element b with χ(b)≠1 leaves the set unchanged but multiplies the whole sum by χ(b).
Character orthogonality is the engine behind many exact counting formulas.
14. Indicators from characters
Suppose m divides p−1 and χ has order m. The indicator that a nonzero element a is an m-th power can be written
1/m · Σ_(j=0 to m−1) χ(a)^j.
If χ(a)=1, the sum is m. Otherwise the roots-of-unity geometric series is zero.
This converts subgroup membership into a finite character sum.
15. Additive characters and Gauss sums
A standard additive character on F_p is
e_p(x)=exp(2πix/p).
For a multiplicative character χ, the Gauss sum is
τ(χ)=Σ_(x mod p) χ(x)e_p(x).
For nontrivial χ, the classical magnitude is
|τ(χ)|=√p.
The phase contains deeper arithmetic information.
16. Jacobi sums
For multiplicative characters χ and ψ, define
J(χ,ψ)=Σ_(x mod p) χ(x)ψ(1−x).
When χ,ψ and χψ are nontrivial,
J(χ,ψ)=τ(χ)τ(ψ)/τ(χψ)
and
|J(χ,ψ)|=√p.
Unlike a generic complex approximation, J often lies exactly in a cyclotomic integer ring.
17. Worked quartic Jacobi sum modulo 5
Use the quartic character χ defined by χ(2)=i.
Compute
J(χ,χ)=Σ_(x=0 to4) χ(x)χ(1−x).
The x=0 and x=1 terms vanish because χ(0)=0.
For x=2:
χ(2)χ(4)=i(−1)=−i.
For x=3:
χ(3)χ(3)=(−i)²=−1.
For x=4:
χ(4)χ(2)=(−1)i=−i.
Therefore
J(χ,χ)=−1−2i.
18. The norm of the Jacobi sum
Its Gaussian norm is
N(−1−2i)=1+4=5.
Thus
|J(χ,χ)|=√5,
exactly matching the general magnitude theorem.
This is a striking return path: a finite-field character sum has become a Gaussian integer whose norm is the underlying prime.
19. Why Gaussian integers appear for quartic characters
A quartic character takes values in the fourth roots of unity
{1,i,−1,−i}.
Therefore sums of quartic character values naturally lie in
Z[i]=Z[ζ_4].
Guide30’s Gaussian arithmetic is not merely adjacent background. It is the natural coefficient ring for quartic character sums.
20. Cubic characters and Eisenstein integers
A cubic character takes values in
{1,ω,ω²},
ω=e^(2πi/3),
ω²+ω+1=0.
Its exact character sums live naturally in the Eisenstein integer ring
Z[ω].
This ring has norm
N(a+bω)=a²−ab+b².
Cubic reciprocity is most naturally formulated in this arithmetic environment.
21. General cyclotomic integers
For an m-th order character, values lie in the cyclotomic field
Q(ζ_m).
The natural exact arithmetic ring is its ring of integers, usually Z[ζ_m] for cyclotomic fields.
Gauss and Jacobi sums are therefore algebraic integers with Galois conjugates obtained by sending
ζ_m → ζ_m^a
for a coprime to m.
22. Galois action on character sums
Changing a character χ to χ^a corresponds to a cyclotomic Galois automorphism.
Thus several character sums that look different numerically are algebraic conjugates.
Computationally, this can reduce work: calculate one exact algebraic object and obtain related sums by automorphism rather than recomputing every finite-field sum independently.
23. Jacobi sums and residue distribution
Character sums count solutions by encoding congruence conditions as roots-of-unity weights.
For example, the number of solutions to equations involving powers can be expressed by expanding power-residue indicators into characters and interchanging sums.
The resulting expressions produce Jacobi sums naturally.
This is one route from elementary congruence counting to zeta functions of diagonal curves and more advanced arithmetic geometry.
24. Higher reciprocity
Quadratic reciprocity describes when one odd prime is a square modulo another.
Quartic and cubic reciprocity refine this question for fourth and third powers, but their cleanest statements require enlarging the coefficient ring.
Quartic reciprocity is naturally expressed in Gaussian integers; cubic reciprocity in Eisenstein integers. General power reciprocity belongs to cyclotomic fields and class-field-theoretic structures.
The computational lesson is important: a difficult residue question over Z may become more structured after adjoining the relevant roots of unity.
25. Solving x^k=a using a primitive root
If p is prime and g primitive, write
a=g^s.
Then x=g^t solves x^k=a exactly when
kt≡s (mod p−1).
Use the linear-congruence algorithm from Euclid.
This gives all roots once s is known. The expensive step may be finding the discrete logarithm s.
26. Solving without a full discrete logarithm
For special k, dedicated root algorithms can avoid solving a generic discrete logarithm.
Square roots use Tonelli–Shanks. Cube or fourth-root extraction can exploit factorisation of p−1, subgroup decomposition and exponent inversion when gcd(k,p−1)=1.
When gcd(k,p−1)>1, one must first test residuosity and then resolve the kernel multiplicity.
27. Character tables from discrete logs
For a small field, build a discrete-log table relative to primitive root g. Then an order-m character is computed by
χ(g^t)=ζ_m^t.
This is ideal for teaching and verification.
For large fields, one should not compute a full discrete-log table merely to evaluate a character if a direct residue-symbol algorithm is available.
28. Exact versus floating character arithmetic
Using complex floating approximations to ζ_m can hide exact cancellations.
For small m, represent character values symbolically: Gaussian pairs for m=4, Eisenstein pairs for m=3 or6, and polynomial residue classes in Z[X]/(Φ_m) more generally.
Then Jacobi sums are exact algebraic integers rather than decimals that merely appear close to one.
29. Verification of a Jacobi sum
A finite-field Jacobi sum can be checked directly from its definition for small p.
Then test algebraic identities:
J · conjugate(J) = p
in the quartic example.
For larger computations, use independent character implementations and exact cyclotomic arithmetic.
30. Common mistakes
1. Using a^((p−1)/k)=1 as the general k-th-power test without replacing k by gcd(k,p−1). 2. Assuming every k-th power has one root. 3. Forgetting χ(0)=0 for nontrivial finite-field multiplicative characters.
4. Treating character values as ordinary integers. 5. Ignoring unit/cyclotomic coefficient rings. 6. Applying |J|=√p without the required nontrivial-character hypotheses. 7. Confusing the Jacobi symbol with a Jacobi sum. 8. Replacing exact cyclotomic arithmetic with floating approximations too early.
31. Practice set
1. In a cyclic group of order N, how large is the kernel of x→x^k? 2. How large is the image? 3. State the k-th-power membership criterion. 4. How many roots does a solvable x^k=a equation have?
5. List the quartic residues modulo17. 6. Verify that4 is one. 7. List the cubic residues modulo13. 8. Define a multiplicative character.
9. Give the quartic character values modulo5 with χ(2)=i. 10. State multiplicative-character orthogonality. 11. Define a Gauss sum. 12. Define a Jacobi sum.
13. Compute J(χ,χ) for the quartic character modulo5. 14. Compute its norm. 15. Why do quartic sums live in Gaussian integers? 16. Where do cubic character sums naturally live?
32. Answers
1. gcd(k,N). 2. N/gcd(k,N). 3. a^(N/d)=1 where d=gcd(k,N). 4. d roots if solvable, otherwise none.
5. {1,4,13,16}. 6. 6⁴≡4 mod17. 7. {1,5,8,12}. 8. A homomorphism from the multiplicative finite-field group to roots of unity.
9. χ(1)=1, χ(2)=i, χ(4)=−1, χ(3)=−i, with χ(0)=0. 10. The sum of a nontrivial character over F_p* is zero. 11. Σχ(x)e_p(x). 12. Σχ(x)ψ(1−x).
13. −1−2i. 14. 5. 15. Their character values lie in the fourth roots of unity, whose integer ring is Z[i]. 16. In Eisenstein/cyclotomic arithmetic Z[ω].
Sources and further study
Victor Shoup, A Computational Introduction to Number Theory and Algebra, develops finite cyclic groups, finite fields and character-related computational foundations. NIST DLMF Chapter 27 is a reference for classical number-theoretic functions and residue structures. For a deeper treatment of exact Gauss and Jacobi sums, see Bruce Berndt, Ronald Evans and Kenneth Williams, Gauss and Jacobi Sums.
Computational Number Theory — Batch 08
Guide 29: Primitive Roots, Multiplicative Orders, Carmichael λ and Cyclotomic Polynomials
Guide 30: Gaussian Integers, Euclidean GCD and Sums of Two Squares
Guide 31: Cornacchia’s Algorithm, Norm Equations and Quadratic-Form Representations
Guide 32: Higher Power Residues, Character Sums, Jacobi Sums and Cyclotomic Arithmetic