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

A Carmichael number is a composite $N$ such that $a^{N-1}\equiv 1(\mathrm{mod}N)$ for every $a$ coprime to $N$. For $p\mid N$, choose by CRT a number whose residue mod $p$ is a primitive root; its order $p-1$ divides $N-1$. If $p^2\mid N$, choose instead a primitive root modulo $p^2$; then $p(p-1)\mid N-1$, impossible because $p\mid N$. Thus $N$ is square-free. Write $N=pm$. Since $p-1\mid N-1$, also $p-1\mid m-1$; compositeness gives $m>1$, hence $m\ge p$ and $p\le \sqrt{N}$. This is Korselt criterion.

Solved by gpt-5.6-sol high.

Let ${\ell }_j$ be the Lagrange basis polynomials for the nodes. Necessity and existence give uniquely $A_j={\int }_{-1}^1{\ell }_j(t)dt$, because every polynomial of degree at most $n-1$ is ${\sum }_{j}p(t_j){\ell }_j(t)$.

Solved by gpt-5.6-sol high.

For $\mathrm{deg}p\le 2n-1$, divide $p=q{p}_n+r$ with $\mathrm{deg}q\le n-1$, $\mathrm{deg}r\le n-1$. Orthogonality makes $\int q{p}_n=0$, and $p(t_j)=r(t_j)$. Apply part (i) to $r$. This is gaussian quadrature.

Solved by gpt-5.6-sol high.

Apply exactness to ${\ell }_j^2$: $A_j={\sum }_k{A}_k{\ell }_j(t_k{)}^2=\int {\ell }_j^2>0$. Applying it to 1 gives $\sum A_j=2$. For continuous $f$ and any admissible $p$,

Solved by gpt-5.6-sol high.

A Rabin cryptosystem chooses Blum primes $p,q$, publishes $N=pq$, and encrypts $m$ as $c=m^2\mathrm{mod}N$. Decryption takes square roots modulo $p$ and $q$, combines them with CRT, and uses redundancy to select the intended one of four roots. Here $2355^2\equiv 25(\mathrm{mod}2773)$, while the obvious root is $5$. ThusSo $2773=47\cdot 59$ is factored, allowing all future square roots and hence all ciphertexts to be decrypted.

Solved by gpt-5.6-sol high.

Run the algorithms for $f(n)$ and $g(n)$ and output their XOR. Closure of computable functions under composition makes $f+g$ computable.

Solved by gpt-5.6-sol high.

No. Let $X_f=\mathbb{N}$ and let $X_g=K$ be an r.e. undecidable set. Both are r.e., but $X_{f+g}=\mathbb{N}\setminus K$ is not r.e.; otherwise $K$ would be decidable.

Solved by gpt-5.6-sol high.

No. Context-free languages are not closed under symmetric difference (a standard counterexample is obtained from the two CFLs enforcing respectively equality of the first two and last two blocks in $a^{\ast }{b}^{\ast }{c}^{\ast }$). Transport such a pair through the bijection $\beta$; pointwise addition corresponds exactly to symmetric difference.

Solved by gpt-5.6-sol high.

Write $f(y;\theta )=\exp \{y\theta -b(\theta )+c(y)\}$ and use canonical parameter ${\theta }_i=X_i^T\beta$. Thenwhere ${\mu }_i=b^{\prime }(X_i^T\beta )$. Geometrically the residual vector is orthogonal to every design column. For $H_0:{\beta }_1=0$, use a two-sided Wald statistic ${\hat{\beta }}_1/\mathrm{se}({\hat{\beta }}_1)$ (or likelihood-ratio statistic), rejecting at the corresponding normal or chi-square critical value.

Solved by gpt-5.6-sol high.

Scaling by $K$, the positive fixed point is $x=1$. Linearization $x_t=1+{ϵ}_t$ gives ${ϵ}_{t+1}={ϵ}_t-r{ϵ}_{t-1}$, with characteristic polynomial ${\lambda }^2-\lambda +r$. The Jury conditions put both roots inside the unit circle exactly for $0<r<1$. At $r=1$ the roots are $e^{\pm i\pi /3}$, sixth roots of unity. The discrete Hopf resonance therefore creates a small period-six branch; expansion of the nonlinear recurrence on the centre eigenspace supplies the nonzero amplitude.

