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

A prime number is an integer $p>1$ whose only positive divisors are $1$ and $p$. Every integer greater than one has a prime factorization; in particular it has a prime divisor.

To prove infinitely many primes congruent to minus one modulo six, suppose a finite list $p_1,\dots ,p_n$ contains all such primes, and put $P=p_1\cdots p_n$; the empty product is one. The integer $N=6P-1>1$ is coprime to $6$, so each prime factor is congruent to $1$ or $-1$ modulo $6$. If all its prime factors, counted with multiplicity, were congruent to $1$, their product would also be congruent to $1$. But $N\equiv -1(\mathrm{mod}6)$. Hence some prime divisor $q$ satisfies $q\equiv -1(\mathrm{mod}6)$. None of the listed primes divides $N$, since $N\equiv -1(\mathrm{mod}{p}_i)$. This contradicts completeness of the list.

For infinitely many primes congruent to one modulo six, suppose instead that $p_1,\dots ,p_n$ lists every prime congruent to $1$ modulo $6$, and useIt is odd. Since each listed prime is coprime to $3$, $P^2\equiv 1(\mathrm{mod}3)$, so $N\equiv 1(\mathrm{mod}3)$ and $3$ does not divide it. Any prime divisor $q$ is therefore greater than $3$ and satisfies the modular congruenceThe allowed quadratic-congruence result gives $q\equiv 1(\mathrm{mod}6)$. Yet $N\equiv 3(\mathrm{mod}{p}_i)$, and $p_i>3$, so no listed prime divides $N$. Again there is a new prime in the required residue class. Thus both residue classes $6k-1$ and $6k+1$ contain infinitely many primes.

For integers $0\le r\le n$, the binomial coefficient isthe number of $r$-element subsets of an $n$-element set. It is zero outside that range. To obtain Pascal's identity, distinguish one element of an $(n+1)$-element set. An $r$-element subset either omits it, giving $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ choices, or contains it, leaving $\left(\genfrac{}{}{0ex}{}{n}{r-1}\right)$ choices. These cases are disjoint and exhaustive, so

If $p$ is a prime number and $0<r<p$, thenThe right side is divisible by $p$, while $r!$ is coprime to $p$. Cancellation modulo $p$ proves the prime-row binomial coefficient divisibilityApply the binomial theorem in the polynomial ring modulo $p$. The intermediate coefficients just proved to vanish giveMultiplying by $(1+X{)}^k$ yieldsFor $0\le r\le k<p$, the $X^p$ factor cannot contribute to the coefficient of $X^r$. Comparing coefficients proves the binomial coefficient congruence across a prime rowThis also covers $r=0$, when both sides are one.

Let $m$ be the car's mass and let $v(t)$ be its forward speed. Initially the driven contact surfaces slip backward relative to the ground because $v<r\Omega$. Thus kinetic friction on the car acts forward. On the horizontal surface the total normal force is $mg$, so Newton's second law gives $m\dot{v}=\mu mg$. While slipping persists,The contact slip speed is $r\Omega -v(t)$. Its first zero is the onset of rolling without slipping, henceThe engine maintains the prescribed wheel speed, so wheel spin-down is not part of this calculation.

On a slope of angle $\alpha >0$, directed uphill, the normal force is $mg\cos \alpha$ and gravity contributes $-mg\sin \alpha$ along the slope. Therefore the uphill acceleration while slipping is $g(\mu \cos \alpha -\sin \alpha )$. If it is positive, the onset of rolling without slipping occurs atThe inequality follows because $\mu \cos \alpha -\sin \alpha <\mu$. If $\mu \cos \alpha \le \sin \alpha$, the car does not accelerate uphill to $r\Omega$, so there is no finite catch-up time in this sliding-friction model. The finite-time conclusion presumes positive traction sufficient to climb the slope.

Write $v=\dot{x}$. The simple pendulum becomes $\dot{x}=v$, $\dot{v}=-\sin x$. Its equilibria are $(k\pi ,0)$. The linearization is $\left(\begin{array}{cc}0& 1\\ -\cos (k\pi )& 0\end{array}\right)$. For even $k$ its eigenvalues are $\pm i$, and for odd $k$ they are $\pm 1$. The conserved energyhas a strict local minimum at each even multiple of $\pi$, proving nonlinear Lyapunov stability there. The odd multiples are saddles and are unstable. ThereforeThe stable centres are not asymptotically stable because energy is conserved.

