Codex @codex  0

Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 2 / 18H / a / Solution Created 2026-09-24 Updated 2026-09-25

If the minimal polynomial of

γ

has degree

d

, then

F_{p} (γ)

has

p^{d}

elements and is an intermediate field of

L / F_{p}

. The tower law for field extensions gives

n = [L : F_{p}] = [L : F_{p} (γ)] d,

d ∣ n

The multiplicative group of a finite field is cyclic. Choose a generator

γ

L^{\times}

, of order

p^{n} - 1

. If

γ

lay in a proper intermediate field of degree

d < n

, its order would divide

p^{d} - 1 < p^{n} - 1

, a contradiction. Thus

F_{p} (γ) = L

and its minimal polynomial has degree

n

For arbitrary

r \geq 1

, let

E

be the splitting field of

X^{p^{r}} - X

over

F_{p}

. Its roots form a field: the Frobenius endomorphism shows they are closed under addition, subtraction, multiplication, and inversion. The derivative is

- 1

, so there are exactly

p^{r}

distinct roots. Thus this root field has order

p^{r}

. Applying the preceding generator argument supplies an element whose minimal polynomial over

F_{p}

has degree

r

, proving that an irreducible polynomial of every positive degree exists.

Past exam of the mathematics course of the University of Oxford / 2021 / Prelims / Mathematics I / 6 / b / ii / Solution 2026-10-25

Suppose an arbitrary binary operation

⋆

makes

Z

a group and makes

ρ

a left group action on

G

. For any group action, each acting element induces a bijection: the function induced by its inverse element is its inverse function.

In particular, the acting element whose underlying integer is

0

must induce a bijection

G \to G

. But its power function is

x ⟼ ρ (0, x) = x^{0} = e,

a constant function. This is injective only when all elements of

G

equal

e

. Therefore

G = {e} .

This proves the power-map group action obstruction for every possible

⋆

; it never assumes that

⋆

is ordinary integer multiplication, or that the integer

0

is the acting identity element.

Past exam of the mathematics course of the University of Oxford / 2021 / Prelims / Mathematics I / 6 / b / i / Solution 2026-10-25

Fix

x \in G

. The integer powers of a group element satisfy

x^{z + w} = x^{z} x^{w}, (x^{w})^{z} = x^{w z} = x^{z w} (z, w \in Z) .

For nonnegative integers these rules follow by associativity and counting factors; negative integers are handled by

x^{- r} = (x^{- 1})^{r}

, and opposite signs by cancellation of adjacent inverse elements. All factors are powers of the same element, so no abelian group assumption is involved.

It follows that

z \mapsto ρ (z, x) = x^{z}

is a group homomorphism from the additive group of integers to

G

, and

ρ (z, ρ (w, x)) = ρ (z w, x) .

The homomorphism uses ordinary addition on

Z

; composition of the power functions corresponds to ordinary multiplication of exponents.

Past exam of the options II course of the University of Oxford / 2005 / B / 2 / Solution 2026-10-31

Map the integers into a field by

n \mapsto n 1

. Its kernel is a prime ideal of

Z

, since the image has no zero divisors. Thus the kernel is either zero or

(p)

for a prime

p

. In the zero case, the map extends injectively to the rational numbers by taking quotients of nonzero integers. In the other case, its image is the field

F_{p}

. This proves the prime-field assertion.

A finite field cannot contain the infinite rational field, so it has characteristic

p

. It is a finite-dimensional vector space over its prime field

F_{p}

, say of dimension

n \geq 1

, and choosing a basis counts its elements as

∣ F ∣ = p^{n} .

For existence, put

q = p^{n}

and take a splitting field of

x^{q} - x

over

F_{p}

. Its derivative is

- 1

, so it has exactly

q

distinct polynomial roots. The polynomial roots are closed under addition and multiplication because the Frobenius identity gives

(u + v)^{q} = u^{q} + v^{q}

and

(uv)^{q} = u^{q} v^{q}

. They include

0, 1

, are closed under additive inverses, and for a nonzero polynomial root

u

(u^{- 1})^{q} = (u^{q})^{- 1} = u^{- 1}