Solved by gpt-5.6-sol high.

The identity theorem says analytic functions agreeing on a set with an interior accumulation point agree throughout a connected domain. Analytic continuation is an analytic function on a larger connected domain agreeing on a nonempty overlap. Factor the denominator as $(t+i)(t-z)$. For $\Im z<0$, contour closure below giveswith a removable value at $-i$; this entire expression is the continuation. For $\Im z>0$, the displayed real-axis integral encloses only $-i$ and equals $2\pi i{e}^{-5}/(z+i)$, so it is not that continuation. Finally $1/n\to 0$ only at a boundary point of $D$, so the zeros do not determine $G$; for example $G(z)=\sin (\pi /z)$ is nonzero and has them all.

Solved by gpt-5.6-sol high.

Hamilton's equations give $\dot{H}=H_q\cdot H_p-H_p\cdot H_q=0$. Also $\mathrm{div}{V}_H={\sum }_a({\partial }_{q_a}{\partial }_{p_a}H-{\partial }_{p_a}{\partial }_{q_a}H)=0$.

Solved by gpt-5.6-sol high.

The supplied Jacobian identity and zero divergence give $J^{-1}\dot{J}=0$, so $J(t)=1$. Change of variables then shows $\mathrm{vol}{\Phi }_t(U)=\mathrm{vol}U$. This is Liouville theorem in Hamiltonian mechanics.

Solved by gpt-5.6-sol high.

The energy sublevel $H\le 1/2$ is compact and has finite phase volume because both $p$ and $q$ are bounded. If all ${\Phi }_{nT}(U)$ were disjoint, volume preservation would put infinitely many equal positive volumes inside it, impossible. Thus two iterates intersect. Pulling the intersection back shows a point of $U$ returns to $U$; applying the argument to arbitrarily small neighbourhoods gives Poincare recurrence theorem.

Solved by gpt-5.6-sol high.

Use $E=m{c}^2+p^2/(2m)+\cdots$ and replace the Fermi denominator by its Boltzmann form. The Gaussian integral gives

Solved by gpt-5.6-sol high.

At $k{T}_d=m_X{c}^2/\alpha$, division by $n_{\gamma }=16\pi \zeta (3)(kT/hc{)}^3$ gives $r(\alpha )=\sqrt{2\pi }{\alpha }^{3/2}{e}^{-\alpha }/[8\zeta (3)]$.

Solved by gpt-5.6-sol high.

Today ${\rho }_X/{\rho }_B=(m_X/mp)r/\eta \simeq {\Omega }_{DM}/{\Omega }_B\simeq 5$. Henceso $\mu =3\times 10^{-9}$. For suitable large $\alpha$ this is nonrelativistic and can match the observed abundance.

Solved by gpt-5.6-sol high.

${\mathrm{QFT}}_N|k⟩=N^{-1/2}{\sum }_{j=0}^{N-1}{e}^{2\pi ijk/N}|j⟩$.

Solved by gpt-5.6-sol high.

The controlled phases and final bit reversal implement QFT. Thus $|000⟩\mapsto 2^{-3/2}{\sum }_{j=0}^7|j⟩$, whilewhich agrees with ${\mathrm{QFT}}_8|0⟩$ and ${\mathrm{QFT}}_8|3⟩$.

Solved by gpt-5.6-sol high.

The amplitude at $y$ is proportional to $e^{2\pi i{x}_{0}y/8}{\sum }_{j=0}^{A-1}{e}^{2\pi ijry/8}$. The geometric sum vanishes unless $ry\equiv 0(\mathrm{mod}8)$, i.e. unless $y$ is a multiple of $A=8/r$. At those $r$ outcomes its modulus is $1/\sqrt{r}$, so each probability is $1/r$. The phase contains $x_0$, but measurement probabilities do not.

Solved by gpt-5.6-sol high.

