Past exam of the mathematics course of the University of Cambridge / 2018 / ia / Paper 4

Fermat's little theorem states that if $p$ is prime, then $a^p\equiv a(\mathrm{mod}p)$ for every integer $a$; equivalently, $a^{p-1}\equiv 1(\mathrm{mod}p)$ when $p\nmid a$.

If $p\equiv 3(\mathrm{mod}4)$ and $x^2\equiv -1(\mathrm{mod}p)$, thenbecause $(p-1)/2$ is odd. This contradicts Fermat's theorem, so $x^2\equiv -1(\mathrm{mod}p)$ has no solution.

If the primes congruent to $1(\mathrm{mod}4)$ were $p_1,\dots ,p_k$, set $N=(2p_1\cdots p_k{)}^2+1$. Any prime divisor $q$ of $N$ is odd and has $-1$ as a quadratic residue. The preceding result forces $q\equiv 1(\mathrm{mod}4)$, but $q$ divides none of the $p_i$ because $N\equiv 1(\mathrm{mod}{p}_i)$. This contradiction proves that infinitely many primes are congruent to $1(\mathrm{mod}4)$.

Suppose $\sqrt{n}=a/b$ in lowest terms. Then $a^2=n{b}^2$. Comparing prime exponents shows that every prime dividing $b$ also divides $a$, unless $b=1$. Hence $\sqrt{n}=a$ is an integer. Therefore $\sqrt{n}$ is either an integer or irrational.

Only $\alpha +q$ must be irrational: if it were rational, subtracting rational $q$ would make $\alpha$ rational. None of the others must be irrational:For ${\alpha }^{\beta }$, let $r=(\sqrt{2}{)}^{\sqrt{2}}$. If $r$ is rational, $\alpha =\beta =\sqrt{2}$ is a counterexample. If $r$ is irrational, take $\alpha =r$ and $\beta =\sqrt{2}$; then ${\alpha }^{\beta }=2$. Thus $\alpha +q$ is the sole expression forced to be irrational.

An inertial frame is a reference frame in which a force-free particle moves with constant velocity, so Newton's first law holds.

The basic Galilean transformations include spacetime translations ${\mathbf{x}}^{\prime }=\mathbf{x}-\mathbf{a}$, $t^{\prime }=t-b$; spatial rotations ${\mathbf{x}}^{\prime }=R\mathbf{x}$, $t^{\prime }=t$; and boosts ${\mathbf{x}}^{\prime }=\mathbf{x}-\mathbf{v}t$, $t^{\prime }=t$, where $R$ is a rotation matrix and $\mathbf{v}$ is constant.

The Principle of Galilean relativity states that the laws of mechanics have the same form in every inertial frame.

The equation of motion isMultiplication by $\dot{x}$ givesso the mechanical energy $E=\frac{1}{2}m{\dot{x}}^2+V(x)$ is conserved. On a segment where the direction of motion is fixed,

For $V=(x^2-4{)}^2$, $V^{\prime }=4x(x^2-4)$. Thus $x=\pm 2$ are stable equilibria at the two potential minima, while $x=0$ is unstable at the local maximum.

For $x\ne 0$, $V^{\prime }(x)=2x^{-3}{e}^{-1/x^2}$ never vanishes. At $x=0$, the smooth flat extension has $V^{\prime }(0)=0$, and $V(x)>V(0)=0$ for every $x\ne 0$. Hence $x=0$ is the unique equilibrium and is stable.

A central force has the form $\mathbf{F}=f(r)\hat{\mathbf{r}}$, so it always points along the line from a fixed centre to the particle. Its torque about the centre vanishes:Thus angular momentum is conserved. Since $\mathbf{r}\cdot \mathbf{L}=0$, the trajectory lies in the fixed plane through the origin perpendicular to $\mathbf{L}$.

The area swept in time $dt$ is $dA=\frac{1}{2}|\mathbf{r}\times d\mathbf{r}|$, sowhich is constant. This proves Kepler's second law.

