Past exam of the mathematics course of the University of Cambridge / 2026 / ii / Paper 1

A primitive root modulo $N$ is a unit of order $\phi (N)$; a nonzero quadratic residue modulo an odd prime $p$ is a square.

If a primitive root $g$ modulo $p$ were $x^2$, then its order would divide $(p-1)/2$, the order of the subgroup of squares, contradicting ${\mathrm{ord}}_p(g)=p-1$.

Modulo $11$, $2$ has order $10$, so the primitive roots are $2^k$ for $\gcd (k,10)=1$:Finally $2^{10}=1024\equiv 56\not\equiv 1(\mathrm{mod}121)$, so the lifting criterion makes $2$ primitive modulo $121$. It is plainly the smallest possible positive primitive root.

Solved by gpt-5.6-sol high.

The planar Brouwer fixed-point theorem says every continuous $F:D^2\to D^2$ has a fixed point. The equivalent no-retraction theorem says no continuous $r:D^2\to S^1$ restricts to the identity on $S^1$. A fixed-point-free map gives a retraction by extending the ray from $F(x)$ through $x$ to the boundary; a retraction followed by the antipodal map gives a fixed-point-free self-map.

Suppose the stated sphere map is not onto and omits $p$. Compactness gives $\epsilon >0$ such that its image lies in $S^2\setminus B_{\epsilon }(p)$. That set is homeomorphic to a closed disc. Restricting $f$ to it gives a continuous self-map of a disc, so Brouwer supplies a fixed point, contrary to the hypothesis. Hence $f$ is surjective.

Solved by gpt-5.6-sol high.

Apply Huffman coding. Combining weightsgives, for example,Any consistent interchange of siblings is equivalent.

Solved by gpt-5.6-sol high.

For the binary code above, the lengths are $1,2,3,5,5,5,5$. ThusThis is optimal by Huffman coding.

Solved by gpt-5.6-sol high.

The ternary merges are $(.02,.03,.04)\mapsto .09$, then $(.04,.09,.14)\mapsto .27$, then $(.27,.28,.45)\mapsto 1$. One code isIts expected length is

Solved by gpt-5.6-sol high.

The basic functions are zero $Z(\mathbf{x})=0$, successor $S(n)=n+1$, and projections $P_i^k(\mathbf{x})=x_i$. Close these under composition and primitive recursion:

Solved by gpt-5.6-sol high.

Define $A(0,m)=m$ and $A(n+1,m)=S(A(n,m))$. This is primitive recursion from a projection and successor, so $A(n,m)=n+m$ is primitive recursive function.

Solved by gpt-5.6-sol high.

If $f$ is primitive recursive, then $d(n)=f(P_1^1(n),P_1^1(n))$ is obtained by composition with projections. Hence the diagonal is primitive recursive.

Solved by gpt-5.6-sol high.

Assume a complete list $f$ were primitive recursive. Closure under diagonal composition and successor makesprimitive recursive. Completeness gives a row $n$ with $f(n,k)=d(k)$ for every $k$, but at $k=n$ this says $f(n,n)=f(n,n)+1$. This is the diagonal argument.

Solved by gpt-5.6-sol high.

The normal linear model is $Y=X\beta +\epsilon$ with $\epsilon \sim N(0,{\sigma }^2{I}_n)$. Full column rank givesWith hat matrix $H=X(X^{T}X{)}^{-1}{X}^T$, the $i$th regression leverage is $h_{ii}$. Since $e=(I-H)Y=(I-H)\epsilon$ and $I-H$ is an orthogonal projection,High-leverage observations can move their own fitted values strongly and may exert disproportionate influence; residual size alone can therefore conceal them.

Solved by gpt-5.6-sol high.

The cross-infection terms transfer susceptible individuals into the infected class: $\beta S\hat{I}$ is male incidence caused by infected females and $\hat{\beta }\hat{S}I$ is female incidence caused by infected males. The terms $\nu I$ and $\hat{\nu }\hat{I}$ are recovery flows back to susceptibility. Adding each susceptible-infected pair shows that $N$ and $\hat{N}$ are conserved.

