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

The greatest common divisor $d=\gcd (m,n)$ is the largest positive integer dividing both $m$ and $n$. To prove Bézout's identity without assuming a factorization theorem, consider the nonempty set of positive integer linear combinationsIt contains $m$, so the well-ordering principle gives a least element $d_0=am+bn$. By Euclidean division, write $m=q{d}_0+r$ with $0\le r<d_0$. Thenis another integer linear combination. If $r>0$, it contradicts minimality, so $r=0$ and $d_0\mid m$. Applying the same argument to $n$ gives $d_0\mid n$. Conversely, every common divisor divides every integer linear combination and therefore divides $d_0$. In particular every positive common divisor is at most $d_0$. Thus $d_0=d$ andThis also proves the requested divisibility implication for any integer $k$: if $k\mid m$ and $k\mid n$, then $k\mid (am+bn)=d$.

For the scaling identity for greatest common divisors, put $D=\gcd (km,kn)$ with $k>0$. Since $kd$ divides $km$ and $kn$, $D\ge kd$. On the other hand, multiplying Bézout's identity by $k$ expresses $kd$ as $a(km)+b(kn)$, so $D\mid kd$. Positivity gives $D\le kd$. Therefore without using prime factorization,

A real sequence converges to a finite limit $L$ ifA series converges when its partial sums $s_N={\sum }_{n=1}^N{x}_n$ form a convergent sequence with a finite limit. These are different conditions: a series concerns accumulated terms, whereas sequence convergence concerns the terms themselves.

If $s_N\to S$, then $s_{N-1}\to S$ as well and $x_N=s_N-s_{N-1}\to 0$. Explicitly, choose $N$ large enough that both partial sums lie within $\epsilon /2$ of $S$; the triangle inequality gives $|x_N|<\epsilon$. Hence convergence of a series forces its terms to tend to zero.

For the converse, take $x_n=1/n$. This is a null sequence, but its harmonic series diverges. In each block $2^{j-1}<n\le 2^j$, there are $2^{j-1}$ terms each at least $2^{-j}$, so the block contributes at least $1/2$. ThusA zero limit for the terms is necessary, but not sufficient, for convergent series.

Use zero-relative-velocity mass shedding: the released sand initially shares the balloon's vertical velocity, rather than being actively ejected. Let $q=M+m(t)$ and let a positive mass $\delta m$ be shed in a short interval $dt$. The momentum of the balloon and that newly released sand changes byThe leading external impulse is $(T-qg)dt$. Newton's second law applied to this combined material system therefore givesWriting $\frac{d}{dt}(qv)=T-qg$ for the remaining balloon alone would omit the outgoing momentum flux. A nonzero relative ejection velocity would instead produce a rocket equation thrust term.

Initial mechanical equilibrium gives $T=(M+m_0)g$. Write $\lambda =m_0/t_0$, so $m=m_0-\lambda t$ up to depletion. ThenIntegrating from rest,Since $A/t_0=1+M/m_0$ and $A/(A-t_0)=1+m_0/M$, the final upward speed isThe acceleration is nonnegative throughout release, consistent with the upward motion.

Use the inverse Lorentz transformationAlong the particle's worldline $d{x}^{\prime }=u^{\prime }d{t}^{\prime }$, so the relativistic velocity-addition formula isFor subluminal collinear velocities, put $u/c=\tanh {\phi }_u$, $u^{\prime }/c=\tanh {\phi }_{u^{\prime }}$ and $v/c=\tanh {\phi }_v$. The hyperbolic tangent addition formula, obtained by dividing the supplied sine/cosine addition formulas, givesBecause hyperbolic tangent is injective on the real line,Thus rapidity is additive even though velocity is not.

Each positive increment in the instantaneous rest frame adds the same rapidity $\alpha =\mathrm{artanh}(1/2)=\frac{1}{2}\log 3$. Starting from zero rapidity, iterated collinear boosts with equal rapidity giveEvery finite number of increments leaves $u_n<c$; the speed of light is approached as $n\to \infty$.

A function is injective when $f(x)=f(x^{\prime })$ implies $x=x^{\prime }$. It is surjective when every element of its codomain equals $f(x)$ for at least one element of its domain.

If $g\circ f$ is injective, then $f(x)=f(x^{\prime })$ implieshence $x=x^{\prime }$. Thus injectivity of the composition implies injectivity of the first map.

If $g\circ f$ is surjective, then for every $z\in Z$ there is an $x\in X$ with $z=g(f(x))$. Taking $y=f(x)$ proves that $z$ lies in the image of $g$. Thus surjectivity of the composition implies surjectivity of the second map. The arguments include empty domains and codomains whenever the specified functions exist.

