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

The Euclidean algorithm givesThus the greatest common divisor is $d=7$. The extended Euclidean algorithm reverses these divisions:This supplies the Bezout identity with $x=8$, $y=-11$.

To obtain all solutions of a linear Diophantine equation, subtract this particular solution from any other and divide by $7$. The result is $29(x-8)+21(y+11)=0$. Since $29$ and $21$ are coprime integers, $21$ divides $x-8$, givingEvery displayed pair satisfies the original linear Diophantine equation, so the parametrization is exhaustive.

For the modular arithmetic calculation, $21\cdot 18=378\equiv 1(\mathrm{mod}29)$, so $18$ is the modular inverse of $21$. Multiplication gives $n\equiv 25\cdot 18\equiv 15(\mathrm{mod}29)$. The admissible integers are $15+29t$ for $0\le t\le 68$, ending at $1987$; the next is $2016$. There are $\boxed{69}$ such integers.

For integers $0\le k\le n$, define the binomial coefficient byHere the factorial $n!$ is the product of the positive integers up to $n$. This also counts the $k$-element subsets of an $n$-element set: an ordered choice has $n!/(n-k)!$ possibilities, and each subset is ordered in $k!$ ways.

Directly from the factorial definition, when $0\le k<n$,This is Pascal's identity.

The required hockey-stick identity follows by mathematical induction on $m$, with $n\ge 0$ fixed. For $m=0$, both sides are $1$. If it holds at $m$, adding the next binomial coefficient and using Pascal's identity givesTherefore for every $n,m\ge 0$,

In classical charged particle in a uniform magnetic field motion, the Lorentz force and Newton's second law giveAssume $\mathbf{B}\ne 0$ and choose an orthonormal coordinate system with $\mathbf{B}=B{\mathbf{e}}_z$, $B=|\mathbf{B}|$. Write $\Omega =qB/m$, retaining the sign of the electric charge. The velocity equations areThus the parallel velocity is constant, and the perpendicular velocity rotates at constant angular frequency. Choosing the time origin and perpendicular axes conveniently givesIntegrating the velocity, one obtainsThe first two coordinates describe a circle of radius $m{v}_{\perp }/(|q|B)$, while the third advances uniformly. This is helical motion in a uniform magnetic field: the helix has axis parallel to $\mathbf{B}$ through the guiding centre. Its cyclotron frequency isand its signed angular velocity vector about that axis is $-q\mathbf{B}/m$. The minus sign follows from the ordering $\mathbf{v}\times \mathbf{B}$ in the Lorentz force. The helix degenerates to a circle when $v_{\parallel }=0$ and to a straight line when $v_{\perp }=0$. If $q=0$ or $B=0$, there is only straight-line motion. In a relativistic extension with fixed Lorentz factor $\gamma$, the frequency becomes $|q|B/(\gamma m)$; the classical result above uses $m\mathbf{v}$ as momentum.

A four-vector is a collection of four components $A^{\mu }=(A^0,\mathbf{A})$ that transforms by the same Lorentz transformation as $(ct,\mathbf{x})$. Use the metric signature $(-,+,+,+)$. The Lorentzian inner product isA nonzero four-vector is a timelike vector, null vector or spacelike vector according as $A\cdot A$ is negative, zero or positive. Reversing the metric signature reverses the signs used to name these three classes, without changing their geometric meaning.

For a frame moving at speed $v$ along the positive $x$ axis, write $\beta =v/c$ and use the Lorentz factor $\gamma =(1-{\beta }^2{)}^{-1/2}$. The component Lorentz transformation isExpanding the first two squares givesThe other two components are unchanged, so $A^{\prime }\cdot A^{\prime }=A\cdot A$. Consequently a timelike vector remains timelike under a Lorentz transformation.

For a nonzero null vector, $|\mathbf{A}|=|A^0|$ and $A^0\ne 0$. Set $a=A^0$ and $\hat{\mathbf{n}}=\mathbf{A}/a$. Then $|\hat{\mathbf{n}}|=1$ and $A=a(1,\hat{\mathbf{n}})$. If the zero four-vector is included among null vectors, take $a=0$ and any unit vector.

