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

Since $31$ is a prime number, the Wilson theorem states that $30!\equiv -1(\mathrm{mod}31)$. But $30!\equiv (-1)(-2)28!=2\cdot 28!$, so the modular inverse of $2$, which is $16$, givesThe Fermat little theorem states that $a^{p-1}\equiv 1(\mathrm{mod}p)$ when $p$ is prime and $p\nmid a$. Therefore $13^{30}\equiv 1(\mathrm{mod}31)$, andsince $14\cdot 20=280=9\cdot 31+1$. Combining these modular congruences,This representative lies between $0$ and $30$, so it is the least nonnegative residue.

The modular inverse of $2$ modulo $3$ is $2$, so the second modular congruence is $x\equiv 2(\mathrm{mod}3)$. The third means $10\mid 2(x-2)$, equivalently $5\mid x-2$. Cancelling this common factor changes the modulus; it gives $x\equiv 2(\mathrm{mod}5)$.

The first three conditions consequently combine to $x\equiv 2(\mathrm{mod}15)$ and $x$ odd, hence $x=17+30k$ for an integer $k$. The last condition becomesAs $30\cdot 38=17\cdot 67+1$, multiplying by the modular inverse $38$ gives $k\equiv 2(\mathrm{mod}67)$. ThusThe Chinese remainder theorem states that modular congruences with pairwise coprime moduli have a unique solution modulo their product. Here those moduli are $2,3,5,67$, with product $2010$. The derivation proves necessity, and substitution gives $77\equiv 1(\mathrm{mod}2)$, $2\cdot 77\equiv 1(\mathrm{mod}3)$, $2\cdot 77\equiv 4(\mathrm{mod}10)$ and $77\equiv 10(\mathrm{mod}67)$, proving sufficiency for the whole displayed class.

Write the rational number as $r=p/q$ with coprime integers $p,q$ and $q>0$. Substituting into the monic polynomial and multiplying by $q^n$ givesAll terms except the first are divisible by $q$, so $q\mid p^n$. If $q>1$, it has a prime factor dividing $p^n$, and the Euclid lemma implies that this prime divides $p$, contradicting coprimality. Thus $q=1$, proving this special case of the rational root theorem:

The exponential series at $1$ givesFor every positive integer $q$, multiply by the factorial $q!$ and separate the integer part:Every term in $R_q$ is positive. Each denominator is at least $(q+1{)}^j$, and the inequality is strict when $j\ge 2$. Comparison with the geometric series therefore givesIf $e=p/q$ with integers $p$ and $q\ge 1$, then $q!e=p(q-1)!$ would be an integer. Since $I_q$ is also an integer, $R_q$ would be an integer strictly between zero and one, which is impossible. HenceThis proves the irrationality of e by using its rapidly decreasing series tail.

With no electric field, the Lorentz force is $F=q\dot{r}\times B\hat{z}$. The equation from Newton's second law and its first integral areThe cyclotron frequency is $|\omega |$; the sign of $\omega$ specifies the sense of rotation. Since $\hat{x}\times \hat{z}=-\hat{y}$, the initial data giveThe component equations are $\dot{x}=\omega y$, $\dot{y}+\omega x=u+a\omega$ and $\dot{z}=v$. For $\omega \ne 0$, differentiating the first givesSolving this linear differential equation and then using $y=\dot{x}/\omega$ givesThe perpendicular projection is a circle of radius $|u/\omega |$ centred at $(a+u/\omega ,0)$, the guiding centre. The velocity parallel to the magnetic field stays constant, producing helical motion in a uniform magnetic field.

When $a\omega +u=0$, this simplifies toThus the trajectory is a helix about the $z$ axis, with radius $|a|$ and axial advance $2\pi v/|\omega |$ per complete revolution in increasing time. Its projection moves clockwise when viewed from positive $z$ for $\omega >0$. If $v=0$ it is a circle; if $a=0$ it is a straight line along the axis.

For $\omega =0$, the Lorentz force vanishes and the solution is instead $r(t)=a\hat{x}+ut\hat{y}+vt\hat{z}$, also the limit of the general formula. The special condition then forces $u=0$.

Choose the two inertial frames to have coincident origins at $t=t^{\prime }=0$, and let the origin of $S^{\prime }$ have $x=vt$. The Lorentz transformation isHere ${\gamma }_v$ is the Lorentz factor. Along the particle's trajectory, $dx/dt=u$, soDividing gives the relativistic velocity-addition formulaThe denominator is positive because $|uv|<c^2$. Direct algebra yieldssince both factors in the numerator are positive. Consequently $\boxed{|u^{\prime }|<c}$: a subluminal velocity remains subluminal in every such inertial frame.

