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

Subtracting twice the first linear congruence from the second gives $5x\equiv 1(\mathrm{mod}53)$. Since $5\cdot 32=3\cdot 53+1$, the modular inverse of $5$ modulo $53$ is $32$. Thus $x\equiv 32(\mathrm{mod}53)$. Substitution in the first linear congruence then gives $2y\equiv 23(\mathrm{mod}53)$, whence $y\equiv 38(\mathrm{mod}53)$. All integer solutions areThe two free integers are independent. Conversely, these values give $6x+2y\equiv 268\equiv 3$ and $17x+4y\equiv 696\equiv 7(\mathrm{mod}53)$, so no additional restriction is needed.

Write the composite number as $n=ab$, with $2\le a\le b<n$. If $a<b$, both $a$ and $b$ occur as distinct factors of the factorial $(n-1)!$, so their product $n$ divides that factorial.

If $a=b$, then $n=a^2$ and $n>4$ implies $a\ge 3$. Both $a$ and $2a$ are distinct factors in $(n-1)!$, because $2a\le a^2-1$. Their product is $2n$, so again $n$ divides the factorial. HenceThe exception $n=4$ matters: its factorial $3!=6$ is not divisible by $4$. This argument handles perfect squares without incorrectly counting the same factor twice.

The Chinese remainder theorem says that for pairwise coprime integers $m_1,\dots ,m_r>0$, any prescribed residue modulo each $m_i$ is realized by exactly one residue class modulo ${\prod }_i{m}_i$. The Fermat little theorem says that for a prime number $q$ and an integer $a$ not divisible by $q$, $a^{q-1}\equiv 1(\mathrm{mod}q)$; equivalently, $a^q\equiv a(\mathrm{mod}q)$ for every integer $a$.

For the given prime number, write $p=2k+1$. Its square is $p^2=1+4k(k+1)=1+8t$ for some integer $t$, since one of two consecutive integers is even. Therefore $p^4=(1+8t{)}^2\equiv 1(\mathrm{mod}16)$. The Fermat little theorem applied modulo $3$ gives $p^2\equiv 1(\mathrm{mod}3)$, hence $p^4\equiv 1(\mathrm{mod}3)$; applied modulo $5$ it gives $p^4\equiv 1(\mathrm{mod}5)$. These applications are valid because $p>5$.

The three moduli $16,3,5$ are pairwise coprime integers and have product $240$. By the Chinese remainder theorem,

Let the uniform mass density be $\rho =3M/(4\pi a^3)$. In spherical polar coordinates about the rotation axis, the perpendicular distance is $r\sin \theta$ and the volume element is $r^2\sin \theta drd\theta d\varphi$. The moment of inertia is thereforeIn the given rigid body kinetic energy decomposition, $\frac{1}{2}M|\dot{\mathbf{R}}{|}^2$ is the translational kinetic energy of the whole mass moving at its center of mass velocity. The term $\frac{1}{2}I{\omega }^2$ is the rotational kinetic energy about the center of mass. The mixed term vanishes because the mass-weighted relative positions sum to zero.

For rolling without slipping, the point of contact has zero instantaneous velocity relative to the stationary surface. Its rotational velocity is opposite the center of mass velocity and has magnitude $a|\omega |$. Hence $V=a|\omega |$. Substituting this and the moment of inertia of a uniform solid sphere givesThe rotational axis is through the center of mass and parallel to the surface, perpendicular to the direction of rolling.

Use the Minkowski metric convention $+---$. A particle's four-momentum is $P=(E/c,\mathbf{p})$, with $P\cdot P=m^2{c}^2$ for rest mass $m$. For a photon, its energy and wavelength obey $E=hc/\lambda$, and its four-momentum is null. Here $h$ is the Planck constant.

The initially stationary electron has $P=(mc,0,0,0)$. Choose the scattering plane as the $xy$ plane. The incoming and outgoing photon four-momenta areBy four-momentum conservation, the final electron has $P^{\prime }=P+K_1-K_2$. Its rest mass is unchanged, so the relativistic energy-momentum relation gives $P^{\prime 2}=P^2=m^2{c}^2$. Since $K_1^2=K_2^2=0$, expansion yieldsorMultiplying through gives the Compton scattering shift:It is nonnegative and vanishes for forward scattering, consistent with the recoil energy being supplied by the photon.