For two future-pointing null vectors, write $A=a(1,\hat{\mathbf{n}})$ and $B=b(1,\hat{\mathbf{m}})$ with $a,b>0$. The sum of future-pointing null vectors satisfiesbecause the ordinary inner product of two unit vectors is at most one. The sum is null if their spatial directions coincide, and timelike otherwise. Its positive time component makes the sum nonzero and future-pointing.

A real sequence $(x_n)$ has limit of a sequence $x$ whenA series ${\sum }_{n\ge 1}{x}_n$ is a convergent series with sum $s$ when its partial sums $S_N={\sum }_{n=1}^N{x}_n$ have limit of a sequence $s$.

For the first comparison test for series, either of the two allowed bounds implies $0<x_n\le a_n+b_n$. HenceThe partial sums form a monotone bounded sequence, so they converge. The series $\sum x_n$ is convergent.

For the exponent $2$, use $1/n^2\le 1/[n(n-1)]=1/(n-1)-1/n$ for $n\ge 2$. The resulting telescoping series bounds every partial sum by $2$, proving that the series converges by the monotone bounded sequence property. To prove divergence of the harmonic series, group the terms with $2^j<n\le 2^{j+1}$: their sum is at least $2^j/2^{j+1}=1/2$. Thus its partial sums are unbounded. If $\alpha \le 1$, then $n^{-\alpha }\ge n^{-1}$, so the comparison test for series proves

For the weighted square assumption, the finite-dimensional Cauchy-Schwarz inequality gives, for every $N$,Again the positive partial sums form a monotone bounded sequence. This is the weighted square roots of a summable sequence argument, with $a_n=n^2{x}_n^2$. The weighted square condition implies $\sum x_n<\infty$.

The converse is false. Take $x_n=n^{-3/2}$. Each block $2^j\le n<2^{j+1}$ contributes at most $2^j{2}^{-3j/2}=2^{-j/2}$, and the resulting geometric series converges. But $n^2{x}_n^2=1/n$, whose harmonic series diverges. This proves the counterexample without assuming the full P-series criterion.

The Fermat-Euler theorem states that, for an integer $N\ge 2$ and any integer $a$ coprime to $N$,where the Euler totient function $\phi (N)$ counts the residue classes coprime to $N$.

Let $r_1,\dots ,r_{\phi (N)}$ be representatives of these residue classes. Multiplication by $a$ gives a permutation of them: each $a{r}_i$ remains coprime to $N$, and $a{r}_i\equiv a{r}_j$ implies $r_i\equiv r_j$ by cancellation using the modular inverse of $a$. Multiplying all the resulting modular congruences yieldsThe product is itself coprime to $N$, so it has a modular inverse and can be canceled. This proves the Fermat-Euler theorem. For $N=1$, the congruence is trivial; no separate argument is needed.

For the odd prime $p$, the Fermat-Euler theorem gives $x^{p-1}\equiv 1(\mathrm{mod}p)$. Therefore the residue class $z=x^{(p-1)/2}$ obeys $(z-1)(z+1)\equiv 0(\mathrm{mod}p)$. Since a prime number dividing a product divides one of its factors,If $x$ is a quadratic residue, choose $y$ with $y^2\equiv x(\mathrm{mod}p)$. Then $y$ is nonzero modulo $p$, and Fermat's little theorem givesThis proves the quadratic residue direction of Euler's criterion.

Suppose $x$ is a quadratic nonresidue. On the nonzero residue classes modulo $p$, define the involutionIt is an involution because $T(T(a))=a$. A fixed point would satisfy $a^2=x$, which is excluded by the quadratic nonresidue hypothesis. Thus it partitions the $p-1$ classes into $(p-1)/2$ disjoint pairs $\{a,x{a}^{-1}\}$, each with product $x$. ConsequentlyNow evaluate the same product by pairing every class with its own modular inverse. The only classes equal to their modular inverses solve $(a-1)(a+1)=0$ and hence are $1$ and $-1$. All other pairs have product one. The complete product is therefore $-1$, soTogether with the preceding part, this is Euler's criterion; the pairing argument establishes the converse without assuming it.