The empty-set cases for Cartesian projections matter here. For $p_i$, write $X_j$ for the other factor. If $X_j$ is nonempty, any $x_i\in X_i$ can be paired with an element of $X_j$, so $p_i$ is surjective. If $X_j$ is empty, the Cartesian product is empty and its image is empty. ConsequentlyThe possibility $X_i=\varnothing$ is included because the empty function onto the empty set is surjective.

If $X_i$ is empty, $p_i$ has empty domain and is injective. If $X_j$ has at most one element, an ordered pair is determined by its $i$th coordinate, so $p_i$ is also injective. Conversely, when $X_i$ is nonempty and $X_j$ contains two different elements, pairing those two elements with one fixed $x_i$ gives distinct ordered pairs with the same projection map. Therefore

The universal property of Cartesian products constructs the desired map pointwise:Its coordinate projection maps are $f_1$ and $f_2$. Any other map with those projection maps must have the same two coordinates at every $y$, and hence must equal $g$. This also covers $Y=\varnothing$.

For joint injectivity of a pair of functions, equality $g(y)=g(y^{\prime })$ means equality of both coordinate images. If either coordinate function is injective, it follows that $y=y^{\prime }$, so $g$ is injective. The converse fails: take $Y=\{a,b,c\}$ and map these points to $(0,0),(0,1),(1,0)$ in $\{0,1{\}}^2$. The paired map is injective, but the first coordinate identifies $a,b$ and the second identifies $a,c$.

There is an empty-factor defect in the printed surjectivity implication. If both $X_1$ and $X_2$ are nonempty and $g$ is surjective, every element of either factor can be completed to a pair and then lifted through $g$. Hence both $f_i$ are surjective. If both factors are empty, existence of the $f_i$ forces $Y$ to be empty and both coordinate maps are again surjective. But takeThen $g:\varnothing \to X_1\times X_2=\varnothing$ is surjective, while $f_1:\varnothing \to \{0\}$ is not. Without a nonempty-factor assumption, the printed implication is false. This is exactly the exception found for the projection maps in part (ii).

Even when both factors are nonempty, the reverse implication fails. For $Y=X_1=X_2=\{0,1\}$, let $f_1(y)=f_2(y)=y$. Both coordinate maps are surjective, but $g(y)=(y,y)$ misses $(0,1)$ and $(1,0)$. Thus coordinate surjectivity does not guarantee that every pair is attained.

Use a stars and bars bijection. For a tuple, place $N$ stars in $r+1$ consecutive blocks of lengths $n_0,\dots ,n_r$, separated by $r$ bars. The bar positions form an $r$-element subset of $\{1,\dots ,N+r\}$. Explicitly,They satisfy $1\le b_1<\cdots <b_r\le N+r$. Conversely, such a subset determinesThese numbers are nonnegative and sum to $N$, proving that the two constructions are inverse. HenceZero-length blocks are permitted, so the bijection also covers $N=0$.

For finitely many finite sets $A_1,\dots ,A_k$, the inclusion-exclusion principle statesTo see why, an element belonging to exactly $t\ge 1$ of the sets contributesby the binomial theorem. Elements outside the union contribute zero. Equivalently, if these sets lie in a finite universe $U$, the number avoiding all of them is

For bounded weak compositions, start with the unrestricted stars and bars set $S$ and let $A_i$ be its subset where $n_i\ge a_i$. For an index subset $J\subseteq \{0,\dots ,r\}$, subtract $a_i$ from each coordinate with $i\in J$. This is a bijection from ${\bigcap }_{i\in J}{A}_i$ to nonnegative tuples summing toThuswhere a negative remaining sum gives zero, in accordance with the stipulated convention. Apply the avoidance form of the inclusion-exclusion principle:Expanding by subset size gives the alternating single-index, pair-index and higher-index sums. The empty subset supplies $\left(\genfrac{}{}{0ex}{}{N+r}{r}\right)$.

Use “countable” to include finite and empty sets: a countable set admits an injection into ${\mathbb{N}}_0$. If $B\subseteq A$ and $j:A\to {\mathbb{N}}_0$ is injective, restricting $j$ to $B$ proves that $B$ is a countable set.

For a countable union of countable sets, index the family as $A_0,A_1,\dots$ and choose an injection $j_i:A_i\to {\mathbb{N}}_0$ for each member. For an element $a$ of the union, let $i(a)$ be the least index containing it, and assignThis is injective: equality of the pair gives the same set index and then the same element. Finally the Cantor pairing functioninjects ${\mathbb{N}}_0^2$ into ${\mathbb{N}}_0$. The union is therefore countable. The proof uses chosen injections for the family, as in the usual set-theoretic framework with axiom of countable choice.