Solved by gpt-5.6-sol high.

Substitute $S=N-I$ and $\hat{S}=\hat{N}-\hat{I}$:Besides the origin, solve both nullcline equations. Eliminating one infected population givesThe assumed epidemic threshold inequality makes both positive.

Solved by gpt-5.6-sol high.

At the origin the Jacobian isThus it is a saddle and unstable. At the positive equilibrium the trace is negative. The product of the off-diagonal entries is $\nu \hat{\nu }$ by the nullcline identities, while the product of the magnitudes of the diagonal entries is strictly larger, so the determinant is positive. Both eigenvalues therefore have negative real part and the endemic equilibrium is stable.

Solved by gpt-5.6-sol high.

The ordinary integral fails because the simple real poles at $-2$ and $3$ produce nonintegrable logarithmic singularities. Partial fractions giveClosing above for $\omega >0$ and below for $\omega <0$, with symmetric semicircular indentations, yieldsTaking real and imaginary parts,All integrals here run over $\mathbb{R}$.

Solved by gpt-5.6-sol high.

Stationarity of the action under variations with fixed endpoints gives the Euler-Lagrange equation. The generalized momentum is $p=\partial L/\partial \dot{q}$. The Legendre transform in mechanics isafter solving $p(q,\dot{q},t)$ for $\dot{q}$. This requires at least local invertibility, ${\partial }^{2}L/\partial {\dot{q}}^2\ne 0$; global single-valuedness requires global invertibility.

Solved by gpt-5.6-sol high.

By Hamiltonian of a charged particle,

Solved by gpt-5.6-sol high.

HereHence

Solved by gpt-5.6-sol high.

Differentiate $\mathcal{G}={\sum }_i{\mathbf{p}}_i\cdot {\mathbf{r}}_i$:

Solved by gpt-5.6-sol high.

Pair the $ij$ and $ji$ terms and use ${\mathbf{f}}_{ji}=-{\mathbf{f}}_{ij}$:For gravity, ${\mathbf{f}}_{ij}=-G{m}^2({\mathbf{r}}_i-{\mathbf{r}}_j)/|{\mathbf{r}}_i-{\mathbf{r}}_j{|}^3$, so each summand is $-G{m}^2/|{\mathbf{r}}_i-{\mathbf{r}}_j|$. Their sum is $V$.

Solved by gpt-5.6-sol high.

For a confined system, $\mathcal{G}(t)$ stays bounded, so its long-time averaged derivative is zero. The preceding identities give the virial theorem

Solved by gpt-5.6-sol high.

Estimate $T\sim M⟨v^2⟩/2$ and $V\sim -G{M}^2/⟨R⟩$. The virial theorem givesup to a profile-dependent factor. If this exceeds the stellar/gas luminous mass, the difference is attributed primarily to dark matter (with modelling uncertainties and non-equilibrium effects checked).

Solved by gpt-5.6-sol high.

The quantum no-signalling principle says Alice's uncommunicated local choice cannot alter Bob's reduced state. Expanding the two tensor products cancels the cross terms and givesAlice obtains either result with probability $1/2$; conditionally Bob has probability ${\cos }^2\theta$ or ${\sin }^2\theta$ of $0$, respectively. Averaging,independent of $\theta$, exactly as no-signalling requires.

Solved by gpt-5.6-sol high.

The Helstrom-Holevo bound for equal priors isPerfect cloning twice changes overlap $c$ to $c^2$, so discrimination would succeed with $\frac{1}{2}(1+\sqrt{1-c^4})$, strictly exceeding $\frac{1}{2}(1+\sqrt{1-c^2})$ for $0<c<1$. For $|0⟩,|+⟩$, $c=1/\sqrt{2}$, producing $\frac{1}{2}(1+\sqrt{3}/2)>\frac{1}{2}(1+1/\sqrt{2})$, a contradiction.

Solved by gpt-5.6-sol high.

The parity-check matrix has rank $3$, so its kernel has dimension $7-3=4$ and size $16$; see linear code. Its columns are precisely the seven distinct nonzero vectors of ${\mathbb{F}}_2^3$. Thus no weight-one or weight-two word is in the kernel, while three dependent columns give a weight-three word. Hence $d=3$.

