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

Use the Euclidean algorithm: $23=18+5$, $18=3\cdot 5+3$, $5=3+2$, and $3=2+1$. Back-substitution gives the Bezout identity $1=9\cdot 18-7\cdot 23$. Multiplying by $101$ gives one solution of the linear Diophantine equation, and shifting the coefficients by multiples of $(23,-18)$ reduces it toIndeed, $18\cdot 12+23(-5)=216-115=101$. More generally all solutions are $x=12+23k$, $y=-5-18k$, $k\in \mathbb{Z}$: subtracting this particular solution gives $18(x-12)=-23(y+5)$, and the coprime integers $18,23$ force $23\mid (x-12)$.

Write $x=3+18k$. The second modular congruence becomes $18k\equiv -1(\mathrm{mod}23)$. The Bezout identity above says that $9$ is the inverse of $18$ modulo $23$, so $k\equiv -9\equiv 14(\mathrm{mod}23)$. ThereforeThe checks are $255=18\cdot 14+3=23\cdot 11+2$. The Chinese remainder theorem explains uniqueness modulo $18\cdot 23=414$, since the moduli are coprime integers.

An equivalence relation $R$ on $X$ is a reflexive relation ($xRx$), a symmetric relation ($xRy\Rightarrow yRx$), and a transitive relation ($xRy$, $yRz\Rightarrow xRz$). Its equivalence class at $x$ is $[x{]}_R=\{y\in X:xRy\}$. Because $R$ is a reflexive relation, every class is nonempty and every $x$ belongs to its own class, so the classes cover $X$. If $[x{]}_R$ and $[z{]}_R$ share an element $y$, symmetry and transitivity give $xRz$. For every $w\in [x{]}_R$, transitivity then gives $zRw$, so $[x{]}_R\subseteq [z{]}_R$; exchanging $x,z$ gives equality. Thus distinct classes are disjoint. The equivalence classes form a set partition of $X$. On the empty set, the empty family is the corresponding partition.

The intersection is always an equivalence relation. Both component relations contain $(x,x)$, so $V$ is a reflexive relation. If $xVy$, both relations relate $x$ to $y$, and symmetry in each gives $yVx$. If $xVy$ and $yVz$, transitivity in each component gives both $xRz$ and $xSz$, hence $xVz$. This is the intersection of equivalence relations; the same argument works for any family of such relations.

The union need not be an equivalence relation, because transitivity can mix the two relations. Take $X=\{1,2,3\}$. Let $R$ have equivalence classes $\{1,2\}$ and $\{3\}$, and $S$ have classes $\{1\}$ and $\{2,3\}$. Then $1W2$ and $2W3$, but neither component relates $1$ to $3$, so $1W3$ fails. The union of equivalence relations is reflexive and symmetric; it is precisely transitivity that may fail.

By Newton's third law, the force on the second particle is $-F_{12}$. For $M=m_1+m_2$ and centre of mass $R=(m_1{r}_1+m_2{r}_2)/M$, Newton's second law gives $M\ddot{R}=F_{12}-F_{12}=0$. ThusThe centre moves on a straight line with constant velocity; zero velocity is allowed. For the relative position $r=r_1-r_2$, subtraction of the two equations givesHence the two-body problem reduces to a single particle of reduced mass $\mu$, together with the elementary centre motion. Reconstruct the positions as $r_1=R+(m_2/M)r$, $r_2=R-(m_1/M)r$.

Yes: the two equal masses can follow the same fixed circle in diametrically opposite positions. Put the stationary centre of mass at the circle's center and choose tangential velocities with the same sense of rotation. If the circle has radius $a$, the separation is $2a$ and the mutual gravitational force is directed toward that center, with magnitude $G{m}^2/(4a^2)$. The circular orbit condition is $ma{\omega }^2=G{m}^2/(4a^2)$, so an equal-mass circular binary hasThese initial data maintain the opposite positions and give the same constant angular speed for both particles.