For the Fibonacci addition formula, use mathematical induction on $k$, with the assertion applying to every $n\ge 1$. At $k=2$, $F_{n+2}=F_{n+1}+F_n=F_2{F}_{n+1}+F_1{F}_n$. If the formula holds for some $k\ge 2$ and all $n$, apply it at $n+1$ and use the Fibonacci number recurrence:This is the assertion at $k+1$, completing the mathematical induction. ThusTaking $k=n\ge 2$ gives the doubling identity

For the Lucas numbers, $L_2=F_3+F_1=3$, and $L_3=F_4+F_2=4=L_2+L_1$. For $n\ge 4$, both expressions for earlier Lucas numbers are available, andHence $\boxed{L_1=1,L_2=3,L_n=L_{n-1}+L_{n-2}(n\ge 3)}$. The separate $n=3$ check matters because the defining expression for $L_1$ was given separately.

The Euclidean algorithm and the Fibonacci number recurrence give, for $n\ge 2$,Repeating reduces to $\gcd (F_2,F_1)=1$; the case $n=1$ is immediate. Therefore $\boxed{\gcd (F_n,F_{n+1})=1(n\ge 1)}$.

For $n\ge 2$, $L_n=F_n+2F_{n-1}$, so a common divisor $d$ of $F_n,L_n$ divides both $F_n$ and $2F_{n-1}$. Since $F_n,F_{n-1}$ are coprime, Bézout's identity gives integers $s,t$ with $s{F}_n+t{F}_{n-1}=1$. Multiplying by $2$ shows $d\mid 2$. Conversely any common divisor of $F_n$ and $2$ divides $L_n$. Including $n=1$, this proves the stronger greatest common divisor identity

The Fermat little theorem states that if $p$ is a prime number, then $a^p\equiv a(\mathrm{mod}p)$ for every integer $a$. Equivalently, for $p\nmid a$, $a^{p-1}\equiv 1(\mathrm{mod}p)$.

To prove it when $p\nmid a$, multiplication by $a$ permutes the nonzero residues $1,\dots ,p-1$. Indeed, $ai\equiv aj(\mathrm{mod}p)$ implies $p\mid a(i-j)$, and the Euclid lemma implies $i=j$ in this range. Multiplying all these residues givesNone of the factors of $(p-1)!$ is divisible by $p$, so the factorial has a modular inverse. Cancelling it proves $a^{p-1}\equiv 1$, hence $a^p\equiv a$. When $p\mid a$, the latter identity has both sides zero, completing the proof.

For an odd prime number $p\ne 5$, the numbers $10,p$ are coprime. The Fermat little theorem gives $10^{p-1}\equiv 1(\mathrm{mod}p)$, and consequentlyThese exponents are distinct, so infinitely many are obtained.

Write the repdigit with $n$ copies of $5$ asIf $p\ne 3,5$, choose $n$ to be any positive multiple of $p-1$. Then $9$ has a modular inverse modulo $p$, so $p\mid R_n$. Division by $9$ cannot be used modulo $3$; instead $10\equiv 1(\mathrm{mod}3)$ gives $R_n\equiv 5n(\mathrm{mod}3)$, so $3\mid R_{3j}$ for every $j\ge 1$. If $p=5$, every $R_n$ is divisible by $5$. ThusThe separate treatment of $3$ accounts for the prime factor of the geometric-sum denominator.

Enumerate $A$ as $a_1,\dots ,a_a$. A function is specified by choosing the image of each of these elements independently, with $b$ possibilities each. The multiplication principle gives $\boxed{b^a\text{ functions}}$.

For an injective function, successive images must be distinct. If $a\le b$, there are $b$ choices for the first, $b-1$ for the second, and so on. If $a>b$, the pigeonhole principle makes injectivity impossible. Thus the number of injective functions isThe product in the first case is a falling factorial.

For finite sets $C_1,\dots ,C_k$, the inclusion-exclusion principle statesIn a finite ambient set $\Omega$, its equivalent complement form iswhere the intersection for $J=\varnothing$ means $\Omega$. To see the counting mechanism, an element in exactly $r\ge 1$ of the sets has coefficient ${\sum }_{i=1}^r(-1{)}^{i+1}(\genfrac{}{}{0ex}{}{r}{i})=1$, by the binomial theorem; an element in none has coefficient zero in the union formula.

