Algebraic Number Theory

Intuition, Vocabulary and Foundations

Ordinary integers occupy a one-dimensional number line. Algebraic number theory enlarges that world by adjoining roots of polynomial equations. Gaussian integers form the square lattice $\mathbb Z[i]=\{a+bi:a,b\in\mathbb Z\}$, where $i^2=-1$, while Eisenstein integers form the triangular lattice $\mathbb Z[\omega]=\{a+b\omega:a,b\in\mathbb Z\}$, where $\omega^2+\omega+1=0$.

This resembles expanding a toolkit: an equation or factorization unavailable over the integers may become visible in a larger ring. For example, $5=(2+i)(2-i)$ in $\mathbb Z[i]$. The Gaussian norm $N(a+bi)=a^2+b^2$ turns multiplication into integer multiplication, so $N(2+i)=5$. In $\mathbb Z[\omega]$, the corresponding norm is $N(a+b\omega)=a^2-ab+b^2$.

A complex number is an algebraic integer if it satisfies a monic polynomial with integer coefficients. The ring of integers of a number field contains all such elements and need not equal the first basis one guesses: the ring of integers of $\mathbb Q(\sqrt5)$ is $\mathbb Z[(1+\sqrt5)/2]$. Elements of norm $1$ are units. Ideals generalize ordinary multiples and retain unique prime factorization even when elements do not. Ramification means a prime ideal occurs repeatedly, while the class group measures the obstruction to every ideal being principal.

Elements may lose unique factorization, but nonzero ideals in the ring of integers of a number field still factor uniquely into prime ideals. Before transferring an integer factorization argument to a larger ring, establish its units, norm, integral basis, and factorization properties.

Concept	Definition or notation	Example	Non-example or boundary	Question answered
Gaussian integer	$a+bi$ with $a,b\in\mathbb Z$	$3-2i$	$(1/2)+i$ is not in $\mathbb Z[i]$	What arithmetic lives on the square lattice?
Eisenstein integer	$a+b\omega$ with $\omega^2+\omega+1=0$	$2-\omega$	Treating $\omega$ as a real number	What arithmetic lives on the triangular lattice?
Algebraic integer	Root of a monic polynomial in $\mathbb Z[x]$	$(1+\sqrt5)/2$ satisfies $x^2-x-1=0$	$1/2$ is not an algebraic integer	Which field elements behave integrally?
Norm	Product of all conjugates	$N(3+4i)=25$	Complex magnitude alone is not the general definition	How can divisibility be related to integer size?
Unit	Element invertible inside the ring	$\pm1,\pm i$ in $\mathbb Z[i]$	$2$ is not a Gaussian unit	Which factors are insignificant up to associates?
Ideal	Additive subgroup closed under ring multiplication	$(2+i)$ in $\mathbb Z[i]$	An arbitrary finite subset	How is divisibility represented structurally?
Ramification	A prime ideal occurs with exponent greater than one	$(2)=(1+i)^2$ up to a unit	Every splitting prime is ramified	Which primes develop repeated factors?
Class group	Fractional ideals modulo principal ideals	Trivial for $\mathbb Z[i]$	It is not generally a group of elements	How far is the ring from principal ideal factorization?
Unique factorization	Irreducibles are unique up to units and order	Holds in $\mathbb Z[i]$	Fails for elements in $\mathbb Z[\sqrt{-5}]$	May element-factor arguments be reused?

Step-by-Step Derivations and Algorithms

The Euclidean algorithm extends to any Euclidean domain. For nonzero $\beta\in\mathbb Z[i]$, divide $\alpha$ by $\beta$ in $\mathbb C$, round both coordinates to the nearest integers to obtain $q\in\mathbb Z[i]$, and set $r=\alpha-q\beta$. Square-lattice geometry guarantees $N(r)\lt N(\beta)$, so repeated division terminates. The invariant $(\alpha,\beta)=(\beta,r)$ says the pairs generate the same ideal and have the same common divisors; back-substitution produces a Gaussian Bézout identity.

Norms constrain factorization because $N(\alpha\beta)=N(\alpha)N(\beta)$. An element whose norm is an ordinary prime is irreducible, though the converse requires care. In $\mathbb Z[i]$, $2$ ramifies, a rational prime $p\equiv1\pmod4$ splits, and a rational prime $p\equiv3\pmod4$ remains inert. Eisenstein integers yield an analogous classification governed by residues modulo $3$.

Cubic reciprocity is naturally formulated in $\mathbb Z[\omega]$, and biquadratic reciprocity in $\mathbb Z[i]$. They replace the sign-valued quadratic symbol with higher-power residue symbols. Their algorithms reduce residue questions using conjugation, norms, and reciprocity, but only after elements are normalized as primary and all coprimality hypotheses are verified.