Solved by gpt-5.6-sol high.

By parity extension, each code keeps size $16$, gains length $8$, and has distance $4$. Extension is injective. A common extended word punctures to a word in $H\cap K$, so only the zero and all-one words occur; both extend to $00000000$ and $11111111$.

Solved by gpt-5.6-sol high.

Write the three blocks as $u=a+x$, $v=b+x$, $w=a+b+x$. Over ${\mathbb{F}}_2$,Thus the parameters are unique and $|G|=|H^{\prime }{|}^2|K^{\prime }|=16^3=2^{12}$.

Solved by gpt-5.6-sol high.

Every nonzero word has weight divisible by $4$. Weight $4$ is impossible: using $u+v=a+b$, $u+w=b$, $v+w=a$, and $u+v+w=x$, the distance-four properties force any nonzero one of these sums to have weight $4$; coordinate counting in total weight $4$ then forces two blocks to vanish, which would put a nontrivial word in $H^{\prime }\cap K^{\prime }$. That intersection contains only $0$ and $1$, and $1$ gives block weight at least $8$. Hence $d(G)\ge 8$, and taking $a\ne 0,b=x=0$ gives weight $2\mathrm{wt}(a)=8$, so $d(G)=8$.

Solved by gpt-5.6-sol high.

Puncturing gives a binary code of length $23$, size $2^{12}$, and distance at least $7$. Radius-three balls are disjoint andThe Hamming bound is an equality, so $G^{-}$ is perfect.

Solved by gpt-5.6-sol high.

A variable-based grammar is $(N,\Sigma ,P,S)$ with disjoint nonterminals and terminals, productions between words over $N\cup \Sigma$, and start variable $S$. Its language is $\{w\in {\Sigma }^{\ast }:S{\Rightarrow }^{\ast }w\}$.

Solved by gpt-5.6-sol high.

A type-2 rule is $A\to \alpha$ with one nonterminal $A$ on the left; a type-2 grammar and its language are context-free languages. The required repetition criterion is the pumping lemma for context-free languages.

Solved by gpt-5.6-sol high.

This language is context-free. One grammar iswhich independently chooses at least one outer $a,c$ pair and at least one $b$.

Solved by gpt-5.6-sol high.

It is not context-free. Intersecting it with the regular language $a^{\ast }{b}^{\ast }{c}^{\ast }$ would give $\{a^n{b}^n{c}^n:n\ge 0\}$, which violates the pumping lemma for context-free languages. Context-free languages are closed under intersection with regular languages.

Solved by gpt-5.6-sol high.

No production introduces $A$, so the two rules containing $A$ are unreachable. The effective derivations areThus the language is $\{a^n{b}^n{c}^n:n\ge 1\}$, which is not context-free language, although the displayed grammar itself also visibly has non-type-2 left sides.

Solved by gpt-5.6-sol high.

For one observation,Thus this is an exponential family with natural parameter $\theta =\log \lambda$, statistic $T(y)=y$, base measure $1/y!$, and cumulant $A(\theta )=e^{\theta }$.

Solved by gpt-5.6-sol high.

For nonnegative $y_i$ summing to $m$, divide the joint Poisson mass by $P(M=m)=e^{-{\lambda }_{+}}{\lambda }_{+}^m/m!$:This is independent Poisson conditioning.

Solved by gpt-5.6-sol high.

In the log-linear model fit1 has only three main effects, so its fitted mean factors into a species factor, a diameter factor, and a height factor: mutual independence. Fit2 adds the species-diameter interaction, allowing those variables to associate, while asserting $\text{Height}\perp (\text{Species},\text{Diameter})$.

The likelihood-ratio deviance drop $12.606$ on one degree of freedom has $p=0.0003845$, strong evidence against species-diameter independence. Test fit2's remaining independence claim by comparing it with a model adding both Species:Height and Diameter:Height interactions (equivalently compare fit2 with the saturated model); its residual deviance $12.431$ is assessed against ${\chi }_3^2$.

Solved by gpt-5.6-sol high.