For $0<v<c$, the Lorentz transformation with coincident origins isFor two simultaneous events in $S$, $\Delta t=0$, so $\Delta t^{\prime }=-\gamma v\Delta x/c^2$. Distinct spatial positions therefore generally give different times in the boosted frame: this is relativity of simultaneity.

Choose the emission events at $(t,x)=(0,0)$ and $(0,d)$. After emission, the photon world lines are $x=ct$ and $x=d+ct$. Applying the Lorentz transformation to either givesThus the two photons move at speed $c$ in $S^{\prime }$ on parallel lines whose intercepts differ by $\gamma (1+v/c)d$. Measuring their positions at the same $t^{\prime }$ after both emissions gives the photon separation under a collinear Lorentz boost:This separation is constant. It is not the contracted distance between the stationary sources: the two emission events are not simultaneous in $S^{\prime }$, and one photon has already moved when the other is emitted.

Take $fg=f\circ g$. The assertion can fail on an infinite set. On $X={\mathbb{N}}_0$, set $g(n)=n+1$, $f(0)=0$, and $f(n)=n-1$ for $n\ge 1$. Then $f(g(n))=n$ for every $n$, but $g(f(0))=1\ne 0$. Thus a right inverse need not be a left inverse.

On a finite set it is always true. From $fg={\mathrm{id}}_X$, $g$ is an injection: equality of two $g$-values gives equality after applying $f$. An injective self-map of a finite set is a bijection. Composing $fg={\mathrm{id}}_X$ with $g^{-1}$ shows $f=g^{-1}$, and hence $gf={\mathrm{id}}_X$. This includes the empty set.

It can be false even on a two-element finite set. On $X=\{0,1\}$, let $f$ and $g$ both be the constant map with value $0$. Then $fg=g$, but $f(1)=0\ne 1$. In general the equation says exactly that $f$ fixes the image $g(X)$; it says nothing about other points. If $g$ happens to be a surjection, it does force $f$ to be the identity map, but finiteness alone does not ensure this. The empty set and a singleton have only one self-map, so the assertion is trivially true on those sets.

It can be false even on a two-element finite set. The same constant maps $f=g=0$ on $\{0,1\}$ satisfy $fg=f$, while $g\ne {\mathrm{id}}_X$. Indeed, a constant $f$ makes $fg=f$ for every $g$. If $f$ were an injection, one could cancel it pointwise to conclude $g(x)=x$, but finiteness alone supplies no such hypothesis. As before, the assertion is trivial on the empty set or a singleton.

The final property concerns a pointwise periodic self-map. Such a map is a bijection: each point has a predecessor in its finite cycle, giving surjectivity; if $f(x)=f(y)$, choose a common multiple $N$ of periods of $x,y$ and apply $f^{N-1}$ to get $x=y$. Its finite cycles are therefore disjoint.

If $X$ is finite, choose the least common multiple of the finitely many cycle lengths. This positive integer $N$ gives $f^N={\mathrm{id}}_X$. The empty set satisfies the property with $N=1$.

Conversely, in the usual set theory with choice, every infinite $X$ contains a countably infinite set. Divide such a subset into disjoint finite blocks $B_j$ of sizes $j+1$, $j\ge 1$, make $f$ a cyclic permutation on each block, and fix every other point. Every point returns to itself, but an identity iterate would have to be divisible by every block length $j+1$. No positive integer has that property: take a block longer than that integer. Thus the uniform period criterion for pointwise periodic maps givesThe axiom of choice assumption is stated here because extracting a countably infinite subset of an arbitrary infinite set is not an unrestricted theorem in set theory without choice.

Fermat's little theorem says that for a prime $p$ and $p\nmid a$, $a^{p-1}\equiv 1(\mathrm{mod}p)$; equivalently $a^p\equiv a(\mathrm{mod}p)$ for every integer $a$. The Wilson theorem says $(p-1)!\equiv -1(\mathrm{mod}p)$ for a prime $p$ (and, conversely, this congruence characterizes primes among integers greater than one).