For the cardinality of integer-periodic function spaces, fix a positive period $n$ first. A periodic function $\mathbb{Z}\to \mathbb{Z}$ with that period is completely and uniquely determined by its $n$ values at $0,\dots ,n-1$, so this class is in bijection with ${\mathbb{Z}}^n$. The integers are a countable set, and repeated pairing shows that a finite Cartesian product of countable sets is countable. Taking the union over positive $n$ and using the countable union of countable sets proves that the integer-domain periodic functions form a countable set.

For the rational domain, even period one leaves infinitely many independent choices. Let $q_k=1/(k+2)$ for $k\in {\mathbb{N}}_0$; these are distinct members of $\mathbb{Q}\cap [0,1)$. For every subset $A\subseteq {\mathbb{N}}_0$, defineThe fractional part is unchanged by adding one, so $f_A$ is an integer-valued periodic function on $\mathbb{Q}$. Distinct subsets give distinct functions because $f_A(q_k)$ records whether $k\in A$. Thus the uncountable power set of ${\mathbb{N}}_0$ injects into these functions. The rational-domain periodic functions form an uncountable set. The difference is that $\mathbb{Z}$ has only finitely many residue classes modulo a fixed integer period, whereas $\mathbb{Q}$ has infinitely many.

Use the parabola obstruction to countable line coverings. The curveis in bijection with the real line and hence is an uncountable set. A vertical line meets $\mathcal{P}$ in one point. A nonvertical line $y=ax+b$ meets it only where $t^2-at-b=0$, so it meets $\mathcal{P}$ in at most two points.

If countably many lines covered the plane, their intersections with $\mathcal{P}$ would cover $\mathcal{P}$. That would express $\mathcal{P}$ as a countable union of countable sets, indeed of sets with at most two elements, contradicting its uncountability. Therefore no countable collection of lines covers the plane.

For Fermat's little theorem, first suppose $p\nmid x$. Multiplication by $x$ permutes the nonzero residue classes modulo $p$: if $xa\equiv xb(\mathrm{mod}p)$, the prime cannot divide $x$, so cancellation gives $a\equiv b(\mathrm{mod}p)$. Multiplying the representatives in this permutation,Every factor of the factorial is nonzero modulo the prime, so the factorial has a modular inverse and can be cancelled. Thus $x^{p-1}\equiv 1(\mathrm{mod}p)$ and $x^p\equiv x(\mathrm{mod}p)$. If $p\mid x$, both sides are zero modulo $p$. Hence for every integer $x$,For completeness, the cancellation used above follows from Bézout's identity: a number relatively prime to $p$ has an inverse modulo $p$.

The prime-power contraction under pth powers is the key step. If $a=b+p^{k}h$ with $k\ge 1$, the binomial theorem givesThe first term is divisible by $p^{k+1}$. Each later term is also divisible by that power because $kj\ge k+1$ for $j\ge 2$. This includes $p=2$ and $k=1$. ThereforeStart with $x\equiv y(\mathrm{mod}{p}^n)$ and apply this implication $r$ times, increasing both the exponent and modulus at each step:The case $r=0$ is precisely the original congruence.

By Fermat's little theorem, $x^p\equiv x(\mathrm{mod}p)$. Apply the same result with initial modulus $p$ and $r=n-1$:

The finite prime-power Teichmuller representative has an explicit description. Let $y$ be the unique least nonnegative residue satisfyingRepeated Fermat's little theorem gives $y\equiv x(\mathrm{mod}p)$. Part (ii) givesso this residue has both required properties.

For uniqueness, suppose $z$ also has them. From $z^p\equiv z(\mathrm{mod}{p}^n)$, raising congruences to the $p$th power repeatedly gives $z^{p^j}\equiv z(\mathrm{mod}{p}^n)$ for every $j\ge 0$. Meanwhile $z\equiv x(\mathrm{mod}p)$ and the lifting result with $r=n-1$ implyHence $z\equiv y(\mathrm{mod}{p}^n)$. Both lie between zero and $p^n-1$, so $z=y$. Thus existence and uniqueness hold for every residue class, including zero, without needing a general Hensel lemma.