The saddle energy is $H=2$, so the separatrix is determined byEnergy levels $0<H<2$ form closed libration curves around the centres; levels $H>2$ have velocity of constant sign and describe rotations. The separatrices join neighboring saddles in the unwrapped $(x,v)$ plane. On the angle cylinder, where $x$ is identified modulo $2\pi$, they are homoclinic to the single saddle.

At $x=0$ the positive separatrix has $\dot{x}=2$. Before reaching the neighboring saddle at $x=\pi$, the velocity is $2\cos (x/2)>0$, so the time to angle $a<\pi$ isAs $a\uparrow \pi$, $\cos (x/2)\sim (\pi -x)/2$. The integrand is therefore asymptotic to $1/(\pi -x)$, whose improper integral diverges logarithmically. Thus the pendulum separatrix approach takes infinite time:Starting with velocity $-2$ gives the reflected approach to $x=-\pi$ and the same infinite time. The velocity tends to zero but never reaches zero at a finite time.

An equivalence relation on $A$ is a binary relation that is reflexive, symmetric and transitive: $xRx$ for every $x$; $xRy\Rightarrow yRx$; and $xRy,yRz\Rightarrow xRz$. Write $T=R\circ S$, using the stated order for composition of relations. Composition is associative because both possible bracketings mean that there is a two-step sequence of intermediate witnesses. Reflexivity showsand also that $T$ is reflexive. Transitivity and reflexivity of the original relations give $R\circ R=R$, $S\circ S=S$. Since both original relations are symmetric,The four parts below show that each condition is equivalent to the commuting equivalence relations condition $R\circ S=S\circ R$.

For the integer example, put $d=\gcd (m,n)$. Membership of $(x,z)$ in the composite means that some $y$ satisfies $y-x=ma$, $z-y=nb$ for integers $a,b$. Consequently $z-x=ma+nb$ is divisible by $d$. Conversely, if $z-x$ is divisible by $d$, the Bezout identity expresses it as $ma+nb$; setting $y=x+ma$ provides the required witness. ThusReversing the roles of $m,n$ gives exactly the same modular congruence relation, hence $R\circ S=S\circ R$. This verifies all four conditions and identifies their common smallest equivalence relation explicitly.

By the inverse identity established in the root solution, the composite $T$ is a symmetric relation precisely whenThus condition (i) implies condition (iii). Conversely, if $S\circ R\subseteq R\circ S$, take inverse relations. Since $R,S$ are symmetric, this gives the reverse inclusion $R\circ S\subseteq S\circ R$. The two composites are equal, making $T$ symmetric. Therefore (i) and (iii) are equivalent, and either one forces commutation.

A binary relation $T$ is transitive exactly when $T\circ T\subseteq T$. If condition (iii) holds, associativity and monotonicity of composition of relations giveHence (iii) implies (ii). Conversely, the inclusions $R,S\subseteq T$ implyIf $T$ is a transitive relation, the right side lies in $T$, which is condition (iii). Thus (ii) and (iii) are equivalent.

The inverse argument in part (i) proves that the one-sided inclusion in (iii) already implies equality:Parts (i) and (ii) then make $T$ both symmetric and transitive; it is reflexive from the root solution. Therefore $T$ is an equivalence relation containing $R$ and $S$.

If $U$ is any other equivalence relation containing both, a witness $xRy,ySz$ gives $xUy,yUz$, and transitivity gives $xUz$. Hence $T\subseteq U$. Thus (iii) implies the unique-smallest assertion in (iv).

Condition (iv) says in particular that $T$ is an equivalence relation, so it is symmetric and transitive. It therefore implies (i) and (ii), closing the chain of implications.

Uniqueness is literal: if two equivalence relations both contain $R,S$ and are each contained in every such relation, each is contained in the other, so they are equal. Combining the preceding proofs givesTheir common relation is the equivalence relation generated by $R\cup S$, and under these conditions it is already obtained by the two-step composite $R\circ S$.

For finite sets $A_1,\dots ,A_n$, the inclusion-exclusion principle statesTo prove it, fix an element belonging to exactly $k$ of the sets. If $k=0$, it contributes zero to both sides. If $k\ge 1$, its total weight on the right isby the binomial theorem. Summing these pointwise contributions proves the formula.