For $p=2$, $x=1$ is a square root of minus one modulo a prime. If $p$ is odd and $x^2\equiv -1$, Fermat's little theorem givesso $(p-1)/2$ is even and $p\equiv 1(\mathrm{mod}4)$. Conversely, put $h=(p-1)/2$. Pairing $j$ with $p-j$ in the factorial gives $(p-1)!\equiv (-1{)}^h(h!{)}^2$. For $p\equiv 1(\mathrm{mod}4)$, $h$ is even, so the Wilson theorem yields $(h!{)}^2\equiv -1$. Thusand in the latter case $x=h!$ supplies a solution.

For the multiplicative order assertion, divide $k$ by $d$: $k=qd+r$, $0\le r<d$. Since $x^d\equiv 1$ and $x^k\equiv 1$, it follows that $x^r\equiv 1$. Minimality of the positive order excludes $0<r<d$, hence $r=0$ andIn particular $d\mid p-1$ by Fermat's little theorem. Negative $k$, if included, are handled by the same division using the modular inverse of $x$.

A Fermat number in the paper has $n\ge 1$. If a prime $p$ divides $F_n=2^{2^n}+1$, it is odd and $2^{2^n}\equiv -1(\mathrm{mod}p)$. Squaring gives $2^{2^{n+1}}\equiv 1$, so the order $d$ divides $2^{n+1}$. It does not divide $2^n$, since $-1\ne 1$ modulo an odd prime. Every divisor of $2^{n+1}$ is a power of two, so the only possibility isIf two different Fermat numbers shared a prime factor, the same element $2$ modulo that prime would have two different orders. This is impossible, proving pairwise coprimality. Also $2^{n+1}\mid p-1$, so for $n\ge 1$ every such prime is $1$ modulo $4$. No prime $3$ modulo $4$ can occur.

A prime $1$ modulo $4$ need not occur: take $p=13$. It is prime, $2^6=64\equiv -1(\mathrm{mod}13)$, and $2^4\equiv 3\ne 1$. Since the order divides $12$, the first congruence excludes every divisor of $6$ and the second excludes $4$; hence the order is $12$. This is not a power of two, so $13$ is not a prime divisor of a Fermat number. The index restriction matters: the conventional extra number $F_0=3$ is outside the paper's positive-$n$ family.

If $q=\sqrt{2}+\sqrt{3}$ were a rational number, then $q^2=5+2\sqrt{6}$ would make $\sqrt{6}$ rational. Write $\sqrt{6}=a/b$ in lowest terms. Then $a^2=6b^2$, which is impossible by unique factorization: the exponent of the prime $2$ is even on the left and odd on the right. Therefore

The exponential function series gives Euler's number $e={\sum }_{k=0}^{\infty }1/k!$. Suppose $e=a/b$ with integers $a,b$ and $b>0$. Choose $n\ge \max (b,2)$. Since $b$ divides $n!$, the numberis an integer. But its positive tail satisfiesThe inequality is strict because the factors after the first exceed $n+1$ when $j\ge 2$. No integer lies strictly between zero and one. This proves the irrationality of e:

For $P(x)=x^3+4x-7$, the derivative $P^{\prime }(x)=3x^2+4$ is positive everywhere, so the mean value theorem makes $P$ strictly increasing. Since a polynomial is a continuous function, the intermediate value theorem and the values $P(1)=-2$, $P(2)=9$ locate its unique real root in $(1,2)$. By the rational root theorem, a rational root of a monic integer polynomial must be an integer. There is no integer in $(1,2)$, so the unique real root is an irrational number. The denominator part of that theorem also follows directly: if $a/b$ in lowest terms were a root, $a^3+4a{b}^2-7b^3=0$ would force $b\mid a^3$, hence $b=1$.

If ${\log }_{2}3=a/b$ were a rational number, choose positive integers $a,b$ because ${\log }_{2}3>0$. Exponentiation gives $2^a=3^b$, but the left side is even and the right side is odd. ThusThis is the basic irrational logarithm criterion: a rational logarithm would force positive integer powers of its base and argument to coincide.

