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

The Wilson theorem says that $(p-1)!\equiv -1(\mathrm{mod}p)$ for a prime number $p$. Thus $18\cdot 17!\equiv -1(\mathrm{mod}19)$, and since $18\equiv -1$, we get $17!\equiv 1$. The Fermat little theorem says $b^{p-1}\equiv 1(\mathrm{mod}p)$ when $p$ does not divide $b$. Applying it to $3$ gives $3^{18}\equiv 1$, so $3^{16}$ is the inverse of $9$ modulo $19$. Since $9\cdot 17=153\equiv 1$, the required residue isThis is the unique representative in $\{1,\dots ,19\}$.

For the simultaneous integer congruences, the modulus-$2$ condition is already implied by $x\equiv 3(\mathrm{mod}4)$. Write $x=3+4k$; the modulus-$3$ condition becomes $k\equiv 1(\mathrm{mod}3)$, hence $x=7+12t$. The modulus-$5$ condition then gives $2+2t\equiv 4$, or $t\equiv 1(\mathrm{mod}5)$. ThereforeEvery such integer satisfies all four integer congruences; reversing the substitutions shows that there are no others. The uniqueness modulo $60$ also follows from the Chinese remainder theorem applied to the coprime moduli $3,4,5$.

For nonnegative integers $n,m$, the binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$ counts the $m$-element subsets of a fixed $n$-element set. It is zero when $m>n$, and $\left(\genfrac{}{}{0ex}{}{n}{0}\right)=1$, including $n=0$. For $0\le m\le n$, taking the complement is a bijection from $m$-element subsets to $(n-m)$-element subsets; taking a complement twice gives the identity. HenceFor $0\le l\le k\le n$, count ordered pairs $(L,K)$ of subsets of an $n$-element set with $L\subseteq K$, $|L|=l$ and $|K|=k$. Choosing $K$ first and then $L$ gives $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\left(\genfrac{}{}{0ex}{}{k}{l}\right)$. Choosing $L$ first and then the $k-l$ additional elements of $K$ from its complement gives $\left(\genfrac{}{}{0ex}{}{n}{l}\right)\left(\genfrac{}{}{0ex}{}{n-l}{k-l}\right)$. These count the same pairs, proving the nested-subset binomial identity:For the Vandermonde identity, let disjoint sets $A,B$ have cardinalities $m,n$. A $k$-element subset of $A\cup B$ contains some number $i$ of elements of $A$. For a fixed $i$, there are $\left(\genfrac{}{}{0ex}{}{m}{i}\right)\left(\genfrac{}{}{0ex}{}{n}{k-i}\right)$ choices. The classes for different $i$ are disjoint and exhaust all $k$-element subsets, so double counting givesThe zero convention makes this valid for all nonnegative $m,n,k$, even if $k>m+n$. No factorial cancellation is needed for either counting proof.

Outside a spherical planet, Newtonian mechanics gives the inverse-square central force equationThe satellite's mass cancels. The angular momentum is conserved, so the orbit lies in a plane. In that plane the general equations in polar coordinates areA synchronous circular orbit fixed above a surface point must be equatorial, prograde and have angular velocity $\omega =2\pi /T$. Substitution of constant $r$ into the radial equation givesThe radius is measured from the planet's centre; an external orbit requires it to exceed the planet's radius.

Now let the release speed be $v=(1+\eta )v_s$, with $0<\eta \ll 1$, in the same tangential direction. At release $\dot{r}=0$, butThus the satellite initially moves outward. Its specific total energy is $v^2/2-GM/r_s<0$ for this small increase, so the Kepler orbit is an ellipse, with the release point its pericentre. To make this explicit, put $b=v^2/v_s^2\in (1,2)$. The radial turning-point equation from energy and angular momentum conservation has rootsIts semi-major axis is $a=r_s/(2-b)>r_s$. The speed follows from the same conserved energy:It is greatest at pericentre and least at apocentre. In particular, the tangential speed at the two turning points satisfies $r_{\min }{v}_{\max }=r_{\max }{v}_{\min }$. The orbital period becomes $2\pi \sqrt{a^3/(GM)}>T$, so the orbit is no longer fixed over the same surface point.

