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

Since $4^{-1}\equiv 16(\mathrm{mod}21)$ and $2^{-1}\equiv 23(\mathrm{mod}45)$, the two linear congruences reduce toWrite $x=16+21k$. The second congruence becomesor $7k\equiv 3(\mathrm{mod}15)$ after division by three. Since $7^{-1}\equiv 13(\mathrm{mod}15)$, $k\equiv 9(\mathrm{mod}15)$. The Chinese remainder theorem therefore gives the complete familyThe modulus is $\mathrm{lcm}(21,45)=315$ because the compatibility condition modulo their greatest common divisor is satisfied.

The first series is telescoping, sinceIts $N$th partial sum is $1-1/(N+1)$, soa rational number.

The second series converges absolutely, for example by the ratio test, and is the odd part of the exponential series:This value is irrational. Indeed, if $a=\sinh 1$ were algebraic, then $e$ would satisfymaking $e$ algebraic over the algebraic numbers and hence algebraic, contrary to the Hermite theorem on the transcendence of e. Thus the second sum is in fact transcendental.

During a short interval $dt$, let the rocket's mass change by $dm<0$ and its speed by $dv$. The expelled mass $-dm$ has inertial-frame speed $v-u$ to first order. Conservation of linear momentum, including the impulse $Fdt$, givesDiscarding the second-order product $dmdv$ leavesand hence the Tsiolkovsky rocket equation

In deep space $F=0$, so $dv=-udm/m$. Burning from initial mass $m_0$ to $m_0/2$ increases the speed by

Measure displacement downward from the release point and take downward speed $v\ge 0$. Newton's second law with quadratic drag givesWritingseparation of variables gives the terminal velocity solutionThe distance fallen by time $t$ is thereforeSetting $y(t)=h$ and solving for $t$ yields

Fermat's little theorem states that for a prime $p$ and integer $a$,if $p\nmid a$, equivalently $a^{p-1}\equiv 1(\mathrm{mod}p)$. For the latter form, multiplication by $a$ permutes the nonzero residue classes modulo $p$. Multiplying the congruences $a,2a,\dots ,(p-1)a$ and cancelling $(p-1)!$ gives $a^{p-1}\equiv 1$. The first form also covers $p\mid a$.

Since $803=50\cdot 16+3$, the theorem gives

We prove both identities by mathematical induction. They hold at $n=1$. Assume they hold at $n$. Using $F_{n-1}=F_{n+1}-F_n$,Adding this to $F_{2n+1}=F_n^2+F_{n+1}^2$ and using $F_{n+2}=F_n+F_{n+1}$ givesThese are precisely the two assertions with $n$ replaced by $n+1$, completing the induction.

True. Write the odd integer as $m=2n+1$. The identity from part (b) and $p\mid F_m$ giveConsecutive Fibonacci numbers are coprime, so $F_{n+1}$ is invertible modulo $p$. HenceThus $-1$ is a quadratic residue modulo the odd prime $p$, which occurs exactly when $\boxed{p\equiv 1(\mathrm{mod}4)}$.

This statement can be false. For example, $m=10$ is even andbut the odd prime divisor $p=5$ satisfies $p\equiv 1(\mathrm{mod}4)$, rather than $3(\mathrm{mod}4)$.

The inclusion-exclusion principle states that for finite sets $A_1,\dots ,A_k$,For each prime $p\mid n$, exclude pairs whose two coordinates are divisible by $p$. For a set of distinct prime divisors $p_1,\dots ,p_j$, exactly $n^2/(p_1\cdots p_j{)}^2$ pairs have both coordinates divisible by their product. Inclusion-exclusion therefore gives

The condition $\gcd (a,b,n)=1$ says that the ideal of $\mathbb{Z}$ generated by $a,b,n$ is all of $\mathbb{Z}$. The multi-integer Bezout identity therefore supplies integers $r,s,t$ such thatEquivalently, first apply Bézout's identity to $a,b$ and then to $\gcd (a,b),n$.

Assume $ad\equiv bc(\mathrm{mod}n)$ and choose $r,s$ as in part (b). Put $\lambda =rc+sd$. Multiplying $ra+sb\equiv 1$ by $c$ and using $ad\equiv bc$ givesSimilarly, multiplication by $d$ gives $\lambda b\equiv d(\mathrm{mod}n)$.