First apply the Cantor theorem by diagonalization. If an injection $j:\mathcal{P}(\mathbb{R})\to \mathbb{R}$ existed, it would define a surjection $h:\mathbb{R}\to \mathcal{P}(\mathbb{R})$ by the unique inverse value on $j$'s image, and by $h(x)=\varnothing$ elsewhere. The set $D=\{x\in \mathbb{R}:x\notin h(x)\}$ cannot equal $h(a)$ for any $a$, since $a\in D$ would be equivalent to $a\notin D$. This contradicts surjectivity. There is no injection from the power set of the real line into the real line.

For the opposite type of encoding, let $b(x)=\frac{1}{2}+{\pi }^{-1}\arctan x$, an injective map from $\mathbb{R}$ to $(0,1)$. Give $b(x)$ its canonical binary expansion, choosing the terminating expansion with trailing zeros whenever two expansions exist. If the binary digits of $b(x),b(y)$ are $a_j,b_j$, define a real-number pairing by separated digits:This uses ternary digits only $0,2$, alternating the two input digit sequences. If two outputs first differ at ternary position $k$, that difference has magnitude $2\cdot 3^{-k}$, while every later digit together contributes at most ${\sum }_{j>k}2\cdot 3^{-j}=3^{-k}$. Their outputs therefore differ. The digits recover both binary sequences, hence both inputs. Neither output endpoint $0$ nor $1$ occurs because the input numbers lie strictly between zero and one. Thus $H$ is an injection from ${\mathbb{R}}^2$ into $(0,1)\subset \mathbb{R}$. The ternary construction avoids an unjustified decimal-interleaving argument at ambiguous expansions.

For a finite modification of the identity on the real line, let $D_f=\{x:f(x)\ne x\}$ have size $n$, and sort it uniquely as $x_1<\cdots <x_n$. Its finite record is $(x_1,f(x_1),\dots ,x_n,f(x_n))$. It determines $f$ completely, with the identity used outside the recorded points. Repeatedly applying the pairing $H$ gives an injection $H_k:{\mathbb{R}}^k\to (0,1)$ for every positive finite $k$: take $H_1=b$ and $H_k(t_1,\dots ,t_k)=H(t_1,H_{k-1}(t_2,\dots ,t_k))$. Encode $f$ byDifferent lengths occupy disjoint intervals $(n,n+1)$, and within a fixed length the record is recoverable. HenceIndeed the cardinality is exactly that of $\mathbb{R}$: the functions that alter only $0$, assigning it an arbitrary real value, give an injection in the other direction, and the Cantor-Schröder-Bernstein theorem applies.

A central force has no angular component, so the supplied polar acceleration formula and Newton's second law give $d(r^2\dot{\theta })/dt=0$. Thus $l=r^2\dot{\theta }$ is the conserved specific angular momentum. For a nonradial orbit, $l\ne 0$ allows $\theta$ to be used as a parameter. With $u=1/r$ and a prime denoting $d/d\theta$,Also $r{\dot{\theta }}^2=l^2{u}^3$. The radial equation $\ddot{r}-r{\dot{\theta }}^2=-f(r)$ therefore becomes the Binet equationFor a purely radial trajectory $l=0$, the angular parameter is unavailable, and one instead uses the direct radial equation. The orbit in part (b) is nonradial.

Set $\theta =0$ initially and choose its positive sense to agree with the initial tangential motion. The inward radial component is $\dot{r}(0)=-4\cos (\pi /3)=-2$, while the tangential speed is $4\sin (\pi /3)=2\sqrt{3}$. HenceSubstitution in the Binet equation gives $12(u^{\prime \prime }+u)=3+9u$, or $u^{\prime \prime }+u/4=1/4$. This is an orbit equation for combined inverse-square and inverse-cube attraction. Solving the constant-coefficient equation and applying both initial conditions givesOn $0\le \theta \le 2\pi$, the sine is nonnegative, so $r$ stays finite and positive. At $\theta =2\pi$, $u=1$, hence $r=1$ and the particle is back at its original spatial position after one revolution. But $u^{\prime }(2\pi )=-1/\sqrt{3}$, so its radial velocity is now $+2$, rather than the original $-2$. The return is not a periodic return in position and velocity.