On the horizontal road the total normal reaction is $Mg$. The kinetic friction force has magnitude $\mu Mg$, so Newtonian mechanics gives $\dot{u}=-\mu g$ until rest. ThusFor the wet high-speed stage, add the four tyre drags: the total linear drag is $\lambda u$, not $\lambda u/4$. Hence $M\dot{u}=-\lambda u$ and $u(t)=U{e}^{-\lambda t/M}$. At the switching speed $u_{\ast }=U/4$, the elapsed time and distance areThe remaining stage has the same constant kinetic friction deceleration as on a dry road, but starts at $U/4$. It therefore contributes time $U/(4\mu g)$ and distance $U^2/(32\mu g)$. Adding both stages of the two-stage stopping under linear drag and dry friction givesThe exponential first stage reaches its positive switching speed in finite time; it need not reach zero under linear drag.

A countable set is a set that is finite or can be put in bijection with the natural numbers; equivalently, it admits an injective function into the natural numbers. To enumerate the rational numbers, list pairs $(p,q)$ with $p\in \mathbb{Z}$, $q\ge 1$ in increasing order of $|p|+q$, and then list $p/q$, discarding repetitions. Each level is finite and every rational eventually appears. An enumeration $q_1,q_2,\dots$ of the rationals then enumerates $\mathbb{Q}\times \mathbb{Q}$ by listing $(q_i,q_j)$ in diagonals of constant $i+j$. ThusTo prove that the real numbers are uncountable, suppose $(0,1)$ had an enumeration $x_1,x_2,\dots$. Write each $x_n$ in its decimal expansion that does not end in an infinite string of nines. Define a new decimal $y=0.d_1{d}_2\cdots$ by taking $d_n=2$ if the $n$th digit of $x_n$ is $1$, and $d_n=1$ otherwise. Then $y\in (0,1)$, has no ambiguous terminating/nines representation, and differs from $x_n$ at digit $n$. The Cantor diagonal argument contradicts the supposed enumeration. Consequently the real numbers are uncountable.

For the discs, use the enumeration of ${\mathbb{Q}}^2$ just constructed. Every positive-radius disc contains a rational-coordinate point: its interior contains a small open rectangle, and each coordinate interval contains a rational number. For each disc $D$, let $j(D)$ be the least index of an enumerated rational-coordinate point in its interior. This minimum exists and requires no arbitrary simultaneous choice. Disjoint discs cannot receive the same point, so $D\mapsto j(D)$ is an injective function into the natural numbers. This proves the countability of pairwise disjoint open disks and also the same conclusion for closed discs, by using their disjoint interiors.

For circles, take all concentric circles centred at the origin with radii $r\in (1,2)$. Two different radii give disjoint circles, and every radius is positive. The radius map is a bijection from the uncountable interval $(1,2)$ to this family. An uncountable disjoint family of nontrivial circles is therefore possible: the rational-point argument for discs relies on their nonempty interiors, which circumferences do not have.

An equivalence relation is reflexive, symmetric and transitive: for all $a,b,c\in S$, one has $aRa$; $aRb$ implies $bRa$; and $aRb$, $bRc$ imply $aRc$. Define the equivalence class $[a]=\{b\in S:aRb\}$. Reflexivity puts $a$ in its class, so these classes cover $S$ and are nonempty. If $[a]$ and $[b]$ share $c$, symmetry and transitivity give $aRb$; the same properties show that every element of either class is in the other. Thus two classes are equal or disjoint. The distinct equivalence classes form a partition of the set.

For the relation defined by a subgroup $H\le G$, $a^{-1}a=1\in H$ proves reflexivity. If $a^{-1}b\in H$, its inverse $b^{-1}a$ belongs to $H$, proving symmetry. If also $b^{-1}c\in H$, their product is $a^{-1}c\in H$, proving transitivity. Finally,These are exactly the left cosets. The map $H\to gH$, $h\mapsto gh$, is a bijection, with inverse $x\mapsto g^{-1}x$. If $G$ is finite and has $r$ such cosets, their disjoint union gives $|G|=r|H|$. This proves the Lagrange theorem:For $g\in G$, finitely many possible powers imply $g^a=g^b$ for some $a<b$, so a positive power is the identity element. If its least positive exponent is $n$, the powers $1,g,\dots ,g^{n-1}$ are distinct: equality of two would produce a smaller positive exponent. They are closed under products and inverses by reducing exponents modulo $n$, hence form the cyclic subgroup $⟨g⟩$ of cardinality $n$. The Lagrange theorem gives $n\mid |G|$, and consequentlyNow take a positive modulus $m$. On residue classes modulo $m$, consider the classes with representatives coprime to $m$. The following integer facts are used: multiplication is associative; reducing representatives respects products; a prime dividing a product divides a factor; and the Bezout identity gives $ra+sm=1$ when $\gcd (a,m)=1$. If $a,b$ are coprime to $m$, no prime divisor of $m$ divides $ab$, so their product class is again in the set. The class of $1$ is its identity element. The Bézout equation gives $ra\equiv 1(\mathrm{mod}m)$, and $r$ is also coprime to $m$ because any common divisor of $r,m$ would divide $1$. Thus every class has an inverse, and these classes form the group of units modulo an integer.