Let $\Omega$ be the set of all functions from the $n$-element domain to the $k$-element codomain, and let $C_j$ consist of the functions which omit codomain element $j$. A function is surjective precisely when it lies outside ${\bigcup }_j{C}_j$.

For $J\subseteq [k]$ of size $i$, the intersection ${\bigcap }_{j\in J}{C}_j$ consists of maps taking all their values in the remaining $k-i$ elements, so it has $(k-i{)}^n$ members. There are $\left(\genfrac{}{}{0ex}{}{k}{i}\right)$ choices of $J$. Applying the complement form of the inclusion-exclusion principle givesWhen $k=n$, every fibre of a surjective function has at least one member, and the $n$ fibres partition an $n$-element domain. Thus every fibre has exactly one member and the function is a bijection. The count of these bijections is $n!$ by the successive distinct-image choices from part (a). Hence

A set is countable if it admits an injective function into $\mathbb{N}$, equivalently if it is finite or can be listed in a sequence. The empty set is included; an infinite countable set has a bijection with $\mathbb{N}$.

Every rational number has a representation $p/q$ with $p\in \mathbb{Z}$ and $q\ge 1$. For each $k\ge 1$, there are only finitely many such pairs with $|p|+q=k$. List these finite levels successively, ordering each level by $p$, and discard repeated fractions when they first recur. Every rational number appears in some finite level, proving $\boxed{\mathbb{Q}\text{ is countable}}$.

For the uncountability proof, suppose all numbers in $(0,1)$ could be listed as $r_1,r_2,\dots$. Choose each decimal expansion not to end in an infinite string of nines, and denote its $j$th digit by $d_{ij}$. Set $b_i=1$ when $d_{ii}\ne 1$, and $b_i=2$ otherwise. Then the decimaldefines a number in $(0,1)$ with a unique such expansion, since its digits are only $1$ and $2$. It differs from $r_i$ at digit $i$ for every $i$, contradicting the enumeration. This Cantor diagonal argument proves $\boxed{\mathbb{R}\text{ is uncountable}}$ because its subset $(0,1)$ already is.

For the union of two countable sets $C,D$, take injective functions ${\iota }_C:C\to \mathbb{N}$ and ${\iota }_D:D\to \mathbb{N}$. The mapis injective: it is injective within each branch, and their images have different parity. Thus $\boxed{C\cup D\text{ is countable}}$, regardless of overlap.

The property of $A$ says that both $A$ and its complement are dense subsets of the real line. Both possible cardinalities occur. To establish the needed density directly, given $x\in \mathbb{R}$ and $\epsilon >0$, choose an integer $q>1/\epsilon$. Then $\lfloor qx\rfloor /q$ is rational and differs from $x$ by less than $1/q<\epsilon$. For an irrational approximation, choose a rational $r$ within $\epsilon /2$ of $x$ and a positive integer $q$ large enough that $\sqrt{2}/q<\epsilon /2$. The number $r+\sqrt{2}/q$ is irrational and lies within $\epsilon$ of $x$; irrationality follows from that of $\sqrt{2}$, since otherwise subtracting $r$ and multiplying by $q$ would make $\sqrt{2}$ rational. To recall the latter fact, a reduced fraction $p/q=\sqrt{2}$ would satisfy $p^2=2q^2$, forcing $p$ even and then $q$ even, contrary to coprimality. ThereforeThe second set is uncountable because, if it were countable, its union with $\mathbb{Q}$ would make $\mathbb{R}$ countable. The same two density arguments give the required approximations from $A$ and from its complement in either example.

Finally, the condition on $B$ makes every one of its points an isolated point, so $B$ is a discrete subset of the real line. Enumerate all rational intervals $(p_j,q_j)$ with $p_j<q_j$; enumerate pairs of indices of the rational list by increasing sum and keep those whose endpoints have the required order. For each $b\in B$, its isolating neighbourhood contains a rational interval $(p_j,q_j)$ containing $b$ and no other point of $B$. Assign to $b$ the least such index $j$. Two distinct points cannot receive the same index, because that interval would then contain two members of $B$. This gives an injective function $B\to \mathbb{N}$ and proves that discrete subsets of the real line are countable:Using the least index makes the assignment explicit and requires no arbitrary selection of an uncountable family of intervals.

