Algebraic number theory enlarges the integers so equations can be solved in richer arithmetic systems—but computation becomes reliable only after the representation of that larger arithmetic has been made explicit.
In the field Q(√2), numbers such as 3+2√2 can be added and multiplied exactly. Their norms and traces return rational information. Ideals restore a useful factorisation theory when elements alone are insufficient. Prime numbers from Z can split, remain prime-like or ramify after entering the larger ring.
This is Guide 16 in the Bukit Timah Tutor Computational Number Theory series. It closes Batch 04 by connecting fast arithmetic and lattice methods to number-field computation. The examples centre on Q(√2), where the integral basis is simple enough for exact hand work. Return to the BTT Mathematics Hub for the wider Mathematics estate.
1. From a polynomial to a number field
Let f(X) be an irreducible polynomial over Q and let α be one of its roots. The field Q(α) consists of rational expressions in α, but every element can be reduced to a polynomial in α of degree less than n=degree(f).
If f(X)=X²−2, write α=√2. Then every field element has a unique form
a+b√2, with a,b in Q.
Multiplication uses the defining relation α²=2. Thus
(a+b√2)(c+d√2) = (ac+2bd)+(ad+bc)√2.
This is quotient-ring arithmetic over Q[X]/(X²−2), just as finite fields used polynomial quotients over finite coefficient fields.
2. Minimal polynomials are arithmetic certificates
An algebraic number β has a unique monic irreducible polynomial over Q that vanishes at β. This is its minimal polynomial.
For β=1+√2, we have β−1=√2 and therefore (β−1)²=2. Rearranging gives
β²−2β−1=0.
The polynomial X²−2X−1 is irreducible over Q, so it is the minimal polynomial.
A numerical approximation to β does not determine this exact relation by itself. If an integer-relation algorithm suggests a polynomial, substitute symbolically or verify at high precision and then prove irreducibility.
3. Algebraic integers
An algebraic number is an algebraic integer if it satisfies a monic polynomial with integer coefficients. The algebraic integers in a number field K form its ring of integers O_K.
Every ordinary integer is an algebraic integer. The number √2 is one because it satisfies X²−2. The number 1/2 is not an algebraic integer.
For K=Q(√2), the ring of integers is Z[√2]. Thus every algebraic integer in this field has the form a+b√2 with a,b in Z.
This equality is special to the chosen field. In Q(√5), the full ring of integers is Z[(1+√5)/2], not Z[√5]. Assuming O_K=Z[α] without checking can corrupt ideal factorisation, discriminants and norm computations.
4. Integral bases
An integral basis is a Z-basis of O_K. If [K:Q]=n, the ring of integers is a free Z-module of rank n.
For Q(√2), {1,√2} is an integral basis. Coordinates of an algebraic integer are therefore ordinary integer pairs.
In computational work, the integral basis is part of the representation contract. Addition is coordinatewise. Multiplication uses precomputed structure constants expressing products of basis elements back in the basis.
A power basis {1,α,…,α^(n−1)} is convenient when it is integral, but not every number field has its ring of integers equal to Z[α] for the initially supplied generator.
5. Multiplication as an integer matrix
Fix the basis {1,√2}. Multiplication by γ=a+b√2 is a Q-linear map from K to itself. Its action on the basis is
γ·1 = a+b√2 γ·√2 = 2b+a√2.
So its matrix is
M_γ = [[a, 2b],
[b, a ]].
The field trace Tr(γ) is the matrix trace, 2a. The field norm N(γ) is the determinant, a²−2b².
These definitions generalise to any finite extension: trace and norm are invariants of the multiplication linear map.
6. Conjugates give the same trace and norm
The two embeddings of Q(√2) into R send √2 to √2 and −√2. The conjugates of γ=a+b√2 are a+b√2 and a−b√2.
Their sum is 2a, agreeing with the trace. Their product is a²−2b², agreeing with the norm.
For γ=3+2√2:
Tr(γ)=6. N(γ)=9−8=1.
Because the norm is one, γ is a unit in Z[√2]. Its inverse is its conjugate 3−2√2, which is again an algebraic integer.
7. Norm is multiplicative
Multiplication maps compose: M_(αβ)=M_α M_β. Determinants therefore multiply:
N(αβ)=N(α)N(β).
This is a structural proof, not an accident of quadratic formulas.
In Q(√2), direct calculation also verifies it:
N(a+b√2)=a²−2b².
Norm can be negative because one real embedding may be negative while the other is positive. Ideal norm, introduced later, is instead a positive integer.
8. Units and Pell equations
An algebraic integer u is a unit exactly when its norm is ±1 in this quadratic setting. Thus solving
a²−2b²=±1
produces units a+b√2.
The fundamental positive unit 3+2√2 has norm one. Its powers generate infinitely many norm-one solutions, matching the Pell-equation structure developed in Guide 7.
This is an important bridge: Pell equations are not isolated Diophantine curiosities. They describe units in real quadratic number fields.
9. Why elements are not enough
In some rings of algebraic integers, unique factorisation into irreducible elements fails. Ideals restore a stronger factorisation theorem.
An ideal I of O_K is an additive subgroup closed under multiplication by arbitrary elements of O_K. Principal ideals have the form (α)=αO_K.
The zero ideal is special. Nonzero ideals in O_K admit unique factorisation into prime ideals. This ideal-level uniqueness is one of the central structural advantages of working in the ring of integers rather than a convenient but nonintegrally closed subring.
10. Ideals as lattices
Under an integral basis, every nonzero ideal I is a full-rank sublattice of O_K≅Z^n. It can therefore be represented by an integer basis matrix.
This is where lattice reduction enters algebraic number theory. Ideal arithmetic creates lattice bases; HNF and LLL-style methods help normalise or reduce them.
For a quadratic field, an ideal may be presented by two generators. Converting those generators into basis coordinates gives a 2×2 integer lattice matrix whose determinant controls the ideal norm.
11. Ideal norm
For a nonzero ideal I in O_K, the absolute ideal norm is
N(I)=|O_K/I|.
It is the finite index of the ideal lattice inside the full ring-of-integers lattice.
For a principal ideal (α),
N((α)) = |N_K/Q(α)|.
For example, N((√2))=2 because N(√2)=−2. The quotient Z[√2]/(√2) has two residue classes, represented by 0 and 1.
12. Prime numbers can change behaviour in a number field
A rational prime p generates the ideal (p) in O_K. That ideal may remain prime, split into several prime ideals, or ramify with repeated prime-ideal factors.
In a monogenic field O_K=Z[α], factoring the minimal polynomial of α modulo p reveals this behaviour cleanly. Q(√2) is such a field with minimal polynomial X²−2.
The examples below show all three possibilities.
13. The prime 3 is inert in Q(√2)
Reduce X²−2 modulo three:
X²−2 ≡ X²+1 (mod3).
At X=0,1,2 the values are 1,2,2, so the polynomial is irreducible over F3. Therefore (3) remains a prime ideal in Z[√2].
Its norm is 3²=9, matching the fact that the residue field O_K/(3) has nine elements and is isomorphic to F9.
This connects directly to Guide 9: the residue field is constructed by adjoining a root of X²+1 to F3.
14. The prime 7 splits
Modulo seven, X²−2 has roots 3 and −3 because 3²=9≡2. Thus
X²−2 ≡ (X−3)(X+3) mod7.
The ideal (7) splits into two distinct prime ideals:
p1=(7, √2−3), p2=(7, √2+3), (7)=p1 p2.
Each prime ideal has norm seven, and their norm product is 49=N((7)).
The two factors correspond to the two ways of reducing √2 to a square root of two modulo seven.
15. The prime 2 ramifies
Modulo two, the defining polynomial becomes X². The repeated factor indicates ramification.
In fact:
(2)=(√2)².
The ideal (√2) has norm two, so squaring it gives norm four, equal to N((2))=2².
Ramification is tied to the discriminant. For Q(√2), the field discriminant is eight, and two is the only rational prime dividing it.
16. Discriminants
For a basis ω1,…,ωn, its discriminant is the determinant of the trace matrix Tr(ω_iω_j). For an integral basis this is the field discriminant.
For {1,√2}, the trace matrix is
[[Tr(1), Tr(√2)], [Tr(√2), Tr(2) ]] = [[2,0],[0,4]].
Its determinant is eight.
The discriminant measures arithmetic degeneracy and controls which primes may ramify. It is also connected to the covolume of the Minkowski embedding.
17. Minkowski embedding turns ideals into Euclidean lattices
A number field with r1 real embeddings and r2 pairs of complex embeddings can be embedded into R^(r1+2r2). Under a suitable scaling of the complex coordinates, O_K and its ideals become full-rank Euclidean lattices.
For Q(√2), both embeddings are real:
σ1(a+b√2)=a+b√2, σ2(a+b√2)=a−b√2.
The image of Z[√2] is a lattice in R². The determinant of this embedded lattice is tied to √|disc(K)|.
This geometric representation enables bounded searches for small elements and underlies computational approaches to units, ideal classes and class groups.
18. Hermite normal form for ideal lattices
An ideal basis matrix is not unique. Hermite normal form provides a canonical triangular-style normal form for integer lattices relative to a chosen coordinate convention.
HNF is useful for testing ideal equality, computing indices and controlling coefficient growth. LLL serves a different purpose: it makes vectors shorter and more orthogonal but does not provide the same canonical normal form.
A computational algebraic-number-theory system often uses both: HNF for exact module structure and LLL for geometry.
19. Ideal arithmetic
If I and J are ideals, their sum I+J is generated by all sums x+y, their product IJ is generated by products xy, and their intersection contains elements lying in both.
In coordinates, these become integer-module operations followed by normalization. Products may initially have many generators; HNF reduces them to a basis of rank n.
Fractional ideals extend the system by allowing denominators. Nonzero fractional ideals form an abelian group under multiplication, and principal fractional ideals form a subgroup.
20. The class group
The ideal class group is the quotient of nonzero fractional ideals by principal fractional ideals. It measures the obstruction to every ideal being principal.
If the class group is trivial, the ring of integers is a principal ideal domain and therefore has unique factorisation of elements. A nontrivial class group records how ideal factorisation remains unique even when element factorisation can fail.
Computing class groups requires much more than forming this quotient symbolically. Algorithms combine discriminant bounds, prime ideals, relation collection, lattice reduction and linear algebra over the integers.
21. Factor bases and relation collection
A common computational pattern chooses a finite set of small prime ideals called a factor base. One searches for principal ideals whose prime-ideal factorisations use only that base.
Each relation gives an integer exponent vector. Collect enough relations and use integer linear algebra, often Smith or Hermite normal forms, to infer information about the class group.
The pattern resembles other algorithms in this series: search for smooth structure, translate multiplicative relations into linear data, then solve the linear problem.
22. Exact arithmetic representation
In Q(√2), an element can be stored exactly as a rational pair (a,b). Algebraic integers use integer pairs. For a general number field, store coefficients in a chosen power or integral basis.
After every multiplication in a power basis, reduce powers of α using its defining polynomial. When changing to an integral basis, apply the exact basis transformation matrix and track denominators explicitly.
Floating approximations to embeddings are useful for size estimates and lattice reduction, but ideal equality and exact norms require exact arithmetic.
23. A minimal quadratic-field arithmetic example
# represents a+b*sqrt(2)
def mul(x, y):
a, b = x
c, d = y
return (a*c + 2*b*d, a*d + b*c)
def conjugate(x):
a, b = x
return (a, -b)
def trace(x):
return 2*x[0]
def norm(x):
a, b = x
return a*a - 2*b*b
u = (3, 2)
v = conjugate(u)
assert mul(u, v) == (1, 0)
assert trace(u) == 6
assert norm(u) == 1This code implements only element arithmetic in Q(√2). It does not implement a general number field, test algebraic integrality in arbitrary fields or perform ideal arithmetic.
The narrow contract makes verification straightforward: compare multiplication with symbolic expansion, and verify norm multiplicativity over bounded integer pairs.
24. Computational workflow for a new number field
Given an irreducible f, first construct K=Q(α). Determine or compute the full ring of integers and an integral basis. Compute the discriminant and embeddings. Build exact element arithmetic in that basis.
Then implement or use tested routines for ideals, HNF, ideal norm and prime decomposition. For deeper arithmetic, compute units, class groups and related invariants.
The order matters. Performing prime-ideal computations in a nonmaximal order while labeling it O_K can give the wrong ramification and factorisation structure.
25. Common mistakes
1. Assuming Z[α] is always the full ring of integers. 2. Confusing element norm with ideal norm. 3. Assuming a rational prime stays prime in O_K. 4. Dropping the chosen basis from a coordinate representation.
5. Treating an approximate embedding as exact algebraic equality. 6. Using LLL as though it were a canonical module normal form. 7. Assuming unique element factorisation merely because ideals factor uniquely. 8. Factoring the defining polynomial modulo p without checking that the chosen generator gives the full integral order in contexts where Dedekind’s simple factorisation rule needs that care.
26. Practice set
1. Multiply (3+2√2)(1−√2). 2. Find the minimal polynomial of 1+√2. 3. Compute the trace and norm of 5+3√2. 4. Find the matrix of multiplication by 5+3√2 on {1,√2}.
5. Verify norm multiplicativity for 3+2√2 and 1+√2. 6. Why is 3+2√2 a unit? 7. Compute the discriminant of {1,√2}. 8. State the ring of integers of Q(√2).
9. Factor X²−2 modulo three and classify the prime 3. 10. Factor it modulo seven and classify 7. 11. Describe the ramification of 2. 12. What is the norm of the ideal (√2)?
13. Why is an ideal naturally an integer lattice? 14. State one role for HNF and one for LLL. 15. What does the class group measure? 16. Why should exact field representation retain an integral basis?
27. Answers and checks
1. The product is −1−√2. 2. X²−2X−1. 3. Trace 10 and norm 25−18=7. 4. [[5,6],[3,5]], whose trace is 10 and determinant 7.
5. N(3+2√2)=1 and N(1+√2)=−1; their product has norm −1. 6. Its norm is one, and its conjugate is an algebraic-integer inverse. 7. The trace-matrix determinant is eight. 8. Z[√2].
9. X²+1 is irreducible over F3, so 3 is inert. 10. It splits as (X−3)(X+3), so 7 splits into two prime ideals. 11. (2)=(√2)². 12. Two.
13. A nonzero ideal is a rank-n Z-submodule of O_K, which itself has an integral Z-basis. 14. HNF gives exact module normalization; LLL gives a geometrically shorter basis. 15. The obstruction to every nonzero ideal being principal. 16. Coordinates, multiplication, norm, ideal index and integrality all depend on the exact ring-of-integers representation.
28. The Batch 04 return path
This batch began with machine-level modular reduction, moved downward to the cost of integer multiplication, then upward through lattices into algebraic number fields. The four topics are connected by computational infrastructure.
Number-field arithmetic needs large integer and polynomial arithmetic. Ideal algorithms use lattice normal forms and reduction. Prime decomposition uses finite fields. Unit calculations meet Pell equations. Fast modular arithmetic supports the primality and factorisation routines used throughout the stack.
The subject is therefore not a linear list of increasingly exotic definitions. It is a network of reusable representations and algorithms, each one becoming infrastructure for another.
Sources and further study
Henri Cohen, A Course in Computational Algebraic Number Theory, is a standard algorithmic reference. Jürgen Neukirch, Algebraic Number Theory, provides broader structural background. SageMath’s number-field documentation is a useful implementation-oriented reference for exact fields, rings of integers, ideals, norms and embeddings.
Computational Number Theory — Batch 04
Guide 13: Montgomery & Barrett Reduction and Fast Modular Multiplication
Guide 14: Fast Integer Multiplication, FFT/NTT and Convolution
Guide 15: Integer Lattices, Gram–Schmidt and LLL Reduction
Guide 16: Algebraic Number Fields, Ideals, Norms and Computational Arithmetic