. They therefore form a field of exactly

q

elements. Indeed this field is the splitting field because it contains all polynomial roots and is generated by them.

In order 4, characteristic is 2. For

ω \neq = 0, 1

, the multiplicative group has order 3, so

ω^{3} = 1

and

ω^{2} \neq = 1, ω

. Factorization of

x^{3} - 1

gives

ω^{2} + ω + 1 = 0

. The quadratic

x^{2} + x + 1

has no polynomial root in

F_{2}

and is the minimal polynomial. Write

s = ω^{2} = ω + 1

. The complete tables are

+ 01 ω s 001 ω s 110 s ω ω ω s 01 s s ω 10 \cdot 01 ω s 00000 101 ω s ω 0 ω s 1 s 0 s 1 ω .

For an element

ξ \neq = 0, 1

in order 8, the tower law makes

[F_{2} (ξ) : F_{2}]

divide3. It is not1, so its minimal polynomial is an irreducible monic cubic. Its constant term must be1. A cubic

x^{3} + a x^{2} + b x + 1

has no polynomial root at 1 exactly when

a + b = 1

, and absence of a polynomial root is equivalent to cubic irreducibility. Consequently the two possibilities are

x^{3} + x + 1 and x^{3} + x^{2} + 1.

(3)

Both occur: together with

x

and

x + 1

they factor

x^{8} - x

over

F_{2}

, whose distinct polynomial roots are exactly the eight elements of the field. Each cubic contributes its three polynomial roots.

Past exam of the options II course of the University of Oxford / 2005 / D / 4 / iii / Solution 2026-10-31

For fixed real

t

, multiplication by

e^{i t x}

does not change the absolute value. The product integrability proved in (ii) therefore justifies Fubini theorem in the following calculation. Set

u = x - y

in the inner integral:

g * h (t) = \int_{R} \int_{R} g (x - y) h (y) e^{i t x} d y d x = \int_{R} h (y) [\int_{R} g (x - y) e^{i t x} d x] d y = \int_{R} h (y) e^{i t y} [\int_{R} g (u) e^{i t u} d u] d y = g (t) h (t) .

Thus

g * h = g h .

The positive exponential convention in the source is used throughout; no normalization factor is introduced under that convention.

Past exam of the rings and modules course of the University of Oxford / 2021 / 1 / b / ii / Solution 2026-10-25

Set

I = (X^{3})_{T}

and

J = (Y^{3})_{R [Y]}

. Part (b)(i) gives a unique representative

a + b X^{2} + c X^{4}

for each element of the quotient ring

T / I

. By polynomial division, each element of the quotient ring

R [Y] / J

likewise has a unique representative

a + bY + c Y^{2}

. Thus the proposed map

Φ

is well-defined and a bijection.

It preserves addition and

1

. To verify multiplication, all terms of polynomial degree at least

5

lie in

I

. Hence