Moreover, $\lambda$ is a unit modulo n: if a prime divided both $\lambda$ and $n$, the two congruences would make it divide $c,d,n$, contrary to $(c,d)\in Y$. Thus $R$ means precisely that two pairs differ by multiplication by a unit modulo $n$. Reflexivity, symmetry using ${\lambda }^{-1}$, and transitivity using products of units now show that $R$ is an equivalence relation.

The class of $(1,1)$ isso its size is Euler's totient functionThe unit group acts freely on every pair in $Y$: if $\lambda a\equiv a$ and $\lambda b\equiv b$, multiplying the Bezout identity by $\lambda -1$ gives $\lambda \equiv 1(\mathrm{mod}n)$. Hence every equivalence class has size $\phi (n)$. Dividing the answer from part (a) by this size gives

If $f$ is injective and $x\in f^{-1}(f(A))$, then $f(x)=f(a)$ for some $a\in A$, so injectivity gives $x=a\in A$. The reverse inclusion always holds; hence $f^{-1}(f(A))=A$.

Conversely, if (ii) holds and $f(x)=f(y)$, then $y\in f^{-1}(f(\{x\}))=\{x\}$, so $x=y$. Thus (i) and (ii) are equivalent.

Assume $f$ is injective. The inclusion $f(A\cap B)\subseteq f(A)\cap f(B)$ holds for every function. If $y$ belongs to the right-hand side, write $y=f(a)=f(b)$ with $a\in A$ and $b\in B$. Injectivity gives $a=b\in A\cap B$, proving equality.

Conversely, suppose (iii) holds and $f(x)=f(y)$. If $x\ne y$, take $A=\{x\}$ and $B=\{y\}$. Then $f(A)\cap f(B)$ is nonempty whereas $f(A\cap B)=f(\varnothing )=\varnothing$, a contradiction. Hence $f$ is injective.

Parts (i) and (ii) prove (i)$\iff$(ii), while the two directions in part (ii) prove (i)$\iff$(iii). Therefore all three statements are equivalent.

DefineCertainly $f(B)\subseteq B$. If $y\in B$, then $y\in f(X)$ and has a unique predecessor $x$ because $f$ is injective. For every $n$, writing $y=f^{n+1}(z)$ and using uniqueness gives $x=f^n(z)$; hence $x\in B$ and $y\in f(B)$. Thus $f(B)=B$.

If $f(a)\in B$, its unique predecessor must lie in $B$, so $a\in B$; consequently $f(A)\subseteq A$. If a point belonged to every $f^n(A)$ for $n\ge 1$, it would belong to $B$ and also to $f(A)\subseteq A$, which is impossible. Therefore

A set is countable if it is finite or admits an injection into the natural numbers; equivalently, its elements can be listed by a finite list or a sequence.

The product of two countable sets is countable: after choosing enumerations, its elements are indexed by pairs $(m,n)\in {\mathbb{N}}^2$, and these pairs can be listed diagonally. Thus an injection $X\to A\times B$ followed by an injection $A\times B\to \mathbb{N}$ proves that $X$ is countable.

The integers are listed as $0,1,-1,2,-2,\dots$, so $\mathbb{Z}$ is countable. Every rational number is represented by a pair $(p,q)\in \mathbb{Z}\times {\mathbb{N}}_{>0}$, so $\mathbb{Q}$ is countable as the image of a countable set.

Finally, if $A_0,A_1,\dots$ are countable, choose listings $A_n=\{a_{n,0},a_{n,1},\dots \}$, allowing repetitions for finite sets. The diagonal listing of the pairs $(n,m)$ lists every $a_{n,m}$, proving that a countable union of countable sets is countable.

Fix a positive rational radius $r$. Distinct disjoint circles of radius $r$ have centers more than $2r$ apart, so their open interior disks are pairwise disjoint. Each such disk contains a point of the countable dense set ${\mathbb{Q}}^2$. Fix an enumeration of ${\mathbb{Q}}^2$ and assign to each disk the first rational point it contains. Disjointness makes this assignment injective, so there are only countably many circles of radius $r$.

The positive rational numbers are countable. Taking the countable union of countable sets over all rational radii proves that the whole collection is countable.

The conclusion remains true, even though the scaling factor and hence the radius may now be arbitrary. At the point where its handle meets its circle, every lollipop contains a simple triod: take a short arc of the circle in each direction together with a short segment of the handle. Pairwise disjoint lollipops therefore contain pairwise disjoint simple triods. The Moore triod theorem says that every such family in the plane is countable, so