Fermat's little theorem reduces the exponent modulo $22$ because $23$ is a prime number and $5$ is coprime to it. Compute $5^2\equiv 3(\mathrm{mod}22)$, then $5^4\equiv 9(\mathrm{mod}22)$ and $5^5\equiv 45\equiv 1(\mathrm{mod}22)$. Thus $5^5=22k+1$ for an integer $k$, andThe exponent is $5^5=3125$, rather than an iterated left-associated power.

A set is a countable set if it admits an injective function into the natural numbers; this includes finite sets and countably infinite sets. A countably infinite set can be listed by a bijection from $\mathbb{N}$.

Let $Z$ be the set of infinite binary sequences. Suppose it were countable and list all its members as $s^{(1)},s^{(2)},\dots$, writing $s_n^{(j)}$ for the $n$th entry of row $j$. A finite listing could be repeated to make such a list as well. Define the binary sequence $y$ by $y_n=1-s_n^{(n)}$. It differs from the $n$th row in coordinate $n$, for every $n$. Thus it belongs to $Z$ but is missing from the list, a contradiction. The set $Z$ is uncountable, by Cantor's diagonal argument.

Use $\mathbb{N}=\{1,2,\dots \}$. If a bijection $f:\mathbb{N}\to \mathbb{N}$ maps $S$ onto the even natural numbers, its restriction is a bijection from $S$ onto an infinite set. Moreover, its restriction to the complement of $S$ maps onto the odd natural numbers. Both sets are therefore infinite.

Conversely, suppose that $S$ and its complement are infinite. Applying the increasing enumeration of an infinite subset of natural numbers to each givesFor completeness, successively choose the least unused member. The process never stops because the set is infinite, and it lists every member: an omitted member would have infinitely many selected natural numbers below it, which is impossible. DefineThis is injective on each list, their images are disjoint, and together their images cover $\mathbb{N}$. Thus it is a bijection and maps $S$ onto $2\mathbb{N}$. Both infinitude conditions are necessary and sufficient. If a convention includes zero in $\mathbb{N}$, index each list from zero and use $2j$, $2j+1$ instead.

Use uncountability by interleaving prescribed binary coordinates. For each arbitrary binary sequence $b=(b_k{)}_{k\ge 1}$, define another binary sequence byThere are infinitely many zero coordinates, namely $3k-2$, so $x\in X$. There are also infinitely many coordinates agreeing with the prescribed binary expansion, namely $3k-1$, so $x\in Y$. The coordinates $3k$ recover $b$, making this map an injection of the uncountable set of all binary sequences into $Y$. If $Y$ were a countable set, composing with an injection into $\mathbb{N}$ would make all binary sequences countable, contrary to part (i). Therefore $\boxed{Y\text{ is uncountable}.}$ The construction works for every prescribed binary sequence $(a_n)$; no special distribution property of the digits of $\sqrt{2}$ is needed.

For finite sets $A_1,\dots ,A_r$, the inclusion-exclusion principle statesTo prove it, count the contribution of one element. If it belongs to exactly $q\ge 1$ of the sets, it is counted by $\left(\genfrac{}{}{0ex}{}{q}{k}\right)$ intersections of size $k$. Its total weight isusing the binomial theorem. An element belonging to none contributes zero. Summing these weights gives the cardinality of the union and proves the inclusion-exclusion principle. Equivalently, within a finite ambient set $U$, the number avoiding every $A_i$ is the sum over all $J$, with sign $(-1{)}^{|J|}$ and the empty intersection interpreted as $U$.

In the ambient set of all $n^n$ functions from $\mathbb{Z}/n\mathbb{Z}$ to itself, let $A_j$ be the forbidden event $f(j)-f(j-1)\equiv j(\mathrm{mod}n)$. Apply the avoidance form of the inclusion-exclusion principle from part (i).