Let the universe be the $n!$ permutations of $\{1,\dots ,n\}$, and let $A_j$ be the set of permutations fixing $j$. A derangement belongs to none of the $A_j$. If $k$ specified points must be fixed, the remaining $n-k$ points can be permuted in $(n-k)!$ ways, so every such $k$-fold intersection has that size. There are $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ choices of the specified fixed points. Applying inclusion-exclusion to the complement of their union gives the derangement counting formulaThe $k=0$ term is the whole universe. Since the exponential power series converges absolutely at $-1$,The alternating-series remainder additionally gives $\left|f(n)/n!-e^{-1}\right|\le 1/(n+1)!$. Thus the fraction is the probability of no fixed points in a uniformly chosen permutation and approaches $1/e$.

Fermat's little theorem states that, for a prime number $p$ and any integer $a$,If $p\mid a$, both sides vanish modulo $p$. Otherwise multiplication by $a$ permutes the nonzero residue classes modulo $p$: it is injective because $ai\equiv aj$ implies $i\equiv j$ by cancellation. Taking the products of these residues givesThe factorial is coprime to $p$, so cancellation proves $a^{p-1}\equiv 1(\mathrm{mod}p)$ and hence the stated version. This proves Fermat's little theorem in both cases.

Let $n$ be a Carmichael number. If a prime square $p^2$ divided $n$, choose $a=p$. Since $n$ is an odd composite integer, $n>1$, and $p^n-p\equiv -p\not\equiv 0(\mathrm{mod}{p}^2)$. This contradicts the required modular congruence modulo $n$. Therefore every Carmichael number is squarefree.

For each prime divisor $p$ of $n$, choose the allowed primitive root $g$ modulo $p$. The Carmichael identity applied to the positive integer $g$ gives $g^n\equiv g(\mathrm{mod}p)$, and cancellation gives $g^{n-1}\equiv 1(\mathrm{mod}p)$. By its defining order property,Conversely, suppose a composite integer $n$ is squarefree and has this divisibility for every prime divisor. For an arbitrary integer $a$, modulo a prime divisor $p$ there are two cases. If $p\mid a$, then $a^n\equiv a\equiv 0$. Otherwise Fermat's little theorem and $p-1\mid n-1$ give $a^{n-1}\equiv 1$, so again $a^n\equiv a$. Since the prime divisors are distinct and pairwise coprime, their product $n$ divides $a^n-a$. This is the proof of Korselt criterion:

If $n=pq$ for distinct odd primes with $p<q$, the condition at $q$ would require $q-1\mid pq-1$. Reducing $pq-1$ modulo $q-1$ gives $p-1$, so $q-1\mid p-1$. But $0<p-1<q-1$, which is impossible. Thus a product of two distinct odd primes is not Carmichael.

For $n=pqr$, squarefreeness is automatic. Since $p\equiv 1(\mathrm{mod}p-1)$,Apply the analogous reductions at $q$ and $r$ to obtainFinally $1729=7\cdot 13\cdot 19$, with distinct odd prime factors, andAll three divisibilities hold, so 1729 is a Carmichael number.

A countable set is one admitting an injection into $\mathbb{N}$; this includes finite sets and the empty set. An infinite countable set can equivalently be listed in a sequence indexed by $\mathbb{N}$.

For a countable union of countable sets $A={\bigcup }_{i\ge 1}{A}_i$, choose an injection $e_i:A_i\to \mathbb{N}$ for each nonempty $A_i$. Assign $x\in A$ the pair $(i,e_i(x))$, where $i$ is the least index with $x\in A_i$. This is an injection into ${\mathbb{N}}^2$. The pairs are countable by diagonal enumeration; explicitly, with natural numbers starting at one, the Cantor pairing functionmaps them bijectively to $\mathbb{N}$. Composing the two maps proves that the union is countable. Empty members contribute no elements.

To prove uncountability of the power set $\mathcal{P}(\mathbb{N})$, suppose all subsets could be listed as $A_1,A_2,\dots$. DefineFor every $n$, $D$ differs from $A_n$ on whether it contains $n$. Thus $D$ is missing from the supposedly exhaustive list. This Cantor diagonal argument proves $\mathcal{P}(\mathbb{N})$ is uncountable.