The rod imposes a mechanical constraint, and its force is perpendicular to the wrecking ball's instantaneous velocity, so it does no work. In the constant parallel Newtonian gravitational field, the ball falls through the vertical distance $l-l\cos {\theta }_0$. Conservation of energy between $B$ and $W$ therefore givesand hence

Let $C$ be the centre of the Earth and let $M$ be its mass. Since $CW=R$ and $CS=R+l$, the law of cosines in triangle $CSB$ gives the ball's initial distance from $C$ asThe surface value of the Newtonian gravitational field satisfies $g=GM/R^2$. Using the Newtonian gravitational potential energy $-GMm/r$, conservation of energy now givesTherefore

Put $ϵ=l/R$ and $a=1-\cos {\theta }_0$. ThenThe binomial series givessoSince $v_1^2=2gRaϵ$, a second binomial series expansion yieldsThus the constants in the stated Big O notation expansion are

The Lorentz force and Newton's second law giveWriting $\Omega =qB/m$, the component equations areThe initial velocity therefore givesand integration with the initial position givesThis is helical motion in a uniform magnetic field: a helix of radius $v/\Omega$ around the line $x=1+v/\Omega$, $y=0$, with its axis parallel to the magnetic field.

The three fixed charges are related by rotations through $2\pi /3$ about the origin. Their three Coulomb's law forces on a charge placed at the origin have equal magnitudes and directions separated by $2\pi /3$, so their vector sum vanishes. Thusis an equilibrium point.

Let $\rho =a/\sqrt{3}$ be the distance from the origin to each fixed charge, and denote their position vectors by ${\mathbf{R}}_j$. For a small planar displacement $\mathbf{r}$, the Taylor expansioncan be summed using the threefold symmetry relationsThe electric potential due to the fixed charges is consequentlyThe moving charge has electrostatic potential energy of point charges $U=q\Phi$. Because the quadratic coefficient is positive, the origin is a strict local minimum of $U$, and the equilibrium is stable.

Taking the gradient of the quadratic potential energy found in part (ii) resolves the linearized force into identical $x$ and $y$ components:Each component therefore performs simple harmonic motion withThus the angular frequency is

By Newton's second law, force is mass times acceleration. Hence its dimensions are

The electric field is force per unit electric charge, so

Write $E=|\mathbf{E}|$ and $\hat{\mathbf{E}}=\mathbf{E}/E$. The constant electric force gives momentumCombining $\mathbf{p}=\gamma m\dot{\mathbf{x}}$ with the relativistic energy-momentum relation givesThe dimensional analysis from part (a) confirms that $qEt$ has the dimensions of momentum, so $qEt/(mc)$ is dimensionless and the expression has the dimensions of velocity.

The speed increases monotonically from zero and approaches the speed of light asymptotically:Integrating in the direction of the field givesAt small times, the Taylor expansion of the square root gives the nonrelativistic limitwhich is motion from rest with the constant acceleration $q\mathbf{E}/m$.

At time $t_0$, the accelerated proton has momentum $p=qE{t}_0$ and, by the relativistic energy-momentum relation, energyThe incident Cosmic microwave background photon adds energy $E_{\gamma }$. Since the final state contains only the Delta-plus baryon, conservation of relativistic energy gives its laboratory-frame Lorentz factorIts rest-frame decay time $t_{\Delta }$ is a proper time, so time dilation gives the laboratory decay time

Let $\{{\mathbf{e}}_i(t)\}$ be an orthonormal basis fixed in $S^{\prime }$ and write $\mathbf{a}=a_i{\mathbf{e}}_i$. A basis vector rotating with angular velocity $\mathbf{\omega }$ satisfiesDifferentiating the components and the basis vectors in $S$ therefore gives the rotating-frame derivative formula

Apply part (a) first to the position $\mathbf{r}$:Applying it again to both terms on the right giveswhere $(\dot{\mathbf{\omega }}{)}_S=(\dot{\mathbf{\omega }}{)}_{S^{\prime }}$ because $\mathbf{\omega }\times \mathbf{\omega }=0$. Substituting the first formula into the last term produces

In the Earth-fixed rotating reference frame, the sideways apparent force is the Coriolis acceleration multiplied by the ski-doo's mass:At the South Pole, $\mathbf{\omega }$ is vertical and antiparallel to the local outward normal, while $\mathbf{v}$ is horizontal, soThe force points to the left of the direction of travel, which is westward when the ski-doo is moving north after crossing the pole.