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.

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)$.

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.

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$,

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.

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

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.

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.

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.

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.

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.

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$.

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.

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.

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

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)]$.

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.

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

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⟩$.

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.

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)$.

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$.

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).

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.

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.

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.

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$.

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.

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

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}$.

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

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.

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.

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.

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.

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

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

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

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

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)$.

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)$.

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$.

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}$.

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.