For a proper subset $J$ of the $n$ cyclic difference constraints, with $|J|=k<n$, the selected edges form disjoint paths around the cycle, including isolated vertices. There are $n-k$ components. On each component, choosing one value of $f$ arbitrarily determines all the other values by the prescribed differences. No consistency condition occurs because the cycle has been broken. ThereforeThis also works for $n=2$, whose two directed constraints use the same pair of vertices: any single constraint leaves one freely chosen value.

If all $n$ constraints hold, summing them around the cycle gives the necessary conditionIt holds when $n$ is odd and fails when $n$ is even, the latter sum being congruent to $n/2$. When it holds, choose $f(0)$ in $n$ ways and determine every other value; the final constraint is then consistent. Thus the full intersection has size $F=n$ for odd $n$ and $F=0$ for even $n$.

There are $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ subsets of size $k$. By the binomial theorem,Hence the number of admissible functions is

First apply momentum conservation to the rocket and the infinitesimal amount of expelled gas. During $dt$, the exhaust mass is $\alpha dt$ and its inertial velocity, to first order, is $v-u$. With no dust, the momentum balance isIt gives the rocket equation $\boxed{m\dot{v}=\alpha u}$, while $\dot{m}=-\alpha$.

For a dust-collecting rocket, the incoming dust mass is $\beta vdt$ with zero initial momentum. The same balance has rocket mass $m+(\beta v-\alpha )dt$ after the interval, soConsequentlyThe second term in the acceleration equation accounts for the momentum required to bring collected dust up to rocket speed.

Set $\lambda =\sqrt{\alpha /(\beta u)}$ and $V=\lambda u$, so $\alpha u=\beta V^2$. As long as the engines operate and $0\le v<V$, the velocity increases and time can be eliminated:Integrating from $v=0$, $m=m_0$, givesThus the required mass–velocity relation is

If $\lambda >1$, this formula would give $m\to 0$ as $v\to V^{-}$. In this interval, $\dot{m}=\beta (v-{\lambda }^{2}u)<0$. A real rocket retains positive body mass even after its fuel is gone, and collected dust only increases that residual mass. It therefore cannot follow this branch all the way to zero mass: its fuel must run out while $v<\lambda u$. Indeed the hypothetical time integral $dt/dv=m/[\beta (V^2-v^2)]$ is integrable at $V$ when $\lambda >1$, so even the formal zero-mass endpoint would occur at finite time.

If $0<\lambda <1$, the same relation instead gives $m\to \infty$ as $v\to V^{-}$. The mass first decreases, reaches its minimum at $v={\lambda }^{2}u$, and then increases because dust arrives faster than fuel is expelled. The time integral now diverges at $V$: under indefinitely maintained thrust, $v$ approaches $\lambda u$ asymptotically while stored dust grows without bound. At that limiting speed, thrust $\alpha u$ balances the dust-loading term $\beta v^2$, and $\dot{m}\to \beta u\lambda (1-\lambda )>0$. This is the physical reason the total rocket mass no longer signals fuel exhaustion. A rocket with a finite initial fuel supply still runs out at finite time $t=M_{\mathrm{fuel}}/\alpha$ and before reaching $V$; increasing total mass does not create new fuel.

For any vector $\mathbf{a}$, differentiating its components and the rotating basis gives the rotating-frame derivative formulaApply it twice to the position $\mathbf{x}$, with constant angular velocity $\mathbf{\omega }$. The inertial acceleration iswhere dots denote rotating-frame derivatives. Newton's second law therefore becomesThe last terms are the Coriolis force and the force corresponding to centrifugal acceleration.

For the particle on a uniformly rotating inclined plane, choose orthonormal vectors ${\mathbf{e}}_1$ along the horizontal $\xi$ axis and ${\mathbf{e}}_2$ up the slope, and set ${\mathbf{e}}_3={\mathbf{e}}_1\times {\mathbf{e}}_2$, the upward normal vector. Then ${\mathbf{e}}_z=\sin \theta {\mathbf{e}}_2+\cos \theta {\mathbf{e}}_3$ andHere $N$ is the normal reaction. The marble is modeled as the smooth sliding particle specified by the printed equations, without an additional rolling constraint. The rotating-frame Coriolis acceleration and centrifugal acceleration are respectivelyThe normal rotating-frame acceleration is zero, so the normal reaction is not generally $mg\cos \theta$; it satisfiesProjecting the same equation onto the two tangential axes gives exactly