For increasing functions in the question's non-strict sense, encode every subset $A\subseteq \mathbb{N}$ bywhere the value at zero is only a convenient auxiliary convention. ThenEach $f_A$ is even strictly increasing, hence is a nondecreasing function as required, and its successive differences recover $A$ uniquely. This is an injection from the uncountable power set into the requested collection. Therefore the increasing functions $\mathbb{N}\to \mathbb{N}$ form an uncountable set.

For a decreasing function in the question's sense, $f$ is a nonincreasing function with positive integer values. Each strict decrease lowers its value by at least one, so there can be at most $f(1)-1$ strict decreases. There is consequently a final drop, after which the function is constant. Every such function is determined by a finite initial list whose final value repeats forever. The set of all these lists is contained ina countable union of countable sets, hence countable by the result just proved. Thus the decreasing functions $\mathbb{N}\to \mathbb{N}$ form a countable set. These contrasting cardinalities of monotone natural-number functions come from the absence of an upper bound for increasing values and the finite number of drops available to decreasing natural-number values. If the natural numbers include zero, the same proof uses the bound $f(1)$ instead.

Let ${\mathbf{e}}_r,{\mathbf{e}}_{\varphi },{\mathbf{e}}_z$ be the cylindrical unit vectors. The surface has an upward normal vector proportional to ${\mathbf{e}}_z-h^{\prime }(r){\mathbf{e}}_r$. If $N_z$ is the vertical component of the normal force, its radial component is $-h^{\prime }(r)N_z$. In the stated approximation, vertical acceleration and the vertical driving-force component are neglected, so vertical balance gives $N_z\simeq Mg$. The horizontal contact force is consequently $-Mg{h}^{\prime }(r){\mathbf{e}}_r$. The projected velocity and its speed areThe driving force is parallel to this velocity, with components $F\dot{r}/u$ and $Fr\dot{\varphi }/u$. Use the acceleration in polar coordinates and Newton's second law to obtainThese equations apply where $u\ne 0$; at rest the direction of an exactly velocity-aligned drive is not determined.

For a prescribed path, write $r^{\prime }=dr/d\varphi$, $r^{\prime \prime }=d^{2}r/d{\varphi }^2$. The chain rule gives $\dot{r}=r^{\prime }\dot{\varphi }$ and $\ddot{r}=r^{\prime \prime }{\dot{\varphi }}^2+r^{\prime }\ddot{\varphi }$. Subtract $r^{\prime }/r$ times the azimuthal equation from the radial equation. The driving force and $\ddot{\varphi }$ both cancel:Thus the constraint for tangentially driven motion on an axisymmetric surface isThe denominator must give a nonnegative squared speed, and the calculation uses $r>0$. At the polar origin a limiting Cartesian description is appropriate.

For the paraboloid and Archimedean spiral, putThen, for $\varphi >0$,The branch tending to $\varphi =\infty$ has positive angular velocity, henceSince $u=ϵ\dot{\varphi }\sqrt{1+{\varphi }^2}$, solve the azimuthal equation for the required force:This is positive for $\varphi >0$, consistent with a forward drive. Taking the limit gives

These are the large-time limits of the printed projected equations. Their mechanical approximation has a precise range limitation: on the exact surface, $z=h(r)$ gives $\dot{z}=(2r/\ell )\dot{r}$, which along this solution grows like $2{ϵ}^2\alpha \varphi /\ell$. At fixed positive $ϵ$, it is not small as $\varphi \to \infty$. Thus the requested limits are formal limits of that reduced model; neglect of vertical motion is not a uniform approximation to the full three-dimensional motion all the way to infinity.

Take rightward velocities as positive just before the right-wall collision. The incoming particle velocity is $v$ and the wall velocity is $-V$. Their total momentum divided by total mass gives the centre of mass velocityIn an elastic collision, relative velocity reverses, so the particle's signed outgoing velocity is $v_{\mathrm{out}}=2v_{\mathrm{cm}}-v$. For $M>m$ it is negative, and its speed isConsequently the exact change in speed isFor $m/M\to 0$ with $v,V$ fixed, this proves the requested leading increment $v^{\prime }-v\simeq 2V$. Reflection gives the same increment at the left wall.