Representing classes in $\{1,\dots ,m\}$ gives precisely the group in the question; for $m=1$ this is the one-element group. Its cardinality is the Euler totient function $\phi (m)$. Applying the finite-group exponent result yields the Fermat-Euler theorem:For $m=1$ the congruence is automatic.

For finite sets $A_1,\dots ,A_r$, the inclusion-exclusion principle isTo prove it, fix an element occurring in exactly $k$ of these sets. Its coefficient on the right is ${\sum }_{s=1}^k(-1{)}^{s+1}(\genfrac{}{}{0ex}{}{k}{s})=1$, by the binomial theorem applied to $(1-1{)}^k$. An element occurring in none has coefficient zero. Summing these elementwise coefficients proves the formula.

Write the prime factorization $n={\prod }_{i=1}^r{p}_i^{c_i}$ with distinct primes and positive exponents. In $\{1,\dots ,n\}$ let $A_i$ be the multiples of $p_i$. A number is coprime to $n$ exactly when it is outside their union. For a nonempty index set $J$, the intersection has $n/{\prod }_{j\in J}{p}_j$ elements, since that product divides $n$. Applying inclusion-exclusion to the complement therefore givesFor $n=1$, the empty product gives $\phi (1)=1$. If positive integers $a,b$ are coprime, their prime factors are disjoint, so the product separates and proves the multiplicativity of the Euler totient function:For a positive divisor $d\mid n$, write the exponent of a prime in $d$ as $b_i\le c_i$, allowing $b_i=0$. Its contribution to $\phi (n)/\phi (d)$ is $p_i^{c_i-b_i}$ if $b_i>0$, and $p_i^{c_i-1}(p_i-1)$ if $b_i=0$. Every contribution is an integer; multiplying proves totient divisibility along divisors:Finally suppose $\phi (n)\mid n$. If $n=1$ the required form is immediate. If $n>1$ were odd, some odd prime $p$ would divide it, and the even factor $p-1$ in $\phi (n)$ would make an even number divide an odd number, impossible. Thus write $n=2^c{\prod }_{j=1}^s{p}_j^{a_j}$ with odd primes and $c\ge 1$. Counting powers of two in the totient formula giveswhere $v_2$ is the $2$-adic P-adic valuation. Every term in the sum is at least one, so there is at most one odd prime $p$ and, if present, $v_2(p-1)=1$. Moreover $p-1\mid \phi (n)\mid n$. Since $p-1$ is coprime to $p$, and $n$ has no prime factors other than $2,p$, the integer $p-1$ must be a power of two. Its exponent is one, hence $p-1=2$ and $p=3$. This provesMore precisely, the integers whose totient divides them are $n=1$ and $2^c{3}^d$ with $c\ge 1$, $d\ge 0$; substitution in the product formula proves the converse. A positive power of $3$ alone does not satisfy the divisibility condition.

The Euclidean algorithm and the Fibonacci number recurrence giveIterating reaches $\gcd (F_1,F_0)=\gcd (1,0)=1$, so consecutive Fibonacci numbers are coprime.