Algebraic Number Theory algorithm map

flowchart TD
    A["Choose a number field"] --> B["Determine its ring of integers"]
    B --> C{"Euclidean norm available?"}
    C -->|Yes| D["Run norm-decreasing gcd"]
    C -->|No| E{"Principal ideal domain?"}
    E -->|Yes| F["Use element or ideal gcd methods"]
    E -->|No| G["Factor ideals and track classes"]
    D --> H["Normalize by a unit"]
    F --> H
    G --> I["Interpret class-group obstruction"]
    H --> J{"Power-residue question?"}
    J -->|Square| K["Quadratic reciprocity"]
    J -->|Cube or fourth power| L["Cubic or biquadratic reciprocity"]

The Euclidean-gcd invariant is $(a,b)=(b,a-qb)$, and a strictly decreasing nonnegative norm proves termination. For Gaussian inputs of at most $B$ bits, the classical analysis uses $O(B)$ divisions; actual bit cost depends on exact multiplication and division, and outside a Euclidean domain the argument must be replaced by ideal arithmetic.

Implementation, Complexity and Engineering

The reference implementation performs exact Gaussian-integer arithmetic. Division uses rational numerators and exact nearest-integer rounding rather than floating point. The gcd is normalized to one of its four associates so callers receive a stable representative.

This code deliberately covers only $\mathbb Z[i]$, a Euclidean domain. It does not imply that the same element-gcd or factorization code works in arbitrary quadratic rings. General number-field software must represent an integral basis, ideals, embeddings, discriminants, and coefficient growth, normally through a specialized computer-algebra library.

from dataclasses import dataclass


@dataclass(frozen=True)
class Gaussian:
    real: int
    imag: int = 0

    def __add__(self, other):
        return Gaussian(self.real + other.real, self.imag + other.imag)

    def __sub__(self, other):
        return Gaussian(self.real - other.real, self.imag - other.imag)

    def __mul__(self, other):
        return Gaussian(
            self.real * other.real - self.imag * other.imag,
            self.real * other.imag + self.imag * other.real,
        )

    def conjugate(self):
        return Gaussian(self.real, -self.imag)

    def norm(self):
        return self.real * self.real + self.imag * self.imag

    def is_zero(self):
        return self.real == 0 and self.imag == 0


ZERO = Gaussian(0, 0)
ONE = Gaussian(1, 0)
UNITS = (
    Gaussian(1, 0),
    Gaussian(-1, 0),
    Gaussian(0, 1),
    Gaussian(0, -1),
)


def nearest_integer(numerator, denominator):
    """Round an exact fraction to a nearest integer; ties go downward."""
    if denominator <= 0:
        raise ValueError("denominator must be positive")
    quotient, remainder = divmod(numerator, denominator)
    if 2 * remainder > denominator:
        quotient += 1
    return quotient


def gaussian_divmod(dividend, divisor):
    if divisor.is_zero():
        raise ZeroDivisionError("Gaussian division by zero")
    denominator = divisor.norm()
    real_numerator = dividend.real * divisor.real + dividend.imag * divisor.imag
    imag_numerator = dividend.imag * divisor.real - dividend.real * divisor.imag
    quotient = Gaussian(
        nearest_integer(real_numerator, denominator),
        nearest_integer(imag_numerator, denominator),
    )
    remainder = dividend - quotient * divisor
    assert remainder.norm() < divisor.norm()
    return quotient, remainder


def divides(divisor, value):
    if divisor.is_zero():
        return value.is_zero()
    _, remainder = gaussian_divmod(value, divisor)
    return remainder.is_zero()


def normalize_associate(value):
    if value.is_zero():
        return value
    associates = [value * unit for unit in UNITS]
    allowed = [
        z for z in associates
        if (z.real > 0 and z.imag >= 0)
        or (z.real == 0 and z.imag > 0)
    ]
    return max(allowed, key=lambda z: (z.real, -z.imag))


def gaussian_gcd(left, right):
    while not right.is_zero():
        _, remainder = gaussian_divmod(left, right)
        left, right = right, remainder
    return normalize_associate(left)


def gaussian_extended_gcd(left, right):
    """Return normalized g, x, y with left*x + right*y == g."""
    old_r, r = left, right
    old_x, x = ONE, ZERO
    old_y, y = ZERO, ONE
    while not r.is_zero():
        quotient, remainder = gaussian_divmod(old_r, r)
        old_r, r = r, remainder
        old_x, x = x, old_x - quotient * x
        old_y, y = y, old_y - quotient * y
    if old_r.is_zero():
        return ZERO, ZERO, ZERO
    normalized = normalize_associate(old_r)
    unit = next(unit for unit in UNITS if old_r * unit == normalized)
    return normalized, old_x * unit, old_y * unit