For the moment of inertia of a uniform solid sphere, write the mass density as $\rho =3m/(4\pi a^3)$. In spherical coordinates about the chosen axis, the squared perpendicular distance is $R^2{\sin }^2\vartheta$. The volume element is $R^2\sin \vartheta dRd\vartheta d\phi$, so

Take $0<\alpha <\pi /2$ and $\ell >0$, with a fixed plane. The normal force has magnitude $N=mg\cos \alpha$ and is perpendicular to the plane. On the perfectly smooth plane there is no friction. Both gravity and the normal force have zero torque about the marble's centre, so a marble released from rest does not rotate. The component of Newton's second law down the plane is $m{A}_1=mg\sin \alpha$, henceThe normal force does no work because the velocity is tangent to the plane. Gravity is conservative, so mechanical energy, the sum of translational kinetic energy and gravitational potential energy, is conserved.

For rolling without slipping, let the static friction force have magnitude $f$, pointing up the plane. It supplies the torque that spins the marble while reducing its translational acceleration. If $\Omega$ is the angular velocity and $A_2$ the acceleration down the plane, the rolling constraint is $a\Omega =\dot{s}$, hence $a\dot{\Omega }=A_2$. The translation and rotation equations areThus $f=I{A}_2/a^2$ andThese are the equations for rolling acceleration with rotational inertia; the plane must be rough enough to supply this static friction.

The point of contact is instantaneously at rest relative to the fixed plane, so static friction does no total work on the rolling marble. Equivalently, its translational power is $-f\dot{s}$ and its rotational power is $fa\Omega =f\dot{s}$, which cancel. The normal force also does no work. Consequently mechanical energy is conserved here too, now with rotational kinetic energy included:where $H$ is the centre's height. No energy loss is implied by the presence of ideal static friction. Constant acceleration from rest gives

For the hollow marble, put $I=\lambda m{a}^2$ in the same equations. The smooth-plane time is unchanged, while the rolling acceleration becomes $g\sin \alpha /(1+\lambda )$. ThereforeThis again assumes rolling without slipping and enough static friction; the ratio depends on the mass distribution through its moment of inertia.

For the inverse-square potential $V(r)=-Q/r$, the central force is $-V^{\prime }(r)\hat{r}=-Q\hat{r}/r^2$. The transverse component of acceleration in polar coordinates is therefore zero:Thus $\boxed{h=r^2\dot{\theta }\text{ is constant}}$; for unit mass it is the signed angular momentum perpendicular to the orbital plane. The radial component givesConsequentlyThis is the mechanical energy, since the full kinetic energy is $\frac{1}{2}({\dot{r}}^2+r^2{\dot{\theta }}^2)$ and $r^2{\dot{\theta }}^2=h^2/r^2$.

For $h\ne 0$ and $Q>0$, the effective potential goes to $+\infty$ as $r\downarrow 0$ and to zero from below as $r\to \infty$. Its derivative is $U^{\prime }(r)=(Qr-h^2)/r^3$, so it decreases up to $r_0=h^2/Q$ and then increases. Its zero and minimum areFor $Q<0$, $U=h^2/(2r^2)+|Q|/r$ is positive and strictly decreasing, with limits $+\infty$ at zero and $0^{+}$ at infinity. It has no minimum at a finite positive radius.

If $h=0$, the centrifugal term disappears. For $Q>0$ the graph is instead $-Q/r$, increasing from $-\infty$ to $0^{-}$ without a minimum; for $Q<0$ it remains positive and decreasing. The bounded-orbit calculation below uses the stipulated $h>0$, which excludes this radial collision case.

The radial energy equation is ${\dot{r}}^2=2(E-U(r))$, so motion requires $U(r)\le E$. For $Q>0$ and $h>0$, the effective potential minimum and its limiting value zero at infinity implyAt the lower endpoint the particle stays at $r=h^2/Q$, giving a circular orbit. Strictly between that endpoint and zero, two positive turning points confine the radial motion. For $E$ below the minimum there is no allowed motion, while $E\ge 0$ does not give a radially bounded orbit.

Write $\epsilon =|E|$ and $D=Q^2-2\epsilon h^2\ge 0$. At each turning point $E=U(r)$, soThe smaller and larger roots give the periapsis distance and apoapsis distance:They coincide for the circular orbit. Their sum and product are