A form $a{x}^2+bxy+c{y}^2$ is positive definite when $a>0$ and $d=b^2-4ac<0$; equivalence is change by $S{L}_2(\mathbb{Z})$, and reduced means $|b|\le a\le c$ with the standard boundary sign convention. Translating $x\mapsto x+my$ reduces $|b|$, and swapping variables reduces $a$; discriminant bounds force termination. For a reduced form, $|b|\le a\le \sqrt{|d|/3}$ and $b\equiv d(\mathrm{mod}2)$. Discriminant $-28$ has one primitive reduced class, represented by $x^2+7y^2$. Therefore an odd prime is represented exactly when it splits in $\mathbb{Q}(\sqrt{-7})$, namely $(p/7)=1$, with the ramified exception $p=7$. Thus $p=7$ or $p\equiv 1,9,11,15,23,25(\mathrm{mod}28)$.

Solved by gpt-5.6-sol high.

Liouville approximation theorem says that if algebraic irrational $\alpha$ has degree $d\ge 2$, then $|\alpha -p/q|>C(\alpha )q^{-d}$ for all rationals $p/q$.

Solved by gpt-5.6-sol high.

Taking determinants of the convergent matrices gives $q_n{p}_{n-1}-q_{n-1}{p}_n=(-1{)}^n$. The complete-quotient formula then yields $|\alpha -p_n/q_n|<1/(q_n{q}_{n+1})<1/q_n^2$. Comparing two consecutive errors shows at least one is below $1/(2q^2)$; hence both stated inequalities occur infinitely often (the second is the elementary precursor of Hurwitz's sharper $1/\sqrt{5}$ bound).

Solved by gpt-5.6-sol high.

Here $q_{n+1}\ge a_{n+1}{q}_n=q_n^{n+1}$, so $|\alpha -p_n/q_n|<q_n^{-(n+2)}$. If $\alpha$ were algebraic of fixed degree $d$, Liouville's theorem would contradict this for $n>d$. Thus $\alpha$ is transcendental.

Solved by gpt-5.6-sol high.

Expanding $\sum (X_i-\bar{X})(Y_i-\bar{Y})=\sum X_i{Y}_i-n\bar{X}\bar{Y}$ and taking expectations gives $(n-1)(E[XY]-EX,EY)$. Division by $n-1$ proves unbiasedness.

Solved by gpt-5.6-sol high.

The OLS normal equation with an intercept gives $\hat{\beta }=S_{XY}/S_{XX}$. By the law of large numbers it tends to $\mathrm{Cov}(X,Y)/\mathrm{Var}X$. Here $X=Z+U+{ϵ}_X$ and $Y=X+U+{ϵ}_Y$, so the limit is $(3+1)/3=4/3$, showing upward confounding bias.

Solved by gpt-5.6-sol high.

First regress $X$ on $Z$, then regress $Y$ on the fitted values. With one centred instrument this equals $S_{ZY}/S_{ZX}$. Its limit is $\mathrm{Cov}(Z,Y)/\mathrm{Cov}(Z,X)=1/1=1$, the causal coefficient of $X$ in $Y=X+U+{ϵ}_Y$.

Solved by gpt-5.6-sol high.

The left side is the flux of newborn trees through size zero. Every tree of size $s$ produces seedlings at rate $b(s)$, so total births are ${\int }_0^{\infty }b(s)n(s,t)ds$, giving the boundary condition.

Solved by gpt-5.6-sol high.

Substitution gives $(g\tilde{n}{)}^{\prime }=-(\mu +r)\tilde{n}$, henceThe boundary condition yields the Euler-Lotka equation

Solved by gpt-5.6-sol high.

The mean lifetime production is $(B/\mu )e^{-\mu s_0/g}$. A time-independent population requires it to equal one, so $B=\mu e^{\mu s_0/g}$.

Solved by gpt-5.6-sol high.

The Euler-Lotka equation becomes $1=(B/g)e^{-(\mu +r)s_{\ast }/g}$, hence $r=(g/s_{\ast })\log (B/g)-\mu$.

Solved by gpt-5.6-sol high.

Euler's equations are $I_1{\dot{\omega }}_1=(I_2-I_3){\omega }_2{\omega }_3$ and cyclic permutations. Setting two components to zero gives uniform rotation about any principal axis.

Solved by gpt-5.6-sol high.

Multiplying Euler's equations by ${\omega }_i$ and by $I_i{\omega }_i$ respectively shows $T=\frac{1}{2}\sum I_i{\omega }_i^2$ and $L^2=\sum I_i^2{\omega }_i^2$ are constant. Their ellipsoids are tangent when their normals are parallel, which occurs on the principal axes.

Solved by gpt-5.6-sol high.

Eliminating ${\omega }_2^2$ between $2T$ and $L^2$ givesThe intersections are closed near axes 1 and 3 but hyperbolic near axis 2. Thus rotations about the smallest and largest inertia axes are stable, while the intermediate-axis rotation is unstable.

Solved by gpt-5.6-sol high.

Linearization about $(0,\Omega ,0)$ gives $\dot{u}=-Av$, $\dot{v}=-Bu$, where $A=(I_3-I_2)\Omega /I_1$, $B=(I_2-I_1)\Omega /I_3$. With $\kappa =\sqrt{AB}$,The exponential growth confirms intermediate-axis instability.

Solved by gpt-5.6-sol high.

A set $x$ is transitive when $y\in z\in x$ implies $y\in x$, equivalently $\bigcup x\subset x$.

Solved by gpt-5.6-sol high.

$\mathrm{tcl}(x)$ is the least transitive set containing $x$, namely $x\cup \bigcup x\cup {\bigcup }^{2}x\cup \cdots$.

Solved by gpt-5.6-sol high.

$V_0=\varnothing$, $V_{\alpha +1}=\mathcal{P}(V_{\alpha })$, and $V_{\lambda }={\bigcup }_{\alpha <\lambda }{V}_{\alpha }$ at limits.

Solved by gpt-5.6-sol high.

The Mirimanoff rank is $\rho (x)=\min \{\alpha :x\subset V_{\alpha }\}={\sup }_{y\in x}(\rho (y)+1)$.

Solved by gpt-5.6-sol high.

From $\rho (x)={\sup }_{y\in x}(\rho (y)+1)$, if every $\rho (y)<\gamma$, then every $\rho (y)+1\le \gamma$ and the supremum is at most $\gamma$, contradicting $\gamma <\rho (x)$.

Solved by gpt-5.6-sol high.

Taking transitive closure adds only descendants of existing members, whose ranks are lower. Thus the supremum of member ranks, and hence the rank of the set, is unchanged: $\rho (x)=\rho (\mathrm{tcl}x)$.

Solved by gpt-5.6-sol high.

Induct on $\gamma$. Part (b) gives a member of rank at least $\gamma$; transitivity and descent through a member of larger rank, using the induction hypothesis, produces a member of rank exactly $\gamma$.

Solved by gpt-5.6-sol high.

If $x$ is hereditarily countable, its transitive closure contains only countably many ranks. Their supremum is a countable ordinal below ${\omega }_1$, so $x\in V_{{\omega }_1}$.

Solved by gpt-5.6-sol high.

Every real $r\subset \omega$ is hereditarily countable, giving $2^{{\aleph }_0}\le |HC|$. Conversely each HC set is represented by a well-founded extensional relation on a subset of $\omega$; there are only $2^{{\aleph }_0}$ such relations. Hence equality.

Solved by gpt-5.6-sol high.

This is Dirac theorem. Take a longest path $v_1\dots v_k$. All neighbours of its ends lie on it. If no index $i$ has both $v_1{v}_{i+1}$ and $v_k{v}_i$, the two end-neighbour sets have total size at most $k-1$, contradicting $2\delta \ge n\ge k$. Such an index closes a cycle through the path, and maximality plus connectedness makes it Hamiltonian. For even $n$, the disjoint union of two copies of $K_{n/2}$ has minimum degree $n/2-1$ and is not Hamiltonian. For odd $n$, $K_{(n-1)/2,(n+1)/2}$ has minimum degree $(n-1)/2$ and no Hamilton cycle because its bipartition sizes differ.

Solved by gpt-5.6-sol high.

Deleting $s$ vertices from a Hamilton cycle leaves at most $s$ path components, so the property is necessary. It is not sufficient: the Petersen graph is 1-tough, meaning $c(G-S)\le |S|$ for every separating set $S$, but it is not Hamiltonian.

Solved by gpt-5.6-sol high.

If $G$ were bipartite, a Hamilton path alternates parts. Endpoints in the same part require that part to have one more vertex; endpoints in opposite parts require equal sizes. Since the assumed path exists for every pair, these incompatible requirements arise. Thus $G$ is not bipartite and $\chi (G)\ge 3$.

Solved by gpt-5.6-sol high.

Artin fixed-field theorem says that for a finite group $G\le \mathrm{Aut}L$, $L/L^G$ is Galois with group $G$ and degree $|G|$. Let any finite $G$ act faithfully by left translation on variables $X_g$ in $L=\mathbb{C}(X_g:g\in G)$. Artin's theorem then realizes $G$ as $\mathrm{Gal}(L/L^G)$.

Solved by gpt-5.6-sol high.

$s_i$ is the sum of all square-free degree-$i$ monomials in the $X_j$. The symmetric group $S_n$ permutes variables and fixes exactly $K=\mathbb{C}(s_1,\dots ,s_n)$, so Artin gives $[L:K]=n!$. The Vandermonde $f={\prod }_{i<j}(X_i-X_j)$ is not symmetric, but $f^2$ is symmetric and hence belongs to $K$.

Solved by gpt-5.6-sol high.

The relations are ${\sigma }^n={\tau }^2=1$ and $\tau \sigma \tau ={\sigma }^{-1}$, so the generated group is $D_{2n}$. The functions $XY$ and $X^n+Y^n$ are fixed. Conversely $X^n,Y^n$ are roots of $T^2-(X^n+Y^n)T+(XY{)}^n$, and adjoining $X$ then $Y$ gives degree at most $2n$. Artin gives degree exactly $|G|=2n$, proving $M^G=\mathbb{C}(X^n+Y^n,XY)$.

Solved by gpt-5.6-sol high.

Mackey and induced representation sum over $H\backslash G/K$. Coprimality makes every $H\cap gK{g}^{-1}$ trivial, each double coset has size $|H||K|$, and each local inner product is $(\dim V)(\dim W)$. Therefore

Solved by gpt-5.6-sol high.

Odd order makes squaring bijective: squaring preserves the odd order of each element, and any square root $x$ of $g$ lies in $⟨g⟩$ because $x=(x^2{)}^m$ for an inverse $m$ of $2$ modulo $|x|$. Thus $g$ has the unique root $g^m$. Hence $⟨\tilde{\chi },\tilde{\chi }⟩=|G{|}^{-1}{\sum }_g|\chi (g^2){|}^2=1$.

Solved by gpt-5.6-sol high.

The second Adams operation $\chi \mapsto [g\mapsto \chi (g^2)]$ lies in the integral character ring, so $\tilde{\chi }=\sum n_i{\chi }_i$ with integers $n_i$. Norm one forces exactly one coefficient to be $\pm 1$; evaluation at the identity makes the sign positive. Squaring is bijective on conjugacy classes as well, so distinct irreducibles remain distinct. Thus the ${\tilde{\chi }}_i$ permute the irreducible characters.

Solved by gpt-5.6-sol high.

The left side is the norm form $N_{K/\mathbb{Q}}(x+y\alpha +z{\alpha }^2)$ for ${\alpha }^3=7$. Reducing a hypothetical equation modulo 7 and then descending through the forced divisibilities of $x,y,z,t$ gives an infinite descent, so only the zero solution exists. If $N(\theta )=3$, clearing denominators minimally and applying the norm equation would produce a forbidden nonzero integer solution; hence no such $\theta$ exists.

Solved by gpt-5.6-sol high.

Dedekind's criterion factors $(p)$ according to the factorization of $X^3-7$ modulo $p$ (the monogenic assumption removes the index obstruction). With $\alpha =\sqrt[3]{7}$,Minkowski's bound is below 11, so classes are generated by prime ideals over $2,3,5,7$. Relations from the displayed factorizations and principal ideals reduce them to $\mathfrak{p}=(3,\alpha -1)$ with ${\mathfrak{p}}^3$ principal. Part (a) shows $\mathfrak{p}$ is not principal, so $\mathrm{Cl}(K)\simeq \mathbb{Z}/3\mathbb{Z}$.