a = Gaussian(11, 3)
b = Gaussian(1, 8)
g = gaussian_gcd(a, b)
assert g == Gaussian(2, 1)
assert divides(g, a) and divides(g, b)

g2, x, y = gaussian_extended_gcd(a, b)
assert g2 == g
assert a * x + b * y == g

q, r = gaussian_divmod(Gaussian(7, 5), Gaussian(2, 1))
assert Gaussian(7, 5) == q * Gaussian(2, 1) + r
assert r.norm() < Gaussian(2, 1).norm()

assert Gaussian(3, 4).norm() == 25
assert gaussian_gcd(Gaussian(5), ZERO) == Gaussian(5)
assert gaussian_gcd(ZERO, ZERO) == ZERO

try:
    gaussian_divmod(ONE, ZERO)
    raise AssertionError("division by zero was accepted")
except ZeroDivisionError:
    pass

print("all tests passed")

Choice	Mathematical domain	Cost or representation	Failure mode	Mitigation
Pair representation	$\mathbb Z[i]$ as $(a,b)$	Exact integer coefficients	Accidentally using complex floating point	Implement arithmetic, conjugation, and norm explicitly
Nearest-lattice division	Gaussian Euclidean division	Exact rounding of two rational coordinates	Rounding error breaks norm descent	Round integer numerators without floating point
Associate normalization	Units $\{\pm1,\pm i\}$	Constant work	Equivalent gcds compare unequal	Select one documented canonical associate
Norm-based gcd	Euclidean quadratic rings	Logarithmic number of steps in norm size	Assuming every quadratic ring is Euclidean	Prove norm descent for the selected ring
Element factorization	UFDs such as $\mathbb Z[i]$	Depends on norms and integer factorization	Reusing it in a non-UFD	Factor ideals or use class-group information
Power basis	Coefficients in $1,\theta,\ldots$	Convenient but not always integral	Missing algebraic integers	Compute or obtain an integral basis
Ideal arithmetic	Dedekind domains	Integer lattices with coefficient growth	Naive matrices become large	Use normal forms and established libraries
Reciprocity symbols	Primary elements under exact hypotheses	Fast residue classification	Ignoring normalization or coprimality	Check every theorem hypothesis

Applications, Case Studies and Exercises

Small lattice rings make the abstract ideas visible. Gaussian arithmetic connects sums of two squares with prime splitting, while Eisenstein arithmetic explains the structure behind cubic residues. A contrasting quadratic field shows why ideals and class groups are necessary: element factorization may fail even though ideal factorization remains unique.

Practice

Apply Algebraic Number Theory

Case study 1 — factor in the Gaussian integers. Begin with $5=(2+i)(2-i)$. Verify both factors have norm $5$, confirm that their product is $5$, and list all associates obtained by multiplying by $\pm1$ and $\pm i$. Then run the reference gcd on $11+3i$ and $1+8i$. Checkpoint: the normalized gcd is $2+i$. Success means it divides both inputs and an exact Bézout identity is recovered.

Case study 2 — detect failed element uniqueness. In $\mathbb Z[\sqrt{-5}]$, compare $6=2\cdot3=(1+\sqrt{-5})(1-\sqrt{-5})$. Compute $N(a+b\sqrt{-5})=a^2+5b^2$ and investigate why the displayed factors are not related merely by units and reordering. Checkpoint: identify the obstruction to treating this ring like $\mathbb Z[i]$, then state how prime-ideal factorization restores uniqueness. Success means no Euclidean or UFD assumption is used without proof.

Hands-on extension — Eisenstein arithmetic. Represent $a+b\omega$ by integer pairs, derive multiplication from $\omega^2=-\omega-1$, and implement $N(a+b\omega)=a^2-ab+b^2$. Verify multiplicativity for every pair with coefficients from $-4$ through $4$, then enumerate the six elements of norm $1$. Success means every norm test passes and exactly six units are found.

Tiered exercises. Recall: define an algebraic integer, unit, ideal, and ramified prime. Derive: prove the Gaussian norm is multiplicative. Implement: print the gcd quotients and decreasing norms. Debug: replace exact rounding with floating point and find a large case where verification becomes unreliable. Extend: compare rings of integers of $\mathbb Q(\sqrt d)$ for squarefree $d$ in the two congruence cases modulo $4$.

Use element arithmetic when the ring is explicitly known to be Euclidean or a UFD; use ideals when unique factorization of elements is absent, and use specialized algebra systems when integral bases or class groups are required. Norms alone do not prove every primality claim, not every quadratic ring is $\mathbb Z[\sqrt d]$, and integer factorization rules do not survive unchanged.

Cookie Consent