Bezout identity gives integers $b,c$ with $ab+nc=1$ whenever $\gcd (a,n)=1$, so $ab\equiv 1(\mathrm{mod}n)$. If $b,b^{\prime }$ are inverses, multiplying $a(b-b^{\prime })\equiv 0$ by an inverse gives $b\equiv b^{\prime }(\mathrm{mod}n)$. Multiplying Bezout identities for $a$ and $b$ shows that $\gcd (ab,n)=1$.

Wilson theorem states that $(p-1)!\equiv -1(\mathrm{mod}p)$ for prime $p$. Pair the nonzero residues with their unique multiplicative inverses. The only self-inverse residues are $1,-1$, whose product is $-1$, proving the theorem.

Counting one factor of $p$ for every multiple of $p$, another for every multiple of $p^2$, and so on proves Legendre formulaNow $22!\equiv 20!\cdot 21\cdot 22\equiv 2(20!)\equiv -1(\mathrm{mod}23)$, so $20!\equiv 11(\mathrm{mod}23)$. Also $v_5(1000!)=200+40+8+1=249$, while $v_2(1000!)>249$, so $1000!\equiv 0(\mathrm{mod}10^{249})$.

Finally,For $1\le j<p^m$, $v_p(p^m-j)=v_p(j)$, so the second factor is a $p$-adic unit. If $v_p(k)=\ell$, then

The Hamming distance satisfies the triangle inequality coordinate by coordinate: if $x_i\ne z_i$, then $x_i\ne y_i$ or $y_i\ne z_i$. Summing these indicator inequalities proves the claim. A word at distance exactly $i$ from $x$ is obtained by choosing the $i$ coordinates to flip, so

For a $k$-code, radius-$k$ balls about codewords are disjoint, giving $|C|{\sum }_{i=0}^k\left(\genfrac{}{}{0ex}{}{n}{i}\right)\le 2^n$. Conversely, take a maximal code of minimum distance $2k+1$. Its radius-$2k$ balls cover $Q_n$, since an uncovered word could otherwise be added, so $2^n\le |C|{\sum }_{i=0}^{2k}\left(\genfrac{}{}{0ex}{}{n}{i}\right)$. Maximizing gives the requested coding bounds.

For $(n,k)=(4,1)$, translate a codeword to $0000$. Every other word has weight at least three, but any two distinct length-four words of weight at least three have distance at most two. Thus at most one can accompany $0000$, while $\{0000,1111\}$ works. Hence $M(4,1)=2$.

Let $M=\{i:x\in A_i\}$, with $|M|=m$. Then $1_{A_S}(x)=1$ exactly when $S\subseteq M$, and the sum becomesThis is $1$ when $m=t$ and $0$ otherwise. Summing over $x\in X$ yieldsTaking the complement of the $t=0$ case gives the inclusion-exclusion principle

If $p_1,\dots ,p_r$ are the distinct prime divisors of $N$, inclusion-exclusion removes their multiples from $\{1,\dots ,N\}$ and givesFor the stated squarefree $n=q_1\cdots q_k$ and $\gcd (x,n)=1$, Fermat's theorem gives $x^{q_j-1}\equiv 1(\mathrm{mod}{q}_j)$. Since $q_j-1\mid n-1$, every $q_j$ divides $x^{n-1}-1$; their product does too. Thus $n$ is a Carmichael number.

A set is countable if it is finite or bijects with a subset of $\mathbb{N}$. For any $f:X\to \mathcal{P}(X)$, the Cantor diagonal argument set $D=\{x:x\notin f(x)\}$ differs from every $f(y)$ at $y$. Hence no such map is surjective. Binary sequences are indicator functions of subsets of $\mathbb{N}$, so $\{0,1{\}}^{\mathbb{N}}\cong \mathcal{P}(\mathbb{N})$ is uncountable.