After that revolution, the first zero of $u$ is at $\theta =8\pi /3$, where $\sin (\theta /2)=-\sqrt{3}/2$. The physical branch therefore has $r\to \infty$ as $\theta \uparrow 8\pi /3$; it must not be continued into negative $u$. Since $dt/d\theta =1/(l{u}^2)$ and $u$ has a simple zero, reaching infinity takes infinite time. As a check, the specific potential energy is $\Phi (r)=-3/r-9/(2r^2)$ and the conserved energy per unit mass is $4^2/2+\Phi (1)=1/2$, giving escape speed $1$ at infinity, also obtained from $-l{u}^{\prime }(8\pi /3)=1$.

Apply the rotating-frame derivative formula first to $r$, then to $v^{\prime }=[dr/dt{]}_{S^{\prime }}$. Since the angular velocity is constant in either frame,The two apparent forces in the rotating equation are the Coriolis force and the centrifugal acceleration multiplied by mass. ThusSet ${\varphi }_{\mathrm{eff}}=\varphi -\frac{m}{2}|\omega \times r{|}^2$. The supplied gradient identity gives $\nabla {\varphi }_{\mathrm{eff}}=\nabla \varphi +m\omega \times (\omega \times r)$. Taking the scalar product with $v^{\prime }$ removes $G$, since it is orthogonal to $v^{\prime }$, and removes the Coriolis force. Therefore the energy balance in a uniformly rotating frame isThe displayed quantity is conserved when the potential is stationary in the rotating coordinates. This includes a static inertial potential invariant under rotations about the chosen axis, such as vertical gravity in part (b). If the word conservative only means a time-independent inertial potential, that extra rotational invariance is needed; a conservative force alone does not imply the claimed conservation.

For an explicit counterexample to that unrestricted interpretation, take unit mass, an inertial force $F=e_x$, $\varphi =-x$, no $G$, rotation $\omega =\omega e_z$, and inertial trajectory $r(t)=(t^2/2,1,0)$ with initial velocity zero. It satisfies Newton's second law. Substituting $v^{\prime }=\dot{r}-\omega \times r$ into the proposed energy gives $E=\omega t$, which is not constant for nonzero rotation. The qualified conservation law above is the one used for the hoop.

In the rotating-hoop bead problem, use a signed angle in the hoop plane from the downward vertical. The gravitational potential energy is $-mga\cos \theta$, the rotating-frame speed is $a\dot{\theta }$, and the distance from the rotation axis is $a\sin \theta$. The centrifugal potential givesGravity is stationary in these rotating coordinates, and the frictionless constraint does no work. Projecting the rotating equation along the hoop, or differentiating its effective potential in the one-dimensional Euler-Lagrange equation, givesIf ${\omega }^2>g/a$, the two off-axis positions areTheir unsigned angle to the downward vertical is the same; they lie on opposite sides of the hoop. The second derivative of the effective potential there is $m{\omega }^2{a}^2{\sin }^2{\theta }_0>0$. Equivalently, writing $\theta ={\theta }_0+\delta$ gives to first orderThe same holds at $-{\theta }_0$. Thus both equilibria are stable, with small-oscillation angular frequency $|\omega |\sin {\theta }_0$.

The parallel axis theorem says that for an axis through a body's centre of mass and a parallel axis at perpendicular distance $d$,where $M$ is the total mass. The displacement is the distance between the two parallel axes; neither axis may be arbitrary in place of the center-of-mass axis. Expanding the squared distances of mass elements gives this formula, since the cross term integrates to zero at the centre of mass.

The moment of inertia of the uniform disc about its central perpendicular axis isThe parallel axis theorem gives $I_A=I_O+m{a}^2=3m{a}^2/2$. For angle $\beta$ from the downward resting position, the gravitational torque is $-mga\sin \beta$, so $I_A\ddot{\beta }=-mga\sin \beta$. Linearizing at $\beta =0$ gives $\ddot{\beta }+(2g/(3a))\beta =0$. Thus the uniform disc pivoted at its rim is a physical pendulum with period