The speed satisfies $v^2=2(E+Q/r)$, which decreases strictly with $r$ because $Q>0$. Thus its maximum is at the periapsis and its minimum at the apoapsis. At either endpoint the radial velocity vanishes, so $v=h/r$. Therefore the apsidal speed sum for an attractive inverse-square orbit isHence $\boxed{v_{\min }+v_{\max }=2Q/h}$. Individually, $v_{\min }=(Q-\sqrt{D})/h$ and $v_{\max }=(Q+\sqrt{D})/h$, also valid when the orbit is circular.

At infinity the potential energy tends to zero, so the conserved mechanical energy is $E=\frac{1}{2}{v}_{\infty }^2$. The impact parameter $b$ is the perpendicular distance from the origin to the incoming asymptotic line. Conservation of angular momentum gives $|h|=b{v}_{\infty }$.

For $b>0$, a turning point of the radial motion satisfiesOnly the positive root is physical, givingFor $Q=0$ this reduces to the straight-line closest distance $b$.

For nonzero $Q$, put $\eta =b{v}_{\infty }^2/|Q|\ll 1$. If $Q<0$, the numerator is $|Q|(\sqrt{1+{\eta }^2}+1)$, soIf $Q>0$, rationalize the numerator instead:Thus the requested leading distances areRepulsion gives a finite barrier even for zero impact parameter; attraction allows much closer passage. At $b=0$, the attractive formula has the limiting closest distance zero, corresponding to collision with the singular centre rather than a positive turning point.

Work in an inertial frame, take all masses to be constant, and assume the internal forces obey the pairwise relation from Newton's third law $F_{ij}=-F_{ji}$. For the angular momentum result, also assume these pair forces are central, so $F_{ij}$ is parallel to $r_i-r_j$ and its pair torque vanishes. The equations from Newton's second law areSumming them and pairing the internal forces gives

About a fixed point $a$, define the total angular momentum and external torque byDifferentiation produces no velocity term because ${\dot{r}}_i\times m_i{\dot{r}}_i=0$. Grouping internal terms into pairs givesEach final cross product is zero by centrality, proving $\boxed{d{L}_a/dt=G_a}$. Equal and opposite internal forces give momentum conservation when the total external force is zero, but do not in general make their internal torques cancel; the central-force assumption supplies that extra step.

Let $M={\sum }_i{m}_i$ and let the centre of mass be $R=M^{-1}{\sum }_i{m}_i{r}_i$, so $P=M\dot{R}$. For an arbitrary moving reference point $a(t)$, the same differentiation givesTaking $a=R$, the extra term is $-\dot{R}\times M\dot{R}=0$. Therefore the corresponding angular momentum about the centre of mass satisfiesIts definition using velocities relative to $\dot{R}$ agrees with the one above, since ${\sum }_i{m}_i(r_i-R)=0$ makes ${\sum }_i(r_i-R)\times m_i\dot{R}=0$. Thus this result remains true even when the centre of mass accelerates.

Finally take the common mass to be $m$ and $F_i=-k{\dot{r}}_i$, with constant $k$. About either a fixed point or the centre of mass,The angular-momentum equation becomes $\dot{L}=-(k/m)L$. Multiplying by the integrating factor $e^{kt/m}$ gives $\frac{d}{dt}(e^{kt/m}L)=0$, hence the angular momentum decay under uniform linear drag isThe common mass and common drag coefficient ensure that the same decay factor applies to every term.

Let $p$ be the magnitude of the incident particle's momentum. The relativistic energy-momentum relation givesThe stationary particle contributes rest energy $m{c}^2$ and zero momentum. Conservation of four-momentum therefore gives equal photon energies $\epsilon =(E+m{c}^2)/2$. A photon has momentum magnitude $\epsilon /c$, so if the two momentum vectors meet at angle $\theta$,Substitution gives the angular relation for two-photon electron-positron annihilation, whose derivation depends only on the stipulated equal rest masses and equal photon energies:All energies and the angle here are in the laboratory inertial frame.

For perpendicular photon trajectories, $\cos \theta =0$ and hence $E=3m{c}^2$. Since $E=\gamma m{c}^2$ with Lorentz factor $\gamma =(1-v^2/c^2{)}^{-1/2}$,For the small-speed limit, set $\beta =v/c\ge 0$ and $\delta =\pi -\theta$. The angle formula impliesUsing $\arcsin z=z+O(z^3)$ therefore gives $\delta =\beta +O({\beta }^3)$, soAt zero incident speed the momenta are equal and opposite, so $\theta =\pi$, consistent with the expansion.