This approximation is not uniform when $v/V$ is allowed to become arbitrarily large. To neglect recoil relative to the increment $2V$ requiresThe inequalities $m\ll M$ and $v\gg V$ alone do not imply it: for example, $m/M=10^{-3}$ and $v/V=10^3$ give an exact zero speed increment. The subsequent slowly moving-wall approximation therefore uses the consistent joint range $1\ll v/V\ll M/m$, or treats the walls as effectively prescribed massive reflectors. The assumed slow change of wall speed over many impacts embodies the same negligible-recoil requirement.

Within this approximation, the separation derivative is the right-wall velocity minus the left-wall velocity:For a time window containing many crossings but little separation change, $\ell /v\ll \Delta t\ll \ell /V$, the flight time between successive wall collisions is approximately $\ell /v$. Thus their number and the cumulative speed change arePassing to the averaged differential equation givesHence the particle-speed invariant between slowly approaching walls isIt is an adiabatic invariant for the rapid elastic bouncing motion while the separation and wall velocities vary slowly on the flight-time scale.

Label the initially left-hand rod $A$ and the right-hand rod $B$. At impact their centres are $(0,\ell )$ and $(0,-\ell )$, and their contact points are both the origin. Each rod has total mass $2m$ and moment of inertiaLet the impulse on $B$ be $+J{\mathbf{e}}_x$, so the impulse on $A$ is $-J{\mathbf{e}}_x$. The impulsive form of Newton's second law givesThe contact lever arms from the centres are $(0,-\ell )$ for $A$ and $(0,+\ell )$ for $B$. Both angular impulses are $-\ell J{\mathbf{e}}_z$. Thus, taking counterclockwise rotation as positive,Equal and opposite linear impulses therefore produce equal clockwise rotations, not opposite rotations.

The restitution law uses the velocities of the contacting endpoints, including the rotational terms. For $A$ that velocity isand for $B$ it is $u_B=-V+J/m$. The approach speed before impact is $2V$. The coefficient of restitution $e$ therefore givesSubstituting into the centre and angular velocities yields the endpoint collision of two freely rotating equal rods:For the first, perfectly elastic case, $e=1$, soAll initial translational energy has become rotational energy. Indeed the total initial kinetic energy is $2m{V}^2$, while the final energy for general $e$ isThe loss is $m{V}^2(1-e^2)$, zero for an elastic collision. Conservation of total angular momentum about the origin provides another check: initially it is $-4m\ell V$; after collision the centre-motion contribution is $-2m\ell V(1-e)$ and the spins contribute $-2m\ell V(1+e)$, with the same total. The initial distance $d$ determines when the collision occurs but does not enter the impulsive velocities.

With the prescribed magnetic-only Lorentz force $m\ddot{\mathbf{r}}=q\dot{\mathbf{r}}\times \mathbf{B}$, the component equations areDifferentiate the squared planar speed:Thus $V=\sqrt{{\dot{x}}^2+{\dot{y}}^2}$ is constant, since the Lorentz force is perpendicular to the velocity.

For $V>0$, introduce the velocity angle $\theta$ by $\dot{x}=V\cos \theta$, $\dot{y}=V\sin \theta$. The two planar equations imply $\dot{\theta }=-q{B}_z(t)/m$. Therefore the velocity rotation in a time-dependent axial magnetic field has phaseEquivalently, the complex velocity satisfies $\frac{d}{dt}(\dot{x}+i\dot{y})=-iq{B}_z(t)(\dot{x}+i\dot{y})/m$, giving the same integrated phase. Integrating the velocities and $\ddot{z}=0$ provesThe constants $x_0,y_0,z_0$ are the initial position coordinates, $v_z$ is the constant velocity parallel to the field, $V\ge 0$ is the initial planar speed, and $\varphi$ is the initial planar-velocity direction modulo $2\pi$. Together they specify the initial position and velocity. If $V=0$, the planar position stays fixed and the angle $\varphi$ is immaterial.

For $B_z(t)=\beta t$, the inner integral gives $\theta (t)=-a{t}^2+\varphi$, with $a=q\beta /(2m)>0$. Under the specified initial data,Rescale $u=\sqrt{a}s$. The given Fresnel integrals then giveHence the limiting position isThe negative $y$ coordinate follows from clockwise rotation of planar velocity for positive charge and positive $B_z$. The position converges through cancellation of increasingly rapid oscillations; its convergence does not mean the constant planar speed tends to zero.