For an equivalence relation $\sim$ on $X$, the equivalence class of $x\in X$ is $[x]=\{y\in X:y\sim x\}$. A set partition is a family of nonempty, pairwise disjoint subsets whose union is $X$.

Reflexivity ensures $x\in [x]$, so every equivalence class is nonempty and every element belongs to one. If $[x]\cap [y]$ contains $z$, then $z\sim x$ and $z\sim y$; symmetry and transitivity give $x\sim y$. If $w\in [x]$, transitivity gives $w\sim y$, so $w\in [y]$; interchanging $x,y$ gives the reverse inclusion. Thus intersecting equivalence classes are equal.

Taking the collection of distinct equivalence classes therefore produces a set partition of $X$. Every element lies in exactly one class. If $X$ is empty, the empty family is its set partition.

Reflexivity follows by taking the two exponents equal to $1$, and symmetry is built into the two divisibility conditions. For transitivity, suppose $m\mid n^a$, $n\mid m^b$, $n\mid {\ell }^c$ and $\ell \mid n^d$. Then $m\mid {\ell }^{ac}$ and $\ell \mid m^{bd}$, with positive exponents. Thus the relation is an equivalence relation.

Its equivalence classes have a useful description by prime factorization. Let $S(n)$ be the finite set of prime factors of $n$, with $S(1)=\varnothing$. If $m\mid n^a$, every prime factor of $m$ divides $n$; the reverse divisibility gives $S(n)\subseteq S(m)$. Conversely, if $S(m)=S(n)$, write $m={\prod }_{p\in S}{p}^{{\alpha }_p}$ and $n={\prod }_{p\in S}{p}^{{\beta }_p}$, with all exponents positive. Choosing $a\ge {\max }_p\lceil {\alpha }_p/{\beta }_p\rceil$ and $b\ge {\max }_p\lceil {\beta }_p/{\alpha }_p\rceil$ gives the required divisibilities. The empty case is exactly $m=n=1$.

Therefore the prime-support equivalence relation iswhere the radical of an integer is the product of its distinct prime factors. The class with empty support is $\{1\}$. For every nonempty finite support $S$, all positive exponent choices give one class, and varying just one exponent produces infinitely many different integers in it.

There are infinitely many classes because each prime number gives a different singleton support. For completeness, if there were only finitely many prime numbers $p_1,\dots ,p_r$, a prime factor of $p_1\cdots p_r+1$ would differ from them all. There are infinitely many classes; the unique finite class is $\{1\}$.

Suppose two base-p expansions represent the same nonnegative integer. Pad the shorter one by trailing zero digits so that both have the same length. Reducing modulo $p$ shows that their first digits satisfy $k_0\equiv k_0^{\prime }(\mathrm{mod}p)$. Since both digits lie between $0$ and $p-1$, they are equal as integers.

Subtract that common digit and divide by $p$. The remaining equality is an equality of two base-p expansions with one fewer digit. Repeating this argument shows that every pair of corresponding digits agrees. Equivalently, repeated Euclidean division recovers the digits as remainders. The digits are unique up to padding by zeroes. The finite nonnegative-digit representation presupposes $k\ge 0$; a negative integer has no such expansion.

For $1\le j\le p-1$, the identity for binomial coefficientsshows that $p$ divides $j\left(\genfrac{}{}{0ex}{}{p}{j}\right)$. Since $p$ is a prime number and $j$ is not divisible by $p$, cancellation modulo $p$ givesThe binomial theorem consequently gives $(1+x{)}^p\equiv 1+x^p$ as a coefficientwise polynomial modular congruence. Apply the same identity with $x$ replaced by $x^{p^r}$ and use mathematical induction to obtainThis is an iteration of the Frobenius endomorphism in characteristic $p$. Comparing the intermediate coefficients gives the prime-power binomial divisibility result

Write both nonnegative integers $n,k$ in base-p expansions, padding with zero digits to a common length $L$. By the preceding polynomial identity,Expanding the last product with the binomial theorem, each term is obtained by choosing an integer $j_i$ with $0\le j_i\le n_i<p$. Its exponent is ${\sum }_i{j}_i{p}^i$ and its coefficient is ${\prod }_i\left(\genfrac{}{}{0ex}{}{n_i}{j_i}\right)$. Uniqueness of base-p expansions says that the only way this exponent can equal $k$ is to choose $j_i=k_i$ for every $i$.