The central force has no transverse component. Its angular equation is thereforeThus the specific angular momentum is the constantThe radial equation isSubstitute $\dot{\theta }=l/r^2$:Consequently the radial motion for $r>0$ is exactly a unit-mass one-dimensional motion in the effective potentialIts conserved energy is $\frac{1}{2}{\dot{r}}^2+V_{\mathrm{eff}}(r)$; the second term in the effective potential accounts for the angular kinetic energy.

For circular orbits in an exponential central potential, a constant positive radius requires $V_{\mathrm{eff}}^{\prime }(r)=0$, orLet $h(r)=r^3{e}^{-r}$. Its derivative is $h^{\prime }(r)=r^2{e}^{-r}(3-r)$: it rises from zero to $h(3)=27/e^3$, then falls back to zero. HenceThe strict lower bound matters: the printed upper bound also allows $l=0$, but then there is no finite-radius circular orbit. Nonzero angular momentum is an implicit hypothesis of the two-orbit claim.

At a circular orbit, use $l^2=r^3{e}^{-r}$ to obtainA small radial displacement $\eta$ satisfies $\ddot{\eta }=-V_{\mathrm{eff}}^{\prime \prime }(r)\eta$. Therefore the inner circular orbit is radially stable at fixed angular momentum, while the outer orbit is unstable. The inner perturbation oscillates with squared frequency $e^{-r_1}(3/r_1-1)$; the outer perturbation has an exponentially growing solution. At the limiting value $l^2=27/e^3$, the radii coalesce at $r=3$ and the linear restoring coefficient vanishes.

For inferring an inverse-square force from Kepler laws, first use the area swept by an infinitesimal radius sector:Kepler's second law makes the areal velocity constant, so $l=r^2\dot{\theta }$ is constant. Then $r\ddot{\theta }+2\dot{r}\dot{\theta }=0$, meaning that the acceleration has no transverse component. Newton's second law therefore gives a central force directed along the Sun–planet line.

For the radial dependence, set $u=1/r$. Since $\dot{\theta }=l{u}^2$,The radial acceleration is the Binet equation expressionThe focus-based ellipse has $u=(1+\epsilon \cos \theta )/A$, hence $u_{\theta \theta }+u=1/A$. ThusFor a planet of mass $m$, the force is $F_r=-m{l}^2/(A{r}^2)$: it is attractive and obeys the inverse-square law. This deduction uses both the shape of the orbit and its constant areal velocity; the orbit shape alone would not determine its time-dependent acceleration.

Let $M_{\mathrm{tot}}={\sum }_i{m}_i$ and introduce positions relative to the centre of mass, ${\mathbf{\rho }}_i={\mathbf{r}}_i-\mathbf{R}$. The definition gives ${\sum }_i{m}_i{\mathbf{\rho }}_i=0$, and differentiation gives ${\sum }_i{m}_i{\dot{\mathbf{\rho }}}_i=0$. Expand the total kinetic energy:The cross term vanishes. This proves the kinetic energy decomposition about the center of mass:The decomposition itself holds without rigidity.

For a rigid body rotating about its centre of mass, ${\dot{\mathbf{\rho }}}_i=\mathbf{\omega }\times {\mathbf{\rho }}_i$. With unit axis vector $\mathbf{n}=\mathbf{\omega }/|\mathbf{\omega }|$, the moment of inertia about that axis iswhere $d_i$ is the perpendicular distance from the axis. Therefore

Use the arch geometry of two hinged rods sliding on a floor, with $A=O=(0,0)$ and $C$ on the other side of $B$. As long as $C$ remains in contact with the floor,The centres of mass of the two rods are $(l\cos \theta ,l\sin \theta )$ and $(3l\cos \theta ,l\sin \theta )$. Their squared speeds are respectively $l^2{\dot{\theta }}^2$ and $l^2(9{\sin }^2\theta +{\cos }^2\theta ){\dot{\theta }}^2$. Each uniform rod has moment of inertia $M{l}^2/3$ about its midpoint, and their angular velocities are $\dot{\theta }$ and $-\dot{\theta }$. Applying the kinetic energy decomposition about the center of mass to each rod givesThe gravitational potential energy is $U=2Mgl\sin \theta$. The fixed pivot does no work; neither does the frictionless floor reaction while $C$ slides horizontally. Conservation of energy from rest therefore givesOn the falling branch $\dot{\theta }$ is the negative square root. Just before the hinge reaches the floor, $\theta =0$, and its speed is $|\dot{B}|=2l|\dot{\theta }|$. Thus, under the maintained-contact interpretation,