Put $\Gamma (z)=I(z)$ for $\Re z>0$. Integration by parts gives $\Gamma (z+1)=z\Gamma (z)$, both proving $\Gamma (n)=(n-1)!$ and defining the meromorphic continuation. A keyhole-contour evaluation of ${\int }_0^{\infty }{t}^{z-1}/(1+t)dt$ gives

Forthe reflection formula at $z$ and $z+\frac{1}{2}$ gives $g(z+1)-g(z)=-2\log 2$. Thus $h(z)=g(z)+2z\log 2$ is entire and $1$-periodic; poles and zeros have cancelled in the quotient. Its Fourier expansion and the exponential growth bound make it a finite Laurent polynomial in $e^{2\pi iz}$; the same growth bound for $e^h$ excludes every nonconstant mode. Hence $h=b$. At $z=1/2$, $e^b=2\sqrt{\pi }$, yielding the duplication formula.

Set $z=1/6$ and use reflection at $1/3$:Therefore

Solved by gpt-5.6-sol high.

The conservation equation with $P=w\rho$ gives $d\rho /\rho =-3(1+w)da/a$, henceThe critical density and density parameter are

Solved by gpt-5.6-sol high.

Radiation has $w=1/3$, matter $w=0$, and a cosmological constant has constant density. With negligible curvature and present-day normalization,where the present density fractions sum to one.

Solved by gpt-5.6-sol high.

Phantom energy with $w=-4/3$ has ${\rho }_P\propto a$, so flatness givesFor $b^2=1+{\beta }^{2}a$, integration yieldsSolving gives the displayed scale factorFor $1-\Omega \ll 1$ and times near $t_0$, this approaches de Sitter growth $e^{H_0\sqrt{\Omega }(t-t_0)}$. The denominator vanishes atEven a tiny phantom fraction therefore ends expansion in finite time; its divergent density ultimately disrupts loosely bound systems.

Solved by gpt-5.6-sol high.

A choice function on a family $\mathcal{A}$ of nonempty sets satisfies $c(A)\in A$. Zermelo's theorem says every set has a total order under which every nonempty subset has a least element.

Solved by gpt-5.6-sol high.

Choose from every nonempty subset of $X$. By transfinite recursion setwhile the remainder is nonempty. This cannot continue through Hartogs theorem's ordinal $h(X)$, since that would inject $h(X)$ into $X$. It therefore exhausts $X$ at some ordinal, and the selection order well-orders $X$.

Solved by gpt-5.6-sol high.

Hessenberg's theorem in ZF states that every infinite well-orderable cardinal satisfies $\kappa \times \kappa =\kappa$; equivalently $|\alpha \times \alpha |=|\alpha |$ for every infinite ordinal $\alpha$.

Solved by gpt-5.6-sol high.

Choice well-orders every infinite $X$, so Hessenberg gives $X^2\cong X$. Conversely assume this square identity for every infinite set. For arbitrary $X$, form the disjoint union $Y=X\bigsqcup h(X)$. A pairing $Y^2\cong Y$, together with the well-order on $h(X)$, yields by the standard tracing/comparison argument an injection either $h(X)\to X$ or $X\to h(X)$. The first is forbidden by Hartogs theorem, so the second well-orders $X$. This is Tarski cardinal-square theorem, and hence choice follows.

Solved by gpt-5.6-sol high.

A matching from $X$ to $Y$ consists of disjoint edges saturating every vertex of $X$. The criterion is Hall marriage theorem.

For sufficiency, induct on $|X|$. If a nonempty proper $S\subset X$ is tight, $|N(S)|=|S|$, apply induction to $S,N(S)$ and to the graph left after deleting them. If no proper set is tight, choose any edge $xy$, delete its endpoints, and Hall still holds because every nonempty proper subset formerly had at least one spare neighbour. Induction completes the matching. Necessity is immediate.

Solved by gpt-5.6-sol high.

For $S\subseteq X$, count with reciprocal degrees. On every edge $xy$, $d(x)\ge d(y)$, soHall's condition holds, so Hall marriage theorem supplies the matching.

Solved by gpt-5.6-sol high.