If some $k_i>n_i$, no such term exists and the coefficient is zero. Otherwise its coefficient is precisely the product below. Comparing the coefficient of $x^k$ proves Lucas theorem:with the convention $\left(\genfrac{}{}{0ex}{}{a}{b}\right)=0$ for $b>a$. This also covers $k>n$, and padding either expansion by further zero digits multiplies the product only by $\left(\genfrac{}{}{0ex}{}{0}{0}\right)=1$.

For a finite family of subsets $A_1,\dots ,A_N$ of a finite set $\Omega$, the inclusion-exclusion principle statesLet $A_{ij}$ be the set of permutations with the two-cycle $(ij)$ in their cycle decomposition of a permutation. Two distinct specified pairs sharing a label cannot both occur, so their intersection is empty. An intersection containing $r$ pairwise disjoint specified pairs fixes those $2r$ labels and leaves $(n-2r)!$ choices for the other labels.

The number of ways to choose $r$ disjoint unordered pairs is $n!/[2^{r}r!(n-2r)!]$: first order the selected labels, then divide by the two orders within each pair, by the $r!$ orders of the pairs, and by the orders of the unused labels. Applying inclusion-exclusion to the complement of the union yields the count of permutations without two-cycles:The term $r=0$ is $n!$. Fixed points and cycles of length at least three are allowed; the restriction concerns two-cycles, not whether a permutation can be expressed as a product of transpositions.

Dividing by $n!$ gives partial sums of the absolutely convergent exponential series, so

A countable set means here a finite set or a countably infinite set, equivalently a set admitting an injection into $\mathbb{N}$. This convention includes the empty set. An infinite set is countably infinite precisely when it can be put in bijection with $\mathbb{N}$.

Let $j:B\to \mathbb{N}$ be an injection witnessing that $B$ is a countable set. The composition $j\circ f:A\to \mathbb{N}$ is an injection, so $A$ is a countable set. This proof includes finite and empty sets.

Choose an injection $j:A\to \mathbb{N}$. For each $b\in B$, its fiber under the surjection $f$ is nonempty, so defineTwo distinct fibers cannot contain the same label $j(a)$, because $j$ is an injection and $f(a)$ has a single value. Thus $h:B\to \mathbb{N}$ is an injection, proving that $B$ is a countable set. Taking the least label avoids any need for a separate choice of one element from each fiber. If $A$ is empty, surjectivity makes $B$ empty as well.

For the unheaded enumeration request, list pairs of positive natural numbers by their sum. An explicit Cantor pairing function isFor $d=m+n-2\ge 0$, the positive integers $n=1,\dots ,d+1$ give the consecutive labels $d(d+1)/2+1,\dots ,(d+1)(d+2)/2$. These blocks are disjoint, consecutive and cover $\mathbb{N}$. Consequently $\pi$ is a bijection from $\mathbb{N}\times \mathbb{N}$ to $\mathbb{N}$, so $\mathbb{N}\times \mathbb{N}$ is countable.

Choose injections $a:X\to \mathbb{N}$ and $b:Y\to \mathbb{N}$. The map $(x,y)\mapsto (a(x),b(y))$ is an injection into the countable set $\mathbb{N}\times \mathbb{N}$. Composing with the Cantor pairing function gives an injection into $\mathbb{N}$. Thus the Cartesian product of two countable sets is countable, including the case of an empty factor.

The integers are countable: $j(z)=2z+1$ for $z\ge 0$ and $j(z)=-2z$ for $z<0$ is an injection $\mathbb{Z}\to \mathbb{N}$. Hence $\mathbb{Z}\times \mathbb{N}$ is a countable set. The map $(a,b)\mapsto a/b$ is a surjection onto the rational numbers, so the image result already proved gives $\mathbb{Q}$ is countable. Unique reduced fractions are not required for this surjection argument.

For the final unheaded geometry request, suppose for contradiction that no two distinct circles in the collection intersect. Restrict to the subcollection ${\mathcal{C}}_0$ of circles tangent to the $x$-axis. Each such nondegenerate circle has a unique tangency point, and the tangency-point map ${\mathcal{C}}_0\to \mathbb{R}$ is a surjection by the hypothesis.