Multiply the equations by $\dot{\xi }$ and $\dot{\eta }$ and add. The Coriolis force terms cancel, as expected because this force does no work relative to the rotating frame. The normal reaction also does no work along the plane. The conserved quantity is rotating-frame kinetic energy plus gravitational and centrifugal potential energy:This need not be the conserved inertial energy, since the externally driven rotating plane can exchange energy with the particle.

The area element in plane polar coordinates is $rdrd\theta$. Thus the axial moment of inertia isFor the removed material, the angular width is $2\pi /13$, andIts moment of inertia is therefore $I_{\mathrm{cut}}=\pi {\rho }_0{a}^5/160$, leavingThe torque equation $I\dot{\Omega }=\tau$ gives constant angular acceleration, so the time to reach the prescribed angular speed from rest is

To find the centre of mass after removing material, let ${\mathbf{e}}_1$ point along the bisector of the missing sector in the disc. The original disc has zero first mass moment about its centre. The missing sector has zero transverse first moment by reflection symmetry, while its component along ${\mathbf{e}}_1$ isbecause the radial integral is $11a^4/192$. The remaining first moment is $-Q_{\mathrm{cut}}{\mathbf{e}}_1$. Dividing by the given mass $k{\rho }_0{a}^3$ gives the body-fixed centre of massIt lies away from the missing sector. In the inertial frame, let $t_{\ast }$ be the moment the applied torque stops and let $\psi ={\psi }_{\ast }+\Omega (t-t_{\ast })$ give the orientation of that sector's bisector. Then, with $d=11a\sin (\pi /13)/(96k)$,The centre of mass has inward centripetal acceleration of magnitude ${\Omega }^{2}d$. The required real force is the constraint reaction exerted by the fixed rod and its support. Its horizontal resultant is $k{\rho }_0{a}^3\ddot{\mathbf{R}}$; a zero applied axial torque does not imply a zero resultant force.

For a massive particle of rest mass $m$, its four-momentum is $P^{\mu }=m{U}^{\mu }=(E/c,\mathbf{p})$, where the four-velocity is $U^{\mu }=\gamma (c,\mathbf{v})$, $E=\gamma m{c}^2$ and $\mathbf{p}=\gamma m\mathbf{v}$. With metric signature $(-,+,+,+)$, $P\cdot P=-m^2{c}^2$. A photon has four-momentum $(E/c,(E/c)\hat{\mathbf{n}})$, a future-pointing null vector. Four-momentum conservation states that the total incoming and outgoing four-momenta agree for an isolated interaction; this includes both energy and momentum conservation in every inertial frame.

Take the incoming photon direction as $x$. Its energy is $\hslash \omega =\mu m{c}^2$, so the total initial four-momentum isThe invariant mass available after photon absorption is therefore $M=m\sqrt{1+2\mu }$. In the centre-of-momentum frame, the two equal daughters have opposite momenta. Their total energy is at least their combined rest energy $2\alpha m{c}^2$, with equality precisely when both daughters have zero momentum in that frame. Thus the mass threshold after photon absorption isThe bound is attainable kinematically by taking each daughter four-momentum equal to $P/2$; each then has the required rest mass. It immediately gives ${\alpha }_{\max }\to 1/2$ as $\mu \to 0$.

At this threshold both daughters move with the centre-of-momentum frame. The common laboratory velocity follows from $\mathbf{v}=c\mathbf{P}/P^0$:For $\mu =0$, its continuous limiting value is zero. At smaller allowed daughter rest masses, some of the centre-of-momentum energy appears as their relative kinetic energy, so their four-momenta need not be $P/2$.