Every member of $L$ corresponds to a unique permutation $(a_0,a_1,\dots )$ of $\mathbb{N}$, with $F_n=\{a_0,\dots ,a_{n-1}\}$. Let $p(j)$ be the position of $j$.

For $L_0$, $p(n)<n$ eventually. Choose $N$ after which this holds and then $m$ larger than all $p(0),\dots ,p(N-1)$. The $m$ positions $0,\dots ,m-1$ would contain all $m+1$ values $0,\dots ,m$, a contradiction. Thus $L_0$ is empty, hence countable.

For $L_1$, $p(n)\le n$ eventually. For every sufficiently large $m$, all values $0,\dots ,m$ occur in positions $0,\dots ,m$, so this initial segment is invariant. Comparing consecutive invariant initial segments gives $p(m)=m$ eventually. These are the finite-support permutations, of which there are countably many. Hence $L_1$ is countable.

For rolling without slipping, $\dot{s}=a\Omega$. Conservation of energy givesand differentiation yields

For a sphere with density proportional to $r^c$,so $I/(M{a}^2)=2(c+3)/(3(c+5))$. A uniform disc has $I/(M{a}^2)=1/2$. Equal launch speeds give equal return times exactly when the accelerations, and hence these ratios, agree. Solving gives $c=3$.

Let $M$ be the mass of a complete uniform sphere of radius $a$. The intact marble has $I_1=2M{a}^2/5$. Each removed bubble has mass $M/8$, radius $a/2$, and centre a distance $a/2$ from the rolling axis. By the parallel axis theorem, each removesThus $M_2=3M/4$, $I_2=2M{a}^2/5-7M{a}^2/80=5M{a}^2/16$, and $I_2/(M_2{a}^2)=5/12$. The two accelerations are therefore $(5/7)g\sin \alpha$ and $(12/17)g\sin \alpha$. From rest, distance is proportional to acceleration, so

The four-momentum isThusMultiplication by $c$ identifies the first two terms as the rest energy $m{c}^2$ and the Newtonian kinetic energy $m|\mathbf{u}{|}^2/2$.

For the fixed-target reaction, the initial invariant isAt threshold the four final particles are at rest in their centre-of-momentum frame, giving invariant $(4mc{)}^2$. Hence $\gamma =7$ and the least laboratory speed is

Four-momentum conservation gives $P={\sum }_i{Q}_i$, while the mass-shell condition gives $P\cdot P=M^2{c}^2$. ThereforeIn the parent rest frame, $M{c}^2={\sum }_i{E}_i$, and each relativistic energy obeys $E_i\ge m_i{c}^2$. Thus

Work in the rest frame of $B$. Two-body decay kinematics gives the massless-particle energiesIf $\theta$ is the angle between their momenta, thenSince $0\le 1-\cos \theta \le 2$,

The Lorentz force law is $\mathbf{F}=q(\mathbf{E}+\mathbf{v}\times \mathbf{B})$. Before impact the acceleration toward the wall is $a=qE/m$, so the first-impact speed is $v_0=\sqrt{2qEh/m}$.

After the $n$th bounce, the outward speed is ${\gamma }^n{v}_0$, so the outward height is ${\gamma }^{2n}h$ and that excursion contributes twice this distance. Henceso $q_1(\gamma )=1+{\gamma }^2$ and $q_2(\gamma )=1-{\gamma }^2$.

With quadratic drag, put $w=-\dot{z}\ge 0$. Thenwhose solution is $w=\sqrt{qE/\alpha }\tanh (\sqrt{\alpha qE}t/m)$. Integration givesThus $A=m/\alpha$, $B=\sqrt{\alpha qE}/m$, and $f(s)=\log \cosh s$.

For constant angular velocity, the equation of motion in a rotating frame isFor $\mathbf{\omega }=(0,0,\omega )$ and $\xi =x+iy$, the planar equations combine toThe initial conditions giveThereforeThe maximum speed and, for $\omega >0$, its times are