Prove the Fibonacci addition formula by mathematical induction on $k$, asserting it simultaneously for every $n\ge 0$. At $k=1$, $F_1{F}_{n+1}+F_0{F}_n=F_{n+1}$. Suppose the formula holds at $k$. Apply it with $n+1$ in place of $n$ and use the recurrence:ThusFor $n\ge 1$, prove $F_n\mid F_{nl}$ by induction on $l$. The case $l=1$ is immediate. For $l\ge 2$, put $k=(l-1)n$ in the addition formula. Its first term is divisible by $F_n$ by the induction hypothesis, and its second term has an explicit factor $F_n$. ThereforeWhen $m>n\ge 1$, put $k=m-n$. Reducing the addition formula modulo $F_n$ gives $F_m\equiv F_{m-n}{F}_{n+1}$. Since $F_{n+1}$ is coprime to $F_n$, multiplication by it leaves the greatest common divisor with $F_n$ unchanged: any divisor of $F_n$ dividing the product divides $F_{m-n}$, by the Bezout identity or the Euclid lemma. This proves the Fibonacci gcd reductionAt $m=n$ both sides equal $F_n$, since $F_0=0$. The case $n=0$ is also immediate from $\gcd (a,0)=|a|$; the divisibility statement at $n=0$ reads $0\mid 0$, valid under the usual definition $b\mid a$ iff $a=bc$ for an integer $c$.

Put $\kappa =qB/m$, retaining its sign. The Lorentz force equations areThus $z=0$ remains invariant when $z(0)=\dot{z}(0)=0$. Also $d|\dot{\mathbf{r}}{|}^2/dt=2\dot{\mathbf{r}}\cdot \ddot{\mathbf{r}}=0$, since a vector is perpendicular to its cross product with the magnetic field. Choose the initial planar velocity along the positive $x$ axis and the initial location at $(0,0)$. Integration givesThis is a circle centred at $(0,-u_0/\kappa )$ with radius $u_0/|\kappa |$. The cyclotron frequency is $|qB|/m$. Equivalently, choosing this centre as the polar origin givesThe rotation is clockwise viewed from positive $z$ when $qB>0$, and reverses when $qB<0$. In the PDF hint, $\dot{r}=\ddot{r}=0$ are radial conditions with this centred origin; they do not require zero particle velocity. If $qB=0$, the limiting motion is a straight line instead.

With linear drag, put $a=\mu /m>0$. The governing equations for damped cyclotron motion becomeTaking the scalar product with the velocity gives $\frac{1}{2}d|\dot{\mathbf{r}}{|}^2/dt=-a|\dot{\mathbf{r}}{|}^2$, henceFor the planar path, let $w=\dot{x}+i\dot{y}$ and $\zeta =x+iy$. Then $\dot{w}=-(a+i\kappa )w$, so for arbitrary initial planar dataLet ${\zeta }_{\infty }={\zeta }_0+w_0/(a+i\kappa )$. The position relative to this limiting point isIts radius shrinks exponentially while its angle rotates uniformly: the path is a logarithmic spiral into ${\zeta }_{\infty }$, not a succession of circles about the original vacuum guiding centre. The weak-drag assumption is $\mu \ll |qB|$, so many revolutions occur before appreciable contraction.

The rim-mass wheel has moment of inertia $I=M{R}^2$. A uniform solid cylinder has axial moment $\frac{1}{2}m{S}^2$, so the roller of mass $M/2$ has $J=M{S}^2/4$. No slip gives equal contact speeds, $R\omega =S\sigma$, when $\omega ,\sigma$ denote angular-speed magnitudes. ThereforeWith parallel signed axes the two angular velocities have opposite signs. Their kinetic energies add regardless of that convention:The reflected inertia of a no-slip wheel and roller must be used because accelerating the wheel also accelerates the roller. The transmitted contact forces redistribute energy without dissipating it. For an applied wheel torque $T$, the input power is $T\omega$, so the work-energy theorem gives $K\omega \dot{\omega }=T\omega$, or $K\dot{\omega }=T$; this also holds at rest by continuity or the constrained equation of motion.

Assume the driving constants $Q,\Omega$ are positive. With the speed-dependent torque,Separating this linear equation givesFor the fan, its resisting roller torque dissipates power $\gamma {\sigma }^3$. Expressing this in the wheel coordinate gives a resisting wheel torque $\gamma (R/S{)}^3{\omega }^2$. Thus, with $\Gamma =\gamma (R/S{)}^3$,The right-hand side is positive at zero, strictly decreasing for nonnegative $\omega$, and has a unique positive zero; the wheel starting at rest approaches this terminal angular speed. HenceFor a nonzero fan drag this is less than $\Omega$, and as $\gamma \to 0$ it tends to $\Omega$. The cubed radius ratio is essential: one factor arises from converting roller power to wheel torque, in addition to the two factors in ${\sigma }^2$.