The closed disk of a circle tangent at $(a,0)$ meets the $x$-axis only at $(a,0)$. Two distinct members of ${\mathcal{C}}_0$ cannot have nested disks: if one disk were inside the other, its tangency point would belong to the larger disk, so both tangency points would be equal and both circle boundaries would pass through it. That already contradicts nonintersection. Circles with disjoint boundaries and no nesting have disjoint disks. Thus their open disks are pairwise disjoint.

By the density of the rational numbers, every nonempty open disk contains a point of ${\mathbb{Q}}^2$, which is a countable set. Fix an enumeration of ${\mathbb{Q}}^2$ and assign to each disk the first enumerated point inside it. Disjointness makes this assignment an injection. This is the countability of pairwise disjoint open disks, and proves that ${\mathcal{C}}_0$ is a countable set. Its surjection onto $\mathbb{R}$ would make the real numbers countable, contrary to the Cantor diagonal argument. ThereforeThe proof allows circles on either side of the axis and counts tangential contact as intersection; it does not assume that all circles in the original collection are tangent to the axis.

Outside a spherical Earth the gravitational field is the field of its total mass at the center, by the shell theorem. Since $G{M}_E=g{R}^2$, the inverse-square force on the upward radial trajectory givesThe independent dimensional inputs are $R,V,g$, of dimensions $L,L{T}^{-1},L{T}^{-2}$. A dimensionless monomial in them must be a power of $V^2/(gR)$. Thus dimensional analysis givesFor a finite turning height and time, assume $0<V<\sqrt{2gR}$, equivalently $0<\lambda <2$. This escape velocity restriction is implicit in the requested maximum-height formulas.

The conservation of energy, per unit particle mass, issoThe numerator vanishes at the turning point, givingOn ascent $\dot{z}>0$, and integrating $dt=dz/\dot{z}$ givesThe upper endpoint has an integrable inverse-square-root singularity. Set $z=Hx$, use $H=R\lambda /(2-\lambda )$ and $V^{2}R=(2gR-V^2)H$, and note $R\lambda /V=V/g$. The result isFor small $\lambda$, $F(\lambda )\sim \lambda /2$ and $G(\lambda )\to 1$, recovering $H\sim V^2/(2g)$ and $T\sim V/g$. At $\lambda =2$ the particle escapes marginally and has no finite maximum; for $\lambda >2$ it escapes with nonzero asymptotic speed. The finite-turning formulas must not be extended to those cases.

The Lorentz force in the uniform magnetic field giveswhere the last step is the vector triple product identity. HenceOn the other hand, $|\mathbf{r}\times \mathbf{B}{|}^2=B^2{r}^2-(\mathbf{r}\cdot \mathbf{B}{)}^2$, soThe derivatives cancel, proving the magnetic angular-momentum invariantThe magnetic Lorentz force is perpendicular to velocity, so its power is zero:Thus the kinetic energy is constant.

For the alternative kinetic energy expression, work on an interval where $r>0$ so that the radial unit vector $\mathbf{u}=\mathbf{r}/r$ is defined. Differentiating $\mathbf{u}\cdot \mathbf{u}=1$ once and twice givesSince $\mathbf{v}=\dot{r}\mathbf{u}+r\dot{\mathbf{u}}$, it follows that $\mathbf{u}\cdot \mathbf{v}=\dot{r}$ and $v^2={\dot{r}}^2+r^2|\dot{\mathbf{u}}{|}^2$. Therefore the unit-direction kinetic-energy identity isThis identity holds for any twice differentiable trajectory away from the origin, not only for motion in a magnetic field.

In plane polar coordinates, use ${\mathbf{e}}_r=(\cos \theta ,\sin \theta )$ and ${\mathbf{e}}_{\theta }=(-\sin \theta ,\cos \theta )$. Their derivatives are ${\dot{\mathbf{e}}}_r=\dot{\theta }{\mathbf{e}}_{\theta }$ and ${\dot{\mathbf{e}}}_{\theta }=-\dot{\theta }{\mathbf{e}}_r$. Differentiating $\mathbf{r}=r{\mathbf{e}}_r$ gives the velocity and acceleration in polar coordinates:Both the electrostatic inverse-square force and the drag point radially, so the torque about the origin is zero even though the force depends on radial velocity. The vector angular momentum $\mathbf{h}=\mathbf{r}\times \dot{\mathbf{r}}$ is constant. For $\mathbf{h}\ne 0$, every position lies in the fixed plane perpendicular to it; if $\mathbf{h}=0$, the trajectory is radial and still lies in a plane. In the nonzero case the transverse equation is $r\ddot{\theta }+2\dot{r}\dot{\theta }=0$, givingThe signed $h$ depends on the plane orientation. The stipulated ratio $k/|h|$ requires $h\ne 0$.