Measure a signed angle $\theta$ from the upward radius $A\to O$ in the direction of falling. With $I_A=3m{a}^2/2$, gravitational torque givesThere is an idealization in the release condition: exactly upright and exactly at rest is an unstable equilibrium, so the exact ideal solution stays there. Uniqueness of this smooth equation with $\theta (0)=\dot{\theta }(0)=0$ prevents spontaneous departure. The usual falling calculation means an infinitesimal disturbance, with its energy tending to that of the upright rest state. For that limiting separatrix motion, conservation of mechanical energy givesOn the branch with increasing angle, $\dot{\theta }=\sqrt{8g/(3a)}\sin (\theta /2)$ for $0<\theta <2\pi$; the opposite branch has the opposite angular velocity. The nontrivial limiting motion approaches the upright position only as $t\to -\infty$, because $dt/d\theta$ has a logarithmically divergent integral near zero.

Let $e_r$ point from $A$ toward $O$, and $e_{\theta }$ in the direction of increasing angle, so $e_r=\sin \theta e_x+\cos \theta e_z$ and $e_{\theta }=\cos \theta e_x-\sin \theta e_z$. The centre of mass acceleration on the limiting falling branch isGravity has components $-mg\cos \theta e_r+mg\sin \theta e_{\theta }$. Applying Newton's second law to the whole disc givesThe signed component parallel to the radius, positive from $A$ toward $O$, is the required $mg(7\cos \theta -4)/3$. This same radial formula is consistent at the exact stationary upright state, where $\theta =0$, $a_O=0$, and $R=mg{e}_z$; nonzero falling angles require the limiting-release interpretation just stated.

Use metric signature $(+---)$, as required by the sign of the scalar product in this question. For a massive particle, the four-momentum isFor a photon of positive frequency $\nu$ and direction $e$, the Planck constant gives $E=h\nu$ andA future-pointing timelike four-vector $P=(P^0,p)$ has $P^0>|p|$ and $P^0>0$ in this signature. The ordinary Euclidean Cauchy-Schwarz inequality yieldsThis is stronger than the requested nonnegative inequality. For an electron and a positron of rest mass $m>0$, their future-pointing timelike four-momenta have $P_1^2=P_2^2=m^2{c}^2$. Thuswhich cannot equal the null norm of a single photon. Four-momentum conservation forbids spontaneous photon decay into an electron-positron pair in vacuum. An external body or field able to exchange momentum would be a different system.

For $u>0$, take the initial electron direction as the longitudinal axis and put $\beta =u/c$. Incoming four-momentum conservation givesThe transverse components must cancel. In the noncollinear case the two transverse directions are opposite, and ${\nu }_1\sin {\theta }_1={\nu }_2\sin {\theta }_2$. Hence the ratio of longitudinal momentum times $c$ to energy isWriting $s=({\theta }_1+{\theta }_2)/2$ and $d=({\theta }_1-{\theta }_2)/2$, the last ratio is $\cos s/\cos d$. It also equals $(1+\cos ({\theta }_1+{\theta }_2))/(\cos {\theta }_1+\cos {\theta }_2)$ whenever that denominator is nonzero. Since ${\gamma }^2{\beta }^2={\gamma }^2-1$, the angular relation for two-photon electron-positron annihilation isThe positive root follows from $u>0$. For noncollinear emission the positive momentum-to-energy ratio ensures $\cos s>0$, and $|d|<\pi /2$ ensures the stated denominator is positive.

The printed quotient needs a qualification for exactly collinear photons. The allowed configuration ${\theta }_1=0$, ${\theta }_2=\pi$ has positive frequencieswhich obey both conservation equations, but the printed left side is $0/0$. Thus the quotient holds for noncollinear angles, or as its appropriate noncollinear limit. The undivided identityremains true in the collinear case, where both sides vanish. The limit $u=0$ similarly requires care because the initial direction is then undefined and the photons are antiparallel.