For a particle constrained to $z=h(x,y)$, the kinetic energy and potential energy areIn the stipulated gentle-surface small-slope approximation, the second kinetic term is higher order. The leading Euler-Lagrange equations for $T-V$ therefore give the small-slope particle motion on a height graph:This is also the small-slope component of gravity along the surface, with $\sin \varphi \simeq \tan \varphi$. Geometric acceleration terms must remain negligible at the speeds considered; the approximation is not asserted for arbitrarily fast motion on a sharply curved surface.

For $h=\alpha x^2$, the equations are $\ddot{x}+2g\alpha x=0$, $\ddot{y}=0$. If $\alpha >0$, put $\omega =\sqrt{2g\alpha }$. For arbitrary initial data the motion isIt is simple harmonic motion across the trough and uniform motion along it. If $\alpha =0$, both coordinates move uniformly; if $\alpha <0$, the same formula uses $\cosh (\sqrt{-2g\alpha }t)$ and $\sinh (\sqrt{-2g\alpha }t)/\sqrt{-2g\alpha }$ instead.

For the radial height profile, $h(r)=(1-r)/r^2$ is positive for $r<1$, zero at $1$, and negative for $r>1$. Its derivative is $(r-2)/r^3$, so the minimum is $h(2)=-1/4$. It diverges to positive infinity as $r\downarrow 0$ and tends to $0$ from below as $r\to \infty$. The requested profile sketch is shown below.

The equations in polar coordinates in the planar approximation areMultiplying the second equation by $r$ gives $d(r^2\dot{\theta })/dt=0$. Thus the specific angular momentum $L=r^2\dot{\theta }$ is conserved, andAt release with negligible radial velocity, the initial specific kinetic energy is indeedIt is not the total energy. Put $A=L^2+2g$. The conserved specific total energy and effective potential areThe radial turning points for an inverse-square height well follow fromAs a function of $r$, this expression tends to $-\infty$ at zero, has its maximum at $r=A/g$, and tends to $2\mathcal{E}$ at infinity. Only regions where it is nonnegative are dynamically accessible. If $\mathcal{E}<0$, there are two positive turning radii,and the radial coordinate is confined between them. They merge at $r_0=A/g$, the circular orbit. If $\mathcal{E}=0$, the particle escapes to arbitrarily large radius with radial speed tending to zero; if $\mathcal{E}>0$, it escapes with positive limiting radial speed. Consequently the bounded-orbit condition, including the circular case, isThe circular release is at $r_0=2+L^2/g$. For $A/(2g)<r_0<A/g$, the release point is the smaller turning radius; for $r_0>A/g$, it is the larger one. These statements concern the prescribed planar small-slope model. The literal surface is steep near its central singularity, so that approximation must be valid along the particular orbit under consideration.

Take $0\le \gamma \le 1$ for the coefficient of restitution. Conservation of energy in the initial vacuum fall givesThe fixed plate has zero velocity, so the restitution rule makes the first upward rebound speed $u_1=\gamma u_0$. The ratio of rebound to impact kinetic energy is ${\gamma }^2$; henceGravity preserves the speed magnitude between departure from and return to the same plate height. Therefore the upward speed after the $n$th bounce is ${\gamma }^n{u}_0$. The geometric bounce sequence hasThe total travelled distance for $\gamma <1$ is the first fall plus ascent and descent for every rebound. Summing the geometric series givesThe idealized infinitely many impacts accumulate in finite time, after which the limiting state is rest on the plate; $\gamma =0$ gives rest at the first impact.

For the atmospheric fall, use upward signed velocity $u$ and height $z$. Newtonian mechanics with quadratic drag givesBefore impact $u\le 0$, so $\dot{u}=-g+(\alpha /m)u^2$. Set $v=-u\ge 0$, $v_T=\sqrt{mg/\alpha }$, and $\beta =\sqrt{\alpha g/m}=g/v_T$. Separation gives $\mathrm{artanh}(v/v_T)=\beta t$, establishing the descent from rest under quadratic drag:The speed approaches the terminal velocity $v_T$, although the formula is used only until the first impact. This occurs when $\cosh (\beta t_{\mathrm{hit}})=e^{\alpha h_0/m}$. In particular, the atmospheric impact speed is $v_T\sqrt{1-e^{-2\alpha h_0/m}}$, and both speed and height formulas recover the vacuum fall as $\alpha \to 0$.