Set $u=1/r$ and use primes for differentiation with respect to $\theta$. Then $\dot{\theta }=h{u}^2$, $\dot{r}=-h{u}^{\prime }$ and $\ddot{r}=-h^2{u}^2{u}^{\prime \prime }$. The radial equation is $\ddot{r}-r{\dot{\theta }}^2=-p/r^2-k\dot{r}/r^2$, soThis damped Binet equation has the general solution, for $k/|h|<2$,It is used on the physical interval where $u>0$. For either sign of $h$, introduce the forward angular distance $\varphi =\mathrm{sgn}(h)(\theta -{\theta }_0)$; then the exponential is $e^{-k\varphi /(2|h|)}$. Thus damping acts forward in time for both orientations, not just when $h>0$.

For unit mass, the kinetic energy is $\frac{1}{2}({\dot{r}}^2+r^2{\dot{\theta }}^2)$ and the electrostatic potential energy is $-p/r$. ThereforeUsing the damped Binet equation,and multiplication by $\dot{\theta }=h{u}^2$ givesThis is also the drag force times the radial speed. Energy is nonincreasing in time, strictly decreasing while radial motion occurs; a circular trajectory already has constant energy. The sign of $dE/d\theta$ alone would be misleading for negative $h$.

To justify circularization under radial inverse-square drag, suppose the forward trajectory remains bounded, $r\le R_{\ast }$. Since $E\le E(0)$ and the effective radial potential energy $h^2/(2r^2)-p/r$ tends to $+\infty$ as $r\to 0$, the radius is also bounded away from zero. Velocity then stays bounded, so the solution continues for all forward time without collision. Moreover $\dot{\varphi }=|h|/r^2\ge |h|/R_{\ast }^2$, so $\varphi \to \infty$. The decaying general solution gives $u\to p/h^2$ and $u^{\prime }\to 0$. ConsequentlyThe tangential motion remains, so the limiting orbit is circular. The convergence is asymptotic; boundedness is needed because a physical solution could otherwise reach $u=0$ and escape rather than complete indefinitely many turns.

The example uses $p=h=1$, $k=0.6$ and $u(\theta )=1+0.35e^{-0.3\theta }\cos (\sqrt{0.91}\theta )$, which stays positive. Radial oscillations decay while angular momentum stays fixed.

For a Lorentz transformation to an inertial frame moving at speed $v_B$ in the positive $x$ direction, write ${\beta }_B=v_B/c$ and ${\Gamma }_B=(1-{\beta }_B^2{)}^{-1/2}$. Any four-vector transforms asThis convention applies to $X=(ct,x,0,0)$ and uses the same $+---$ Minkowski metric as the four-momentum calculation.

The definition of proper time gives $d\tau =dt\sqrt{1-u^2/c^2}=dt/\gamma$ for $|u|<c$. Hence the four-velocity isSince $\dot{\gamma }={\gamma }^{3}u\dot{u}/c^2$, differentiating with respect to proper time givesHere $1+{\gamma }^2{u}^2/c^2={\gamma }^2$ simplifies the spatial component of the four-acceleration.

At each event, boost with $v_B=u$ to the instantaneous rest inertial frame. Then $A^{\prime 0}=0$ and $A^{\prime 1}=\gamma {\gamma }^4\dot{u}(1-u^2/c^2)={\gamma }^3\dot{u}$. Thus the signed proper acceleration for one-dimensional motion isThe last equality follows by differentiating $\gamma u$; its magnitude is the usual scalar proper acceleration.

If this signed proper acceleration is constant and the particle starts from rest, integration gives $\gamma u=at$, soIntegrating once more and imposing $x(0)=0$ yields the hyperbolic motion worldlineFor $a=0$ the continuous limiting solution is $x=0$. Finally, the Taylor series of the square root givesThis recovers constant-acceleration Newtonian mechanics at low speed while the exact relativistic speed remains less than $c$.