Past exam of the rings and modules course of the University of Oxford 2023 3 b i Solution Created 2026-10-25 Updated 2026-11-05
The Gaussian integers form an integral domain, since they are a subring of the complex numbers. Use the Gaussian integer normwhich is a positive integer for nonzero and satisfies .
For with , write . Choose integers with and , put , and set . ThenThus division with remainder has either or a strictly smaller Gaussian integer norm. This proves that is a Euclidean function and
Past exam of the rings and modules course of the University of Oxford 2023 3 b iv Solution 2026-10-25
Each entry of the matrix from part (b)(iii) has unique real and imaginary integer coefficients. WriteIt already belongs to the general linear group . Expanding the relation from part (b)(iii) givesThe real and imaginary parts must both vanish, soThese are the required identities, with .
Euler's criterion states, for an odd prime ,Apply it to . The integer is when and when . Since those signs are distinct modulo an odd prime, the modular congruence determines the actual Legendre symbol:This is the first supplementary law for quadratic reciprocity.
For an odd prime , the Legendre symbol isIt depends only on the congruence class of the integer . The values and distinguish a nonzero quadratic residue from a quadratic nonresidue; zero is a separate case.
Choose any pair from part (i), and put . The divisibilities of the exponents makepositive integers. Their powers areThus , with all three powers nonzero and distinct. For example, take , for every nonnegative integer . Then strictly increases, giving infinitely many distinct solutions. The construction uses modular congruences to turn the elementary identity into three prescribed perfect powers.
Writing , the second condition becomes . Writing , its second condition becomes . Consequentlygives an infinite set of positive integer solutions. Conversely these are the positive solutions in the indicated congruence classes, by the Chinese remainder theorem.
For an odd prime number , Euler's criterion states thatwhere the Legendre symbol is zero if , one if is a nonzero quadratic residue, and minus one otherwise. Including the zero case makes this formulation valid for every integer .
Apply Euler's criterion to , , and . Multiplication in modular arithmetic givesIf divides either factor, both sides are zero. Otherwise both sides belong to ; these two values are distinct modulo the odd prime number . The congruence is therefore an equality of integers, proving multiplicativity of the Legendre symbol:
The binomial theorem isolates the only terms that can survive reduction modulo the prime number :For , neither nor is divisible by , whereas is. Consequently , and every intermediate term vanishes in modular arithmetic. ThusThis works for arbitrary integers , including those divisible by . It is the additive identity behind the Frobenius endomorphism in characteristic .
Euler's totient function counts the integers in a complete complete residue system that are coprime to the modulus:If the prime factorization is with distinct prime numbers , Euler's totient product formula isIn particular, . Adjoining the prime factor changes neither the odd factor nor its count of units, since . The product formula givesThis is a positive integer distinct from , as required.
The Chinese remainder theorem says that for pairwise coprime positive moduli and arbitrary integers , the simultaneous modular congruenceshave a solution, unique modulo .
Choose distinct prime numbers . Their prime powers are pairwise coprime. Apply the Chinese remainder theorem toFor the resulting integer , each is divisible by , the required power of an integer greater than one. Adding a sufficiently large multiple of makes positive without changing any modular congruence. Thus such a positive exists, indeed infinitely many do. This is the general construction of consecutive integers divisible by prescribed prime powers.
Past exam of the theoretical physics II course of the University of Cambridge 2019 2 c Solution 2026-10-18
The radial S wave vanishes at the hard surface, so outside the sphere . Comparison with givesThe hard-sphere S-wave scattering amplitude and cross section are thereforeThe three prominent features are the finite low-energy limit , the oscillations with exact zeros at for positive integers , and the decreasing envelope . The zero-energy value is four times the geometric area . Near zero the normalized cross section is . The large- fall here concerns the S wave alone; summing all partial waves gives a different high-energy total.
Past exam of the topics in applied mathematics course of the University of Oxford 2008 B 6 Solution 2026-10-31
For integers ,Thus reducing coordinates modulo one gives a well-defined function on the torus . Its determinant is one and its inverse matrix is the integer matrix , so it induces a bijection of the torus. The Jacobian determinant one makes this bijection area-preserving.
Its eigenvalues solve , givingThere are therefore expanding and contracting eigendirections and no eigenvalue on the unit circle: the function is a hyperbolic toral automorphism. The Lyapunov exponents per iterate areThey sum to zero, as required by area preservation.
The four vertices of the unit square map to , the vertices of an area-one parallelogram. To reduce it modulo one, cut it by the integer grid. For each piece in the cell , translate by . Up to boundary identifications these translated pieces partition the unit square, because the inverse integer matrix gives exactly one torus preimage to every point. The colored pieces in the original diagram show the same pieces before and after these translations.
For the Fibonacci identity, at the claimed matrix is . If the identity holds at , multiplication on the right by givesEach equality uses , with the specified indexing . This proves the formula for every positive integer .
A fixed point satisfies . Since has an inverse integer matrix, this forces , so the origin is the only fixed point modulo one.
For period dividing two,The second congruence gives ; inserting it into the first gives . Thus the complete list isThe first is the fixed origin. Direct application of exchanges the other four in exactly two pairs:This both verifies the periodic orbits and excludes additional ones.
Finally, if is fixed by , then for an integer vector . The eigenvalues of are and , neither zero. Hence its inverse exists and has rational entries by the adjugate matrix formula for an integer matrix. Therefore has rational coordinates. The derivative of the return map is , with eigenvalues and . Every periodic point is a hyperbolic saddle fixed point of a map and is unstable, although perturbations in its stable eigendirection contract.
Past exam of the topology and groups course of the University of Oxford 2023 3 a iii Solution 2026-10-25
With local path connectedness, the intended conclusion holds. Choose a base point and the standard covering mapThe fundamental group of the circle is . Since the image of a finite group under a group homomorphism is finite and has no nontrivial finite subgroups,is trivial. If is also locally path-connected, the lifting criterion for a covering space supplies a continuous map with , because . The homotopyruns from to the constant function . This proves the claimed null-homotopy under that additional hypothesis, in particular for CW complexes and the topological graphs considered later in the paper.
For arbitrary path-connected spaces, the printed assertion is false. Here is an explicit Warsaw circle counterexample, including the obstruction that the usual lifting argument misses. In the Euclidean plane takeJoin to by the polygonal arc passing successively through , and put with its subspace topology. The arc meets only at . The topologist's sine curve has two path components, but the added arc joins them, making path-connected.
Every loop in is contained infor some . To justify the assertion, a path cannot reach along the oscillating tail: the intermediate value theorem for its -coordinate would force its -coordinate to attain both and arbitrarily close to the supposed arrival time, contradicting continuity. The only alternative route from the tail to uses and the joining arc. If a loop visited tail points with , a convergent subsequence of their parameter values would approach a time at which the loop lies in . On a sufficiently small parameter interval around that time its image avoids . That would give a forbidden path from into the tail without passing through . Thus those tail coordinates have a positive lower bound. The space is a finite tree, in fact a single arc, so every such loop contracts. ConsequentlyNow define a continuous map to be on , and to make one full turn on : for a parametrization from to , set . The pieces and are closed in , and the formulas agree at , so the pasting lemma for closed subspaces proves continuity.
There is no continuous lift . Any such lift is integer-valued on , so it is constant on each of the connected spaces . Since accumulates on , continuity forces those two constants to be the same. But along a lift of has the form , giving values at and differing by , a contradiction. Finally, if had a null-homotopy, the homotopy lifting theorem for a covering map, starting with a lift of the final constant function and reversing time, would produce a continuous lift of . This theorem needs no local path connectedness of the parameter space. Hence is not null-homotopic, although has finite, indeed trivial, fundamental group.
The native PDF explicitly assumes only path connectedness here. The missing local path connectedness cannot be inferred from the finiteness of the fundamental group.
True. Choose the irrational number , and partition the rational numbers intoNo endpoint is rational, so these disjoint sets cover . Each is nonempty by the density of the rational numbers, and each is clopen in the subspace topology on .
Let two rational numbers be equivalent exactly when they belong to the same . The bijectionis well-defined. For every subset , the preimage of under the canonical projection of a quotient set is , which is open in . Thus every subset of is open: its quotient topology is the discrete topology. The usual subspace topology on the integers is also the discrete topology, because . Consequently is a homeomorphism.
Write and . The operands occupy the integer points of the square . The exact sum is representable precisely whenThe upper boundary is , and the lower boundary is . Within the operand square, the closed band between these lines is representable. The triangle below the lower line has negative overflow, and the triangle above the upper line has positive overflow. The boundary lines themselves are included.
Consequently overflow occurs exactly when or . Negative overflow requires two negative operands; positive overflow requires two nonnegative operands. Same-sign operands alone are not sufficient: their exact sum must cross a range endpoint. Opposite-sign operands never overflow on addition. In terms of the stored wrapped result, addition overflows exactly when the operands have equal sign bits and the result has the opposite sign bit.
The illustration uses , so and , and marks every permissible operand pair. The general region follows from the same two inequalities for arbitrary .
An -bit two's complement word represents the integerThe leading bit has negative weight. Words beginning with zero encode the nonnegative values; words beginning with one encode the negative values. Equivalently, interpret the whole word as unsigned and subtract when its leading bit is one. For example, the four-bit words
0111, 1000, and 1111 encode , , and respectively. The range is asymmetric: the most negative value has no positive counterpart in the same number of bits.For a nonzero representable magnitude, complementing all bits and adding one obtains its negative modulo . Fixed-width addition can therefore use the same low-order binary numeral system addition circuitry for signed and unsigned operands; interpreting the result as signed requires detecting integer overflow.
Use pattern matching to separate the empty list from a head and tail. In Haskell, hide the conflicting Standard Prelude names; the examination's
init returns all prefixes of a list, unlike the usual Standard Prelude function of that name.import Prelude hiding (map, length, init, tails, foldr, compare)
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs
length :: Num n => [a] -> n
length [] = 0
length (_:xs) = 1 + length xs
copy :: (Eq n, Num n) => n -> a -> [a]
copy 0 xs = []
copy n xs = xs : copy (n-1) xs
combine :: [[a]] -> [[a]] -> [[a]]
combine [] _ = []
combine _ [] = []
combine (xs:xss) (ys:yss) = (xs ++ ys) : combine xss yss
init :: [a] -> [[a]]
init [] = [[]]
init (x:xs) = [] : map (x:) (init xs)
tails :: [a] -> [[a]]
tails [] = [[]]
tails (x:xs) = (x:xs) : tails xsThe map function preserves the input list shape while transforming each entry.
length counts the cons cells. copy repeats the whole value xs, so for the specified use its second argument is a list and the result is a list of lists. Its inferred type is more general: the repeated value can have any data type. If one restricts the interface to lists, the corresponding type is (Eq n, Num n) => n -> [a] -> [[a]]. The numeric argument has the precondition that it is a nonnegative integer; the most general inferred numeric constraints do not guarantee termination on arbitrary values of their instances. An explicitly integral interface may instead use Integral n => n -> [a] -> [[a]].combine performs list concatenation head by head and stops as soon as either outer list ends. For init, every nonempty prefix of a list starts with x and continues with a prefix of a list from xs; prepending [] supplies the shortest prefix of a list. For tails, the longest suffix of a list is the whole input, followed by all suffixes of a list of its tail. For example, init [1,2] = [[],[1],[1,2]] and tails [1,2] = [[1,2],[2],[]]. Thus both include the empty list, andA string data type suffices for a name, an algebraic data type for the recorded sex, and a triple of integers for a date. Use a constructor for
Person so that selectors are unambiguous in Haskell:type Name = String
data Sex = Female | Male deriving (Eq, Show)
data Date = Date { day :: Int, month :: Int, year :: Int }
deriving (Eq, Show)
data Person = Person { name :: Name, sex :: Sex, born :: Date }
deriving (Eq, Show)
type BirthCertificate = (Person, Person, Person)
type Database = [BirthCertificate]Dates have the precondition that their fields form a valid calendar date. This simple database representation assumes the triple of identifying fields distinguishes the recorded individuals; a production database would normally add a stable identifier to distinguish namesakes. The two constructors for
Sex model the two recorded values used by this exercise. In mathematical notation,For nonnegative integer
x and positive integer y, initialize the quotient to zero and subtract one divisor at a time:q := 0; r := x;
WHILE r >= y DO
r := r-y;
q := q+1
ENDThe loop invariant is , , , with
x and y unchanged. It is true initially. A body execution changes to and keeps nonnegative because of the guard. The nonnegative integer loop variant strictly decreases by , so termination follows. At exit the guard supplies ; henceThere are exactly body executions. Under the unit-cost model, the time complexity including initialization and the final test is , which is for integer . This is a bound in the value of x, rather than in its encoded bit length.