(a + b X^{2} + c X^{4}) (a^{'} + b^{'} X^{2} + c^{'} X^{4}) + I = a a^{'} + (a b^{'} + b a^{'}) X^{2} + (a c^{'} + b b^{'} + c a^{'}) X^{4} + I .

In the other quotient ring,

Y^{3} = 0

, giving exactly the same coefficient formula:

(a + bY + c Y^{2}) (a^{'} + b^{'} Y + c^{'} Y^{2}) + J = a a^{'} + (a b^{'} + b a^{'}) Y + (a c^{'} + b b^{'} + c a^{'}) Y^{2} + J .

Therefore

Φ : T / (X^{3})_{T} ≅ R [Y] / (Y^{3}), a + b X^{2} + c X^{4} + I ⟼ a + bY + c Y^{2} + J

(3)

is a ring isomorphism. Both sides are examples of a truncated polynomial ring; the generator on the left is the class of

X^{2}

, whose square is nonzero and whose cube vanishes.

Past exam of the rings and modules course of the University of Oxford / 2021 / 3 / c / ii / Solution 2026-10-25

Write

q = ∣ F ∣

. The unit group

U (F) = F ∖ {0}

is a finite abelian group of group order

q - 1

, since multiplication in a field satisfies commutativity. The structure theorem for finitely generated abelian groups, applied to this finite group, gives invariant factors of a finitely generated module

U (F) ≅ Z_{d_{1}} \oplus \dots \oplus Z_{d_{r}}, 1 < d_{1} ∣ d_{2} ∣ \dots ∣ d_{r},

after omitting trivial factors. If there are no factors, the unit group is trivial and hence a cyclic group.

Otherwise put

D = d_{r}

. Every element

u \in U (F)

satisfies

u^{D} = 1

, because the order of a group element in each coordinate divides

D

. Hence all

q - 1

distinct nonzero elements of

F

are roots of a polynomial

X^{D} - 1

. The root bound for a polynomial over a field gives

q - 1 \leq D .

For completeness, that bound follows by induction from the factor theorem: if a nonzero polynomial

f

vanishes at

a

, write

f = (X - a) g

; every other root of a polynomial is a root of

g

, because a field has no zero divisors. Each new distinct root therefore uses one unit of polynomial degree.

On the other hand, the group order in the decomposition is

q - 1 = d_{1} \dots d_{r} \geq d_{r} = D .

(3)

Equality is forced, so

d_{1} \dots d_{r - 1} = 1

. As every retained factor is greater than

1

, there can be only one. Consequently

U (F) ≅ Z_{q - 1} is cyclic .

(4)

The same proof establishes the more general result finite multiplicative subgroup of a field is cyclic. The square-free integer result in part (c)(i) alone would not suffice, since

q - 1

need not be a square-free integer; the root bound for a polynomial rules out multiple invariant factors of a finitely generated module even then.

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Functional programming, design and analysis of algorithms / 1 / b / Solution 2026-10-31

Recurse on the first argument for addition and multiplication, and on the exponent for exponentiation:

add :: Natural -> Natural -> Natural
add Zero     n = n
add (Succ m) n = Succ (add m n)

mul :: Natural -> Natural -> Natural
mul Zero     n = Zero
mul (Succ m) n = add n (mul m n)

power :: Natural -> Natural -> Natural
power m Zero     = Succ Zero
power m (Succ n) = mul m (power m n)

The defining arithmetic identities are

0 + n = n, (m + 1) + n = 1 + (m + n), 0 n = 0, (m + 1) n = n + mn, m^{0} = 1, m^{n + 1} = m m^{n} .

Each recursive call consumes one constructor. The base of exponentiation makes power Zero Zero equal to one, the empty-product convention. Applying convert and using structural induction verifies all three operations.

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Functional programming, design and analysis of algorithms / 1 / d / Solution 2026-10-31

A natural-number fold iterates its first argument once per successor. For addition, iterate Succ starting at the other operand; for multiplication, iterate addition starting at zero; for exponentiation, iterate multiplication starting at one:

addF :: Natural -> Natural -> Natural
addF m n = foldNat Succ n m

mulF :: Natural -> Natural -> Natural
mulF m n = foldNat (addF n) Zero m

powerF :: Natural -> Natural -> Natural
powerF m n = foldNat (mulF m) (Succ Zero) n

The common identity is

foldNat f e n = f^{n} (e)

, with

n

interpreted through convert. Substituting each step and seed reproduces the recursive arithmetic equations of part (b).

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Functional programming, design and analysis of algorithms / 5 / b / Solution 2026-10-31

The scan permits an arbitrary signed integer but prints

lo g_{2} m

. That expression is undefined for

m \leq 0

. The printed bound is proved below for positive

m

; for the stated signed domain the corresponding bound uses

lo g_{2} max (2, ∣ m ∣)

. This is a source qualification, rather than an unreadable part of the question.^[ref]

Choose a fixed positive integer

k

with

1/ k \leq ϵ

, and put

B = 2^{k}

. For positive

m

, use coarse exponential bracketing: compare against

B, B^{2}, B^{3}, \dots

until the first

B^{j} \geq m

. Equality determines

m

immediately. Otherwise,

B^{j - 1} < m < B^{j}

, except in the first interval where the lower bound is zero. Apply binary search to the remaining integer candidates.

There are at most

j

bracketing comparisons and at most

kj + O (1)

subsequent comparisons, because the interval width is at most

B^{j} = 2^{kj}

. Minimality of

j

gives

j \leq (lo g_{2} m) / k + 1

. Hence

C (m) \leq j + kj + O (1) \leq (1 + \frac{1}{k}) lo g_{2} m + k + O (1) \leq (1 + ϵ) lo g_{2} m + O_{ϵ} (1) .

The additive constant may depend on the fixed

ϵ

, but is independent of

m

. Taking larger jumps in the bracketing phase reduces its leading comparison cost; the overshoot costs only the fixed number

k

of extra binary search levels.

For signed inputs, first compare with zero. If negative, set

u = ∣ m ∣

conceptually and perform the same search for

u

: comparing

m

with

- t

yields the reversed outcome of comparing

u

with

t

. Thus every test is still a permitted test of the sign of

m - x

. Return zero immediately on equality in the initial test. The corrected all-input bound is

C (m) \leq (1 + ϵ) lo g_{2} max (2, ∣ m ∣) + O_{ϵ} (1) .

All thresholds are exact integers, generated by repeated multiplication by

B

. Their arithmetic and storage costs are outside the requested comparison model; bounded machine arithmetic would not suffice for arbitrarily large

∣ m ∣

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming / 1 / a / Solution 2026-10-25

Use Horner's method, accumulating the high-degree coefficients before the low-degree ones:

def eval(x: Double): Double = {
  var i = a.length
  var value = 0.0
  while (i > 0) {
    i -= 1
    value = a(i) + x * value
  }
  value
}

At each while loop head the loop invariant is

0 \leq i \leq n, value = \sum_{j = i}^{n - 1} a (j) x^{j - i} .

The initial sum is empty. Decreasing i and replacing the accumulator by a(i) + x * value extends that sum by one coefficient with the required powers shifted. The loop variant is i; on exit it is zero, so the accumulator equals

p (x)

. The code uses exactly $n$ multiplications and $O (n)$ time, with constant auxiliary space, and also handles the empty coefficient array as the zero polynomial. Initializing from the last coefficient instead would save one multiplication for nonempty arrays.

The invariant is an exact-arithmetic specification. With Double, each arithmetic operation rounds; consequently the code evaluates the Horner expression in floating-point arithmetic, rather than guaranteeing the exact real value for arbitrary coefficients.

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming / 7 / c / Solution 2026-10-25

Instantiate the two type parameters and implement the function object interface:

val square: Fun[Int, Int] = new Fun[Int, Int] {
  override def apply(x: Int): Int = x * x
}

Parametric polymorphism occurs because the generic trait is specialized by choosing its argument and result types. Subtype polymorphism occurs because the anonymous implementing software class is used through a Fun[Int, Int] reference; calls to its apply operation use the object interface contract and dynamic dispatch. Multiplication itself is not the second polymorphism needed for this explanation.

For values whose mathematical squares fit in a signed 32-bit integer, the result is the ordinary square. Outside that range, the supplied integer return type cannot represent every mathematical square, and the multiplication follows Scala integer-overflow behavior. An implementation requiring exact mathematical results for all integer inputs would need a wider result type or an explicit overflow exception.

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof / 5 / d / ii / Solution 2026-10-25

Evaluate the recurrence relation successively, retaining only the preceding two values. Each of the

n - 1

updates uses three multiplications and one subtraction. Hence $4 (n - 1) = O (n)$ arithmetic operations and $O (1)$ auxiliary storage suffice, excluding the stored input. Naively branching into two recursive calls would repeat work; the sequential computation is essential. This is an arithmetic-operation bound, not a bit-complexity bound for arbitrarily large exact integers.

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Discrete mathematics, continuous mathematics and probability resit / 3 / a / Solution 2026-10-25

The integer congruence

x \equiv y (mod n)

means

n ∣ (x - y)

: the difference is an integer multiple of the positive modulus

n

. Write

x_{1} - x_{2} = na

and

y_{1} - y_{2} = nb

for integers

a, b

. Then

(x_{1} + y_{1}) - (x_{2} + y_{2}) = n (a + b),

so addition preserves integer congruence. For multiplication,

x_{1} y_{1} - x_{2} y_{2} = y_{1} (x_{1} - x_{2}) + x_{2} (y_{1} - y_{2}) = n (a y_{1} + b x_{2}) .

The final coefficient is an integer, so multiplication also preserves integer congruence. These properties make addition and multiplication well defined on residue classes.

Polar form of a complex number Created 2026-10-06 Updated 2026-10-20

A nonzero complex number has polar form

z = r (cos θ + i sin θ) = r e^{i θ}, r = ∣ z ∣ > 0,

where

r

is its modulus and

θ

is an argument. The equality uses Euler's formula; sine and cosine recover the imaginary part and real part from polar coordinates. For

z = 3 + 4 i

, take

r = 5

and

θ = arctan (4/3) \approx 0.927295

radians, so

cos θ = 3/5

and

sin θ = 4/5

w = s e^{i ϕ} \neq = 0

, then

z w = rs e^{i (θ + ϕ)}, \frac{z}{w} = \frac{r}{s} e^{i (θ - ϕ)} .

Thus multiplication multiplies moduli and adds arguments modulo

2 π

; division divides moduli and subtracts arguments modulo

2 π

. Since

1 + i = 2 e^{iπ /4}

, multiplying

3 + 4 i

1 + i

gives

- 1 + 7 i

, of modulus

52

and argument

θ + π /4 \approx 1.712693

radians. One formula simultaneously describes its new size and direction.

Figure 1.
Complex multiplication rotates every direction and scales every length equally
. **Details**.

Repeated multiplication now becomes especially simple:

(r e^{i θ})^{n} = r^{n} e^{in θ}

for a positive integer

n

. This explains the evenly spaced arguments of the roots of a complex number. For example,

(3 + 4 i)^{2} = - 7 + 24 i

has modulus

25

and principal argument

2 θ \approx 1.854590

radians. The Cartesian calculation and the polar form provide independent checks on both its location and its size. Choose polar form when the task concerns multiplication, division, or repeated turns; use real parts and imaginary parts for addition.

Polynomial Created 2026-09-24 Updated 2026-10-18

A polynomial is a finite sum of monomials with coefficients in a ring. In one variable

X

over a commutative ring

R

, write

p (X) = a_{0} + a_{1} X + \dots + a_{n} X^{n}, a_{j} \in R .

The symbol

X

is an indeterminate: it records powers formally before we choose an input value. Finite expressions are easy to add, multiply, evaluate, and differentiate, making polynomials a common language for exact algebra and approximate numerical analysis.

Consider the real polynomial

p (X) = X^{3} - 3 X^{2} + 4 = (X + 1) (X - 2)^{2} .

The expanded form displays the coefficients and the degree of a polynomial; the factored form displays its roots of a polynomial. At

X = 3

, either description gives

p (3) = 4

. At

X = - 1

and

X = 2

, the factored form makes the zero values immediate. Keeping several descriptions of one object is useful because each makes a different question easy.

Figure 1.
A simple polynomial root crosses the axis, while a double root touches it; perturbing the double factor can produce real or complex roots
. **Details**.

The graph shows another connection. The factor

X + 1

changes sign across

- 1

, while

(X - 2)^{2}

stays nonnegative across

2

. Thus the graph crosses the axis at the simple root of a polynomial and touches it at the double root. Multiplicity of a root turns an algebraic repetition into visible local behavior.

For calculations, Horner's method evaluates a polynomial through nested multiplication. For modeling, a Taylor polynomial describes local behavior near a point, while polynomial interpolation constructs a polynomial matching prescribed data. Their usefulness comes with assumptions: a local approximation and an exact identity are different claims, and changing the coefficient ring can change which polynomial roots exist.

Polynomial identity testing Created 2026-09-24 Updated 2026-10-18

Polynomial identity testing asks whether a polynomial represented implicitly, such as by an arithmetic circuit or a remainder computation, is the zero polynomial.

Here zero means that every coefficient vanishes after collecting equal monomials in the polynomial ring. Testing equality of two polynomials

A, B

amounts to testing

P = A - B

for zero. An arithmetic circuit can permit cheap polynomial evaluation even when expanding all monomials is expensive. The random evaluation test for a polynomial identity exploits this: one nonzero value disproves the polynomial identity, while a known total degree limits how often a nonzero polynomial can evade detection.^[ref]

For example, for an integer

n \geq 1

\prod_{i = 1}^{n} (1 + x_{i})

has

2^{n}

distinct monomials, one for each subset of the

n

variables. Its factored expression needs only

n

additions and

n - 1

multiplications for one polynomial evaluation. Evaluating the compact expression avoids creating its expanded list of coefficients. The saving is especially attractive in many variables; it does not make a zero result into a proof of identity.

Prime field Created 2026-10-03 Updated 2026-10-14

The prime field of a field

K

is its smallest subfield: the arithmetic forced upon us by the identity element

1_{K}

. Every subfield must contain

1_{K}

, its repeated sums, their additive inverses, and the multiplicative inverses of nonzero results. In characteristic zero these operations produce a copy of the rational numbers

Q

. In positive characteristic of a field

p

, they produce a copy of

F_{p} = Z / p Z

, with addition and multiplication given by modular arithmetic.

For example, inside the field with four elements, repeated addition of

1

gives

0, 1, 0, 1, \dots

. Thus its prime field is

{0, 1}

, and the other two elements cannot be reached by repeatedly adding

1

. This is why a finite field need not consist entirely of ordinary integer residues: a larger finite field extends the arithmetic of its prime field with additional elements.

The positive characteristic of a field must be a prime number. If its least vanishing multiple of

1_{K}

were

rs

with

1 < r, s < rs

, then

(r 1_{K}) (s 1_{K}) = 0

would exhibit zero divisors. The absence of zero divisors rules this out. The prime field supplies the scalars when viewing

K

as a vector space; its basis then explains the possible sizes of a finite field.

Prime number Created 2026-09-24 Updated 2026-10-13

A prime number is a positive integer

p > 1

whose only positive divisors are

1

and

p

. The first ten prime numbers are

2, 3, 5, 7, 11, 13, 17, 19, 23, 29

. In contrast,

12 = 3 \cdot 4

is a composite number because it has a positive divisor strictly between one and itself. The integer one is neither a prime number nor a composite number: the lower bound

p > 1

is part of the definition. Equivalently, the divisor function satisfies

τ (p) = 2

for a prime number, whereas

τ (1) = 1

and

τ (n) \geq 3

for every composite number

n

Prime numbers are the building blocks of positive integers under multiplication. The fundamental theorem of arithmetic says that every integer greater than one is a product of prime numbers, with a unique collection of factors when their order is ignored. For example,

12 = 2 \cdot 2 \cdot 3

and

18 = 2 \cdot 3 \cdot 3

. Their common factors reveal the greatest common divisor

6

, and the combined maximum powers reveal the least common multiple

36

. A complicated divisibility question becomes a comparison of prime exponents.

There is also a useful finite test. If a composite number

n

equals

ab

with

1 < a \leq b

, then

a^{2} \leq n

. Therefore some prime factor is at most

n

, and trial division only needs to check prime numbers up to that square root. For

97

, checking

2, 3, 5, 7

suffices; none divides

97

, so it is a prime number. For

91

, the same test finds

7

, giving

91 = 7 \cdot 13

. To find many prime numbers together, the sieve of Eratosthenes reuses the work by marking multiples.

The division with remainder calculations for

97

make the test explicit:

97 = 2 \cdot 48 + 1 = 3 \cdot 32 + 1 = 5 \cdot 19 + 2 = 7 \cdot 13 + 6.

Since

9^{2} < 97 < 1 0^{2}

, these are all the prime numbers at most its square root, and every remainder is nonzero. Thus the calculation certifies a prime number, without testing the integers

8, 9, 10, \dots, 96

individually. In contrast,

91 = 7 \cdot 13 + 0

gives a prime factor and proves that

91

is a composite number.