There is a contact hypothesis behind this calculation. A floor can push upward but cannot pull downward. For $s=\sin \theta$ and $a=\sin \alpha$, the required normal reaction at $C$, found from the second rod's linear and angular equations, isFor the usual acute arch, this stays nonnegative throughout $0\le \theta \le \alpha$ exactly when $\sin \alpha \le 35/54$. Indeed, for $s>0$, its nonnegativity is $a\le 1/(18s)+11s/6+2s^3$, whose minimum is $35/54$ at $s=1/6$. For larger initial angles, the endpoint lifts before the hinge hits the floor, and the one-coordinate formula no longer governs the whole motion. The displayed impact speed is the intended floor-constrained answer; for unrestricted initial angles, maintained contact is an additional assumption. Subsequent free motion and possible reimpact would require a different model and contact/impact conditions.

Write the position in the rotating basis as $\mathbf{r}={\sum }_i{x}_i^{\prime }{\mathbf{e}}_i^{\prime }$. Differentiating with respect to time in the inertial frame,Here ${\mathbf{v}}^{\prime }={\sum }_i{\dot{x}}_i^{\prime }{\mathbf{e}}_i^{\prime }$ is the relative velocity measured in the rotating reference frame. ConsequentlyThis is the vector differentiation rule for a rotating reference frame with a common origin: the extra term accounts for the changing basis, not a translational motion of that origin.

The PDF gives initial position $(x^{\prime },y^{\prime },z^{\prime })=(1,0,0)$ and initial rotating-frame velocity zero. Use those values; the TeX erroneously places dots over the position coordinates.

For rotation about the third axis, the supplied acceleration relation and Newton's second law give the equations of motion in a rotating frameThus $z^{\prime }=0$. Set $\zeta =x^{\prime }+i{y}^{\prime }$ to combine the planar equations:The two characteristic roots are $i\omega$ and $-3i\omega$. From $\zeta (0)=1$ and $\dot{\zeta }(0)=0$,The triple-angle formulas therefore give the particularly simple astroid motion of a harmonic oscillator in a rotating frameThe orbit satisfies $|x^{\prime }{|}^{2/3}+|y^{\prime }{|}^{2/3}=1$; the zero speed at each cusp is consistent with the smooth time-parametrized motion.

Its rotating-frame speed isHence, for $\omega >0$, the first maximum occurs at $t=\pi /(4\omega )$, andThe maximum repeats periodically. For a signed negative angular frequency, use $\pi /(4|\omega |)$ and $3|\omega |/2$; at $\omega =0$ the particle remains at rest.

Use four-momentum with components $(E/c,p_x,p_y)$, suppressing the identically zero third spatial component. The photon in the primed frame hasIts energy is $h{\nu }^{\prime }$ and its spatial momentum has magnitude $h{\nu }^{\prime }/c$. Apply the same Lorentz transformation as for the spacetime coordinates. With $\beta =v/c$,The time component gives the relativistic Doppler effectThe aberration of light follows by dividing spatial components by $E/c$:In particularwhere the tangent expression is understood only when its denominators exist. The sine and cosine equations determine the correct quadrant and also cover directions where the tangent/secant expression is undefined.

For the photon-number half-cone under relativistic aberration, the forward half of the primed emission angles is $-\pi /2\le {\theta }^{\prime }\le \pi /2$. The aberration of light is monotone on this interval, and its endpoints have $\cos \theta =\beta$. Thus exactly half of a uniform angular photon distribution lies within the lab-frame coneAs $v\to c^{-}$, $\alpha =\arcsin (1/\gamma )\sim 1/\gamma$, so the cone becomes narrow. Here “half” counts emitted photons or ray directions; it is not a claim that half of the observed energy or power lies there, since the relativistic Doppler effect changes the photon energies with angle.

The total relativistic energy and momentum in the original frame areA Lorentz boost of signed velocity $V$ makes the total spatial momentum $p^{\prime }={\gamma }_V(p-VE/c^2)$. Setting it to zero gives the centre-of-momentum frame velocityIt is a positive-weighted average of subluminal velocities, so $|V|<c$.

In the rest mass of a coalescing relativistic collision, four-momentum conservation gives $P_3=P_1+P_2$ provided no energy or momentum escapes in additional radiation. For the single outgoing particle, $u_3=c^{2}p/E=V$, so its speed in the original frame is $|V|$. Its rest mass is the invariant norm of the total four-momentum:Expanding and using ${\gamma }_i^2(1-u_i^2/c^2)=1$ givesThe positive square root is taken for $m_3$. The factor multiplying $2m_1{m}_2$ is the relative Lorentz factor, at least one. Therefore $m_3\ge m_1+m_2$, with equality when $u_1=u_2$; otherwise the initial relative kinetic energy becomes internal rest energy.