• # Paper 4 , Section I, E

Consider functions $f: X \rightarrow Y$ and $g: Y \rightarrow X$. Which of the following statements are always true, and which can be false? Give proofs or counterexamples as appropriate.

(i) If $g \circ f$ is surjective then $f$ is surjective.

(ii) If $g \circ f$ is injective then $f$ is injective.

(iii) If $g \circ f$ is injective then $g$ is injective.

If $X=\{1, \ldots, m\}$ and $Y=\{1, \ldots, n\}$ with $m, and $g \circ f$ is the identity on $X$, then how many possibilities are there for the pair of functions $f$ and $g$ ?

comment
• # Paper 4, Section I, $2 E$

The Fibonacci numbers $F_{n}$ are defined by $F_{1}=1, F_{2}=1, F_{n+2}=F_{n+1}+F_{n}(n \geqslant 1)$. Let $a_{n}=F_{n+1} / F_{n}$ be the ratio of successive Fibonacci numbers.

(i) Show that $a_{n+1}=1+1 / a_{n}$. Hence prove by induction that

$(-1)^{n} a_{n+2} \leqslant(-1)^{n} a_{n}$

for all $n \geqslant 1$. Deduce that the sequence $a_{2 n}$ is monotonically decreasing.

(ii) Prove that

$F_{n+2} F_{n}-F_{n+1}^{2}=(-1)^{n+1}$

for all $n \geqslant 1$. Hence show that $a_{n+1}-a_{n} \rightarrow 0$ as $n \rightarrow \infty$.

(iii) Explain without detailed justification why the sequence $a_{n}$ has a limit.

comment
• # Paper 4, Section II, $6 \mathrm{E}$

(a) (i) By considering Euclid's algorithm, show that the highest common factor of two positive integers $a$ and $b$ can be written in the form $\alpha a+\beta b$ for suitable integers $\alpha$ and $\beta$. Find an integer solution of

$15 x+21 y+35 z=1$

(ii) Suppose that $n$ and $m$ are coprime. Show that the simultaneous congruences

$\begin{array}{ll} x \equiv a & (\bmod n) \\ x \equiv b & (\bmod m) \end{array}$

have the same set of solutions as $x \equiv c(\bmod m n)$ for some $c \in \mathbb{N}$. Hence solve (i.e. find all solutions of) the simultaneous congruences

$\begin{array}{ll} 3 x \equiv 1 & (\bmod 5) \\ 5 x \equiv 1 & (\bmod 7) \\ 7 x \equiv 1 & (\bmod 3) \end{array}$

(b) State the inclusion-exclusion principle.

For integers $r, n \geqslant 1$, denote by $\phi_{r}(n)$ the number of ordered r-tuples $\left(x_{1}, \ldots, x_{r}\right)$ of integers $x_{i}$ satisfying $1 \leqslant x_{i} \leqslant n$ for $i=1, \ldots, r$ and such that the greatest common divisor of $\left\{n, x_{1}, \ldots, x_{r}\right\}$ is 1 . Show that

$\phi_{r}(n)=n^{r} \prod_{p \mid n}\left(1-\frac{1}{p^{r}}\right)$

where the product is over all prime numbers $p$ dividing $n$.

comment
• # Paper 4, Section II, $7 \mathrm{E}$

(a) Prove that every real number $\alpha \in(0,1]$ can be written in the form $\alpha=$ $\sum_{n=1}^{\infty} 2^{-b_{n}}$ where $\left(b_{n}\right)$ is a strictly increasing sequence of positive integers.

Are such expressions unique?

(b) Let $\theta \in \mathbb{R}$ be a root of $f(x)=\alpha_{d} x^{d}+\cdots+\alpha_{1} x+\alpha_{0}$, where $\alpha_{0}, \ldots, \alpha_{d} \in \mathbb{Z}$. Suppose that $f$ has no rational roots, except possibly $\theta$.

(i) Show that if $s, t \in \mathbb{R}$ then

$|f(s)-f(t)| \leqslant A(\max \{|s|,|t|, 1\})^{d-1}|s-t| .$

where $A$ is a constant depending only on $f$.

(ii) Deduce that if $p, q \in \mathbb{Z}$ with $q>0$ and $0<\left|\theta-\frac{p}{q}\right|<1$ then

$\left|\theta-\frac{p}{q}\right| \geqslant \frac{1}{A}\left(\frac{1}{|\theta|+1}\right)^{d-1} \frac{1}{q^{d}} .$

(c) Prove that $\alpha=\sum_{n=1}^{\infty} 2^{-n !}$ is transcendental.

(d) Let $\beta$ and $\gamma$ be transcendental numbers. What of the following statements are always true and which can be false? Briefly justify your answers.

(i) $\beta \gamma$ is transcendental.

(ii) $\beta^{n}$ is transcendental for every $n \in \mathbb{N}$.

comment
• # Paper 4, Section II, 8E

(a) Prove that a countable union of countable sets is countable.

(b) (i) Show that the set $\mathbb{N}^{\mathbb{N}}$ of all functions $\mathbb{N} \rightarrow \mathbb{N}$ is uncountable.

(ii) Determine the countability or otherwise of each of the two sets

\begin{aligned} &A=\left\{f \in \mathbb{N}^{\mathbb{N}}: f(n) \leqslant f(n+1) \text { for all } n \in \mathbb{N}\right\}, \\ &B=\left\{f \in \mathbb{N}^{\mathbb{N}}: f(n) \geqslant f(n+1) \text { for all } n \in \mathbb{N}\right\} \end{aligned}

(c) A permutation $\sigma$ of the natural numbers $\mathbb{N}$ is a mapping $\sigma \in \mathbb{N}^{\mathbb{N}}$ that is bijective. Determine the countability or otherwise of each of the two sets $C$ and $D$ of permutations, justifying your answers:

(i) $C$ is the set of all permutations $\sigma$ of $\mathbb{N}$ such that $\sigma(j)=j$ for all sufficiently large $j$.

(ii) $D$ is the set all permutations $\sigma$ of $\mathbb{N}$ such that

$\sigma(j)=j-1 \text { or } j \text { or } j+1$

for each $j$.

comment
• # Paper 4, Section II, E

(a) Let $S$ be the set of all functions $f: \mathbb{N} \rightarrow \mathbb{R}$. Define $\delta: S \rightarrow S$ by

$(\delta f)(n)=f(n+1)-f(n)$

(i) Define the binomial coefficient $\left(\begin{array}{l}n \\ r\end{array}\right)$ for $0 \leqslant r \leqslant n$. Setting $\left(\begin{array}{l}n \\ r\end{array}\right)=0$ when $r>n$, prove from your definition that if $f_{r}(n)=\left(\begin{array}{l}n \\ r\end{array}\right)$ then $\delta f_{r}=f_{r-1}$.

(ii) Show that if $f \in S$ is integer-valued and $\delta^{k+1} f=0$, then

$f(n)=c_{0}\left(\begin{array}{l} n \\ k \end{array}\right)+c_{1}\left(\begin{array}{c} n \\ k-1 \end{array}\right)+\cdots+c_{k-1}\left(\begin{array}{l} n \\ 1 \end{array}\right)+c_{k}$

for some integers $c_{0}, \ldots, c_{k}$.

(b) State the binomial theorem. Show that

$\sum_{r=0}^{n}(-1)^{r}\left(\begin{array}{l} n \\ r \end{array}\right)^{2}=\left\{\begin{array}{cl} 0 & \text { if } n \text { is odd } \\ (-1)^{n / 2}\left(\begin{array}{c} n \\ n / 2 \end{array}\right) & \text { if } n \text { is even } \end{array}\right.$

comment

• # Paper 2, Section I, $2 \mathrm{D}$

Define an equivalence relation. Which of the following is an equivalence relation on the set of non-zero complex numbers? Justify your answers. (i) $x \sim y$ if $|x-y|^{2}<|x|^{2}+|y|^{2}$. (ii) $x \sim y$ if $|x+y|=|x|+|y|$. (iii) $x \sim y$ if $\left|\frac{x}{y^{n}}\right|$ is rational for some integer $n \geqslant 1$. (iv) $x \sim y$ if $\left|x^{3}-x\right|=\left|y^{3}-y\right|$.

comment
• # Paper 2, Section II, D

(a) Define what it means for a set to be countable. Prove that $\mathbb{N} \times \mathbb{Z}$ is countable, and that the power set of $\mathbb{N}$ is uncountable.

(b) Let $\sigma: X \rightarrow Y$ be a bijection. Show that if $f: X \rightarrow X$ and $g: Y \rightarrow Y$ are related by $g=\sigma f \sigma^{-1}$ then they have the same number of fixed points.

[A fixed point of $f$ is an element $x \in X$ such that $f(x)=x$.]

(c) Let $T$ be the set of bijections $f: \mathbb{N} \rightarrow \mathbb{N}$ with the property that no iterate of $f$ has a fixed point.

[The $k^{\text {th }}$iterate of $f$ is the map obtained by $k$ successive applications of $f$.]

(i) Write down an explicit element of $T$.

(ii) Determine whether $T$ is countable or uncountable.

comment
• # Paper 2, Section II, D

(a) Define the Euler function $\phi(n)$. State the Chinese remainder theorem, and use it to derive a formula for $\phi(n)$ when $n=p_{1} p_{2} \ldots p_{r}$ is a product of distinct primes. Show that there are at least ten odd numbers $n$ with $\phi(n)$ a power of 2 .

(b) State and prove the Fermat-Euler theorem.

(c) In the RSA cryptosystem a message $m \in\{1,2, \ldots, N-1\}$ is encrypted as $c=m^{e}$ $(\bmod N)$. Explain how $N$ and $e$ should be chosen, and how (given a factorisation of $N$ ) to compute the decryption exponent $d$. Prove that your choice of $d$ works, subject to reasonable assumptions on $m$. If $N=187$ and $e=13$ then what is $d$ ?

comment

• # Paper 4, Section $I$, E

Show that the series

$\sum_{n=1}^{\infty} \frac{1}{n^{2}+n} \quad \text { and } \quad \sum_{n=1}^{\infty} \frac{1}{(2 n-1) !}$

converge. Determine in each case whether the limit is a rational number. Justify your answers.

comment
• # Paper 4, Section I, E

Find all solutions to the simultaneous congruences

$4 x \equiv 1 \quad(\bmod 21) \quad \text { and } \quad 2 x \equiv 5 \quad(\bmod 45)$

comment
• # Paper 4, Section II, $7 \mathrm{E}$

(a) Let $f: X \rightarrow Y$ be a function. Show that the following statements are equivalent.

(i) $f$ is injective.

(ii) For every subset $A \subset X$ we have $f^{-1}(f(A))=A$.

(iii) For every pair of subsets $A, B \subset X$ we have $f(A \cap B)=f(A) \cap f(B)$.

(b) Let $f: X \rightarrow X$ be an injection. Show that $X=A \cup B$ for some subsets $A, B \subset X$ such that

$\bigcap_{n=1}^{\infty} f^{n}(A)=\emptyset \quad \text { and } \quad f(B)=B$

[Here $f^{n}$ denotes the $n$-fold composite of $f$ with itself.]

comment
• # Paper 4, Section II, E

(a) What is a countable set? Let $X, A, B$ be sets with $A, B$ countable. Show that if $f: X \rightarrow A \times B$ is an injection then $X$ is countable. Deduce that $\mathbb{Z}$ and $\mathbb{Q}$ are countable. Show too that a countable union of countable sets is countable.

(b) Show that, in the plane, any collection of pairwise disjoint circles with rational radius is countable.

(c) A lollipop is any subset of the plane obtained by translating, rotating and scaling (by any factor $\lambda>0$ ) the set

$\left\{(x, y) \in \mathbb{R}^{2} \mid x^{2}+y^{2}=1\right\} \cup\left\{(0, y) \in \mathbb{R}^{2} \mid-3 \leqslant y \leqslant-1\right\} .$

What happens if in part (b) we replace 'circles with rational radius' by 'lollipops'?

comment
• # Paper 4, Section II, E

State the inclusion-exclusion principle.

Let $n \geqslant 2$ be an integer. Let $X=\{0,1,2, \ldots, n-1\}$ and

$Y=\left\{(a, b) \in X^{2} \mid \operatorname{gcd}(a, b, n)=1\right\}$

where $\operatorname{gcd}\left(x_{1}, \ldots, x_{k}\right)$ is the largest number dividing all of $x_{1}, \ldots, x_{k}$. Let $R$ be the relation on $Y$ where $(a, b) R(c, d)$ if $a d-b c \equiv 0(\bmod n)$.

(a) Show that

$|Y|=n^{2} \prod_{p \mid n}\left(1-\frac{1}{p^{2}}\right)$

where the product is over all primes $p$ dividing $n$.

(b) Show that if $\operatorname{gcd}(a, b, n)=1$ then there exist integers $r, s, t$ with $r a+s b+t n=1$.

(c) Show that if $(a, b) R(c, d)$ then there exists an integer $\lambda$ with $\lambda a \equiv c(\bmod n)$ and $\lambda b \equiv d(\bmod n)$. [Hint: Consider $\lambda=r c+s d$, where $r, s$ are as in part (b).] Deduce that $R$ is an equivalence relation.

(d) What is the size of the equivalence class containing $(1,1) ?$ Show that all equivalence classes have the same size, and deduce that the number of equivalence classes is

$n \prod_{p \mid n}\left(1+\frac{1}{p}\right) \text {. }$

comment
• # Paper 4, Section II, E

(a) State and prove Fermat's theorem. Use it to compute $3^{803}(\bmod 17)$.

(b) The Fibonacci numbers $F_{0}, F_{1}, F_{2}, \ldots$ are defined by $F_{0}=0, F_{1}=1$, and $F_{n}=F_{n-1}+F_{n-2}$ for all $n \geqslant 2$. Prove by induction that for all $n \geqslant 1$ we have

$F_{2 n}=F_{n}\left(F_{n-1}+F_{n+1}\right) \quad \text { and } \quad F_{2 n+1}=F_{n}^{2}+F_{n+1}^{2}$

(c) Let $m \geqslant 1$ and let $p$ be an odd prime dividing $F_{m}$. Which of the following statements are true, and which can be false? Justify your answers.

(i) If $m$ is odd then $p \equiv 1(\bmod 4)$.

(ii) If $m$ is even then $p \equiv 3(\bmod 4)$.

comment

• # Paper 4, Section I, E

Given $n \in \mathbb{N}$, show that $\sqrt{n}$ is either an integer or irrational.

Let $\alpha$ and $\beta$ be irrational numbers and $q$ be rational. Which of $\alpha+q, \alpha+\beta, \alpha \beta, \alpha^{q}$ and $\alpha^{\beta}$ must be irrational? Justify your answers. [Hint: For the last part consider $\sqrt{2}^{\sqrt{2}}$.]

comment
• # Paper 4, Section I, E

State Fermat's theorem.

Let $p$ be a prime such that $p \equiv 3(\bmod 4)$. Prove that there is no solution to $x^{2} \equiv-1(\bmod p) .$

Show that there are infinitely many primes congruent to $1(\bmod 4)$.

comment
• # Paper 4, Section II, $5 E$

Let $n$ be a positive integer. Show that for any $a$ coprime to $n$, there is a unique $b$ $(\bmod n)$ such that $a b \equiv 1(\bmod n)$. Show also that if $a$ and $b$ are integers coprime to $n$, then $a b$ is also coprime to $n$. [Any version of Bezout's theorem may be used without proof provided it is clearly stated.]

State and prove Wilson's theorem.

Let $n$ be a positive integer and $p$ be a prime. Show that the exponent of $p$ in the prime factorisation of $n$ ! is given by $\sum_{i=1}^{\infty}\left\lfloor\frac{n}{p^{2}}\right\rfloor$ where $\lfloor x\rfloor$ denotes the integer part of $x$.

Evaluate $20! \mod 23$ and $100! \mod 10^{249}$

Let $p$ be a prime and $0. Let $\ell$ be the exponent of $p$ in the prime factorisation of $k$. Find the exponent of $p$ in the prime factorisation of $\left(\begin{array}{c}p^{m} \\ k\end{array}\right)$, in terms of $m$ and $\ell$.

comment
• # Paper 4, Section II, $7 \mathrm{E}$

Let $n \in \mathbb{N}$ and $A_{1}, \ldots, A_{n}$ be subsets of a finite set $X$. Let $0 \leqslant t \leqslant n$. Show that if $x \in X$ belongs to $A_{i}$ for exactly $m$ values of $i$, then

$\sum_{S \subset\{1, \ldots, n\}}\left(\begin{array}{c} |S| \\ t \end{array}\right)(-1)^{|S|-t} \mathbf{1}_{A_{S}}(x)= \begin{cases}0 & \text { if } m \neq t \\ 1 & \text { if } m=t\end{cases}$

where $A_{S}=\bigcap_{i \in S} A_{i}$ with the convention that $A_{\emptyset}=X$, and $\mathbf{1}_{A_{S}}$ denotes the indicator function of $A_{S} \cdot\left[\right.$ Hint: Set $M=\left\{i: x \in A_{i}\right\}$ and consider for which $S \subset\{1, \ldots, n\}$ one has $\mathbf{1}_{A_{S}}(x)=1$.]

Use this to show that the number of elements of $X$ that belong to $A_{i}$ for exactly $t$ values of $i$ is

$\sum_{S \subset\{1, \ldots, n\}}\left(\begin{array}{c} |S| \\ t \end{array}\right)(-1)^{|S|-t}\left|A_{S}\right| .$

Deduce the Inclusion-Exclusion Principle.

Using the Inclusion-Exclusion Principle, prove a formula for the Euler totient function $\varphi(N)$ in terms of the distinct prime factors of $N$.

A Carmichael number is a composite number $n$ such that $x^{n-1} \equiv 1(\bmod n)$ for every integer $x$ coprime to $n$. Show that if $n=q_{1} q_{2} \ldots q_{k}$ is the product of $k \geqslant 2$ distinct primes $q_{1}, \ldots, q_{k}$ satisfying $q_{j}-1 \mid n-1$ for $j=1, \ldots, k$, then $n$ is a Carmichael number.

comment
• # Paper 4, Section II, 8E

Define what it means for a set to be countable.

Show that for any set $X$, there is no surjection from $X$ onto the power set $\mathcal{P}(X)$. Deduce that the set $\{0,1\}^{\mathbb{N}}$ of all infinite $0-1$ sequences is uncountable.

Let $\mathcal{L}$ be the set of sequences $\left(F_{n}\right)_{n=0}^{\infty}$ of subsets $F_{0} \subset F_{1} \subset F_{2} \subset \ldots$ of $\mathbb{N}$ such that $\left|F_{n}\right|=n$ for all $n \in \mathbb{N}$ and $\bigcup_{n} F_{n}=\mathbb{N}$. Let $\mathcal{L}_{0}$ consist of all members $\left(F_{n}\right)_{n=0}^{\infty}$ of $\mathcal{L}$ for which $n \in F_{n}$ for all but finitely many $n \in \mathbb{N}$. Let $\mathcal{L}_{1}$ consist of all members $\left(F_{n}\right)_{n=0}^{\infty}$ of $\mathcal{L}$ for which $n \in F_{n+1}$ for all but finitely many $n \in \mathbb{N}$. For each of $\mathcal{L}_{0}$ and $\mathcal{L}_{1}$ determine whether it is countable or uncountable. Justify your answers.

comment
• # Paper 4, Section II, E

For $n \in \mathbb{N}$ let $Q_{n}=\{0,1\}^{n}$ denote the set of all $0-1$ sequences of length $n$. We define the distance $d(x, y)$ between two elements $x$ and $y$ of $Q_{n}$ to be the number of coordinates in which they differ. Show that $d(x, z) \leqslant d(x, y)+d(y, z)$ for all $x, y, z \in Q_{n}$.

For $x \in Q_{n}$ and $1 \leqslant j \leqslant n$ let $B(x, j)=\left\{y \in Q_{n}: d(y, x) \leqslant j\right\}$. Show that $|B(x, j)|=\sum_{i=0}^{j}\left(\begin{array}{c}n \\ i\end{array}\right)$.

A subset $C$ of $Q_{n}$ is called a $k$-code if $d(x, y) \geqslant 2 k+1$ for all $x, y \in C$ with $x \neq y$. Let $M(n, k)$ be the maximum possible value of $|C|$ for a $k$-code $C$ in $Q_{n}$. Show that

$2^{n}\left(\sum_{i=0}^{2 k}\left(\begin{array}{c} n \\ i \end{array}\right)\right)^{-1} \leqslant M(n, k) \leqslant 2^{n}\left(\sum_{i=0}^{k}\left(\begin{array}{l} n \\ i \end{array}\right)\right)^{-1}$

Find $M(4,1)$, carefully justifying your answer.

comment

• # Paper 4, Section I, D

(a) Give the definitions of relation and equivalence relation on a set $S$.

(b) Let $\Sigma$ be the set of ordered pairs $(A, f)$ where $A$ is a non-empty subset of $\mathbb{R}$ and $f: A \rightarrow \mathbb{R}$. Let $\mathcal{R}$ be the relation on $\Sigma$ defined by requiring $(A, f) \mathcal{R}(B, g)$ if the following two conditions hold:

(i) $(A \backslash B) \cup(B \backslash A)$ is finite and

(ii) there is a finite set $F \subset A \cap B$ such that $f(x)=g(x)$ for all $x \in A \cap B \backslash F$.

Show that $\mathcal{R}$ is an equivalence relation on $\Sigma$.

comment
• # Paper 4, Section I, D

(a) Show that for all positive integers $z$ and $n$, either $z^{2 n} \equiv 0(\bmod 3)$ or $z^{2 n} \equiv 1(\bmod 3)$.

(b) If the positive integers $x, y, z$ satisfy $x^{2}+y^{2}=z^{2}$, show that at least one of $x$ and $y$ must be divisible by 3 . Can both $x$ and $y$ be odd?

comment
• # Paper 4, Section II, 7D

(a) For positive integers $n, m, k$ with $k \leqslant n$, show that

$\left(\begin{array}{l} n \\ k \end{array}\right)\left(\frac{k}{n}\right)^{m}=\left(\begin{array}{l} n-1 \\ k-1 \end{array}\right) \sum_{\ell=0}^{m-1} a_{n, m, \ell}\left(\frac{k-1}{n-1}\right)^{m-1-\ell}$

giving an explicit formula for $a_{n, m, \ell}$. [You may wish to consider the expansion of $\left.\left(\frac{k-1}{n-1}+\frac{1}{n-1}\right)^{m-1} .\right]$

(b) For a function $f:[0,1] \rightarrow \mathbb{R}$ and each integer $n \geqslant 1$, the function $B_{n}(f):[0,1] \rightarrow \mathbb{R}$ is defined by

$B_{n}(f)(x)=\sum_{k=0}^{n} f\left(\frac{k}{n}\right)\left(\begin{array}{l} n \\ k \end{array}\right) x^{k}(1-x)^{n-k}$

For any integer $m \geqslant 0$ let $f_{m}(x)=x^{m}$. Show that $B_{n}\left(f_{0}\right)(x)=1$ and $B_{n}\left(f_{1}\right)(x)=x$ for all $n \geqslant 1$ and $x \in[0,1]$.

Show that for each integer $m \geqslant 0$ and each $x \in[0,1]$,

$B_{n}\left(f_{m}\right)(x) \rightarrow f_{m}(x) \text { as } n \rightarrow \infty$

Deduce that for each integer $m \geqslant 0$,

$\lim _{n \rightarrow \infty} \frac{1}{4^{n}} \sum_{k=0}^{2 n}\left(\frac{k}{n}\right)^{m}\left(\begin{array}{c} 2 n \\ k \end{array}\right)=1$

comment
• # Paper 4, Section II, D

Let $\left(a_{k}\right)_{k=1}^{\infty}$ be a sequence of real numbers.

(a) Define what it means for $\left(a_{k}\right)_{k=1}^{\infty}$ to converge. Define what it means for the series $\sum_{k=1}^{\infty} a_{k}$ to converge.

Show that if $\sum_{k=1}^{\infty} a_{k}$ converges, then $\left(a_{k}\right)_{k=1}^{\infty}$ converges to 0 .

If $\left(a_{k}\right)_{k=1}^{\infty}$ converges to $a \in \mathbb{R}$, show that

$\lim _{n \rightarrow \infty} \frac{1}{n} \sum_{k=1}^{n} a_{k}=a$

(b) Suppose $a_{k}>0$ for every $k$. Let $u_{n}=\sum_{k=1}^{n}\left(a_{k}+\frac{1}{a_{k}}\right)$ and $v_{n}=\sum_{k=1}^{n}\left(a_{k}-\frac{1}{a_{k}}\right)$.

Show that $\left(u_{n}\right)_{n=1}^{\infty}$ does not converge.

Give an example of a sequence $\left(a_{k}\right)_{k=1}^{\infty}$ with $a_{k}>0$ and $a_{k} \neq 1$ for every $k$ such that $\left(v_{n}\right)_{n=1}^{\infty}$ converges.

If $\left(v_{n}\right)_{n=1}^{\infty}$ converges, show that $\frac{u_{n}}{n} \rightarrow 2$.

comment
• # Paper 4, Section II, D

(a) Define what it means for a set to be countable.

(b) Let $A$ be an infinite subset of the set of natural numbers $\mathbb{N}=\{0,1,2, \ldots\}$. Prove that there is a bijection $f: \mathbb{N} \rightarrow A$.

(c) Let $A_{n}$ be the set of natural numbers whose decimal representation ends with exactly $n-1$ zeros. For example, $71 \in A_{1}, 70 \in A_{2}$ and $15000 \in A_{4}$. By applying the result of part (b) with $A=A_{n}$, construct a bijection $g: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$. Deduce that the set of rationals is countable.

(d) Let $A$ be an infinite set of positive real numbers. If every sequence $\left(a_{j}\right)_{j=1}^{\infty}$ of distinct elements with $a_{j} \in A$ for each $j$ has the property that

$\lim _{N \rightarrow \infty} \frac{1}{N} \sum_{j=1}^{N} a_{j}=0$

prove that $A$ is countable.

[You may assume without proof that a countable union of countable sets is countable.]

comment
• # Paper 4, Section II, D

(a) State and prove the Fermat-Euler Theorem. Deduce Fermat's Little Theorem. State Wilson's Theorem.

(b) Let $p$ be an odd prime. Prove that $X^{2} \equiv-1(\bmod p)$ is solvable if and only if $p \equiv 1(\bmod 4)$.

(c) Let $p$ be prime. If $h$ and $k$ are non-negative integers with $h+k=p-1$, prove that $h ! k !+(-1)^{h} \equiv 0(\bmod p) .$

comment

• # Paper 4, Section I, E

Explain the meaning of the phrase least upper bound; state the least upper bound property of the real numbers. Use the least upper bound property to show that a bounded, increasing sequence of real numbers converges.

Suppose that $a_{n}, b_{n} \in \mathbb{R}$ and that $a_{n} \geqslant b_{n}>0$ for all $n$. If $\sum_{n=1}^{\infty} a_{n}$ converges, show that $\sum_{n=1}^{\infty} b_{n}$ converges.

comment
• # Paper 4, Section I, E

Find a pair of integers $x$ and $y$ satisfying $17 x+29 y=1$. What is the smallest positive integer congruent to $17^{138}$ modulo 29 ?

comment
• # Paper 4, Section II, $6 \mathrm{E}$

Suppose that $a, b \in \mathbb{Z}$ and that $b=b_{1} b_{2}$, where $b_{1}$ and $b_{2}$ are relatively prime and greater than 1. Show that there exist unique integers $a_{1}, a_{2}, n \in \mathbb{Z}$ such that $0 \leqslant a_{i} and

$\frac{a}{b}=\frac{a_{1}}{b_{1}}+\frac{a_{2}}{b_{2}}+n$

Now let $b=p_{1}^{n_{1}} \cdots p_{k}^{n_{k}}$ be the prime factorization of $b$. Deduce that $\frac{a}{b}$ can be written uniquely in the form

$\frac{a}{b}=\frac{q_{1}}{p_{1}^{n_{1}}}+\cdots+\frac{q_{k}}{p_{k}^{n_{k}}}+n$

where $0 \leqslant q_{i} and $n \in \mathbb{Z}$. Express $\frac{a}{b}=\frac{1}{315}$ in this form.

comment
• # Paper 4, Section II, $7 \mathrm{E}$

State the inclusion-exclusion principle.

Let $A=\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ be a string of $n$ digits, where $a_{i} \in\{0,1, \ldots, 9\}$. We say that the string $A$ has a run of length $k$ if there is some $j \leqslant n-k+1$ such that either $a_{j+i} \equiv a_{j}+i(\bmod 10)$ for all $0 \leqslant i or $a_{j+i} \equiv a_{j}-i(\bmod 10)$ for all $0 \leqslant i. For example, the strings

$(\underline{0,1,2}, 8,4,9),(3, \underline{9,8,7}, 4,8) \text { and }(3, \underline{1,0,9}, 4,5)$

all have runs of length 3 (underlined), but no run in $(3,1,2,1,1,2)$ has length $>2$. How many strings of length 6 have a run of length $\geqslant 3$ ?

comment
• # Paper 4, Section II, 8E

Define the binomial coefficient $\left(\begin{array}{c}n \\ m\end{array}\right)$. Prove directly from your definition that

$(1+z)^{n}=\sum_{m=0}^{n}\left(\begin{array}{c} n \\ m \end{array}\right) z^{m}$

for any complex number $z$.

(a) Using this formula, or otherwise, show that

$\sum_{k=0}^{3 n}(-3)^{k}\left(\begin{array}{l} 6 n \\ 2 k \end{array}\right)=2^{6 n}$

(b) By differentiating, or otherwise, evaluate $\sum_{m=0}^{n} m\left(\begin{array}{c}n \\ m\end{array}\right)$.

Let $S_{r}(n)=\sum_{m=0}^{n}(-1)^{m} m^{r}\left(\begin{array}{c}n \\ m\end{array}\right)$, where $r$ is a non-negative integer. Show that $S_{r}(n)=0$ for $r. Evaluate $S_{n}(n)$.

comment
• # Paper 4, Section II, E

(a) Let $S$ be a set. Show that there is no bijective map from $S$ to the power set of $S$. Let $\mathcal{T}=\left\{\left(x_{n}\right) \mid x_{i} \in\{0,1\}\right.$ for all $\left.i \in \mathbb{N}\right\}$ be the set of sequences with entries in $\{0,1\} .$ Show that $\mathcal{T}$ is uncountable.

(b) Let $A$ be a finite set with more than one element, and let $B$ be a countably infinite set. Determine whether each of the following sets is countable. Justify your answers.

(i) $S_{1}=\{f: A \rightarrow B \mid f$ is injective $\}$.

(ii) $S_{2}=\{g: B \rightarrow A \mid g$ is surjective $\}$.

(iii) $S_{3}=\{h: B \rightarrow B \mid h$ is bijective $\}$.

comment

• # Paper 4 , Section I, E

State the Chinese remainder theorem and Fermat's theorem. Prove that

$p^{4} \equiv 1 \quad(\bmod 240)$

for any prime $p>5$.

comment
• # Paper 4, Section I, E

(a) Find all integers $x$ and $y$ such that

$6 x+2 y \equiv 3 \quad(\bmod 53) \quad \text { and } \quad 17 x+4 y \equiv 7 \quad(\bmod 53)$

(b) Show that if an integer $n>4$ is composite then $(n-1) ! \equiv 0(\bmod n)$.

comment
• # Paper 4, Section II, E

What does it mean for a set to be countable? Prove that

(a) if $B$ is countable and $f: A \rightarrow B$ is injective, then $A$ is countable;

(b) if $A$ is countable and $f: A \rightarrow B$ is surjective, then $B$ is countable.

Prove that $\mathbb{N} \times \mathbb{N}$ is countable, and deduce that

(i) if $X$ and $Y$ are countable, then so is $X \times Y$;

(ii) $\mathbb{Q}$ is countable.

Let $\mathcal{C}$ be a collection of circles in the plane such that for each point $a$ on the $x$-axis, there is a circle in $\mathcal{C}$ passing through the point $a$ which has the $x$-axis tangent to the circle at $a$. Show that $\mathcal{C}$ contains a pair of circles that intersect.

comment
• # Paper 4, Section II, E

State the inclusion-exclusion principle.

Let $n \in \mathbb{N}$. A permutation $\sigma$ of the set $\{1,2,3, \ldots, n\}$ is said to contain a transposition if there exist $i, j$ with $1 \leqslant i such that $\sigma(i)=j$ and $\sigma(j)=i$. Derive a formula for the number, $f(n)$, of permutations which do not contain a transposition, and show that

$\lim _{n \rightarrow \infty} \frac{f(n)}{n !}=e^{-\frac{1}{2}}$

comment
• # Paper 4, Section II, E

Let $p$ be a prime. A base $p$ expansion of an integer $k$ is an expression

$k=k_{0}+p \cdot k_{1}+p^{2} \cdot k_{2}+\cdots+p^{\ell} \cdot k_{\ell}$

for some natural number $\ell$, with $0 \leqslant k_{i} for $i=0,1, \ldots, \ell$.

(i) Show that the sequence of coefficients $k_{0}, k_{1}, k_{2}, \ldots, k_{\ell}$ appearing in a base $p$ expansion of $k$ is unique, up to extending the sequence by zeroes.

(ii) Show that

$\left(\begin{array}{l} p \\ j \end{array}\right) \equiv 0 \quad(\bmod p), \quad 0

and hence, by considering the polynomial $(1+x)^{p}$ or otherwise, deduce that

$\left(\begin{array}{c} p^{i} \\ j \end{array}\right) \equiv 0 \quad(\bmod p), \quad 0

(iii) If $n_{0}+p \cdot n_{1}+p^{2} \cdot n_{2}+\cdots+p^{\ell} \cdot n_{\ell}$ is a base $p$ expansion of $n$, then, by considering the polynomial $(1+x)^{n}$ or otherwise, show that

$\left(\begin{array}{l} n \\ k \end{array}\right) \equiv\left(\begin{array}{l} n_{0} \\ k_{0} \end{array}\right)\left(\begin{array}{l} n_{1} \\ k_{1} \end{array}\right) \cdots\left(\begin{array}{l} n_{\ell} \\ k_{\ell} \end{array}\right) \quad(\bmod p)$

comment
• # Paper 4, Section II, E

(i) Let $\sim$ be an equivalence relation on a set $X$. What is an equivalence class of $\sim$ ? What is a partition of $X ?$ Prove that the equivalence classes of $\sim$ form a partition of $X$.

(ii) Let $\sim$ be the relation on the natural numbers $\mathbb{N}=\{1,2,3, \ldots\}$ defined by

$m \sim n \Longleftrightarrow \exists a, b \in \mathbb{N} \text { such that } m \text { divides } n^{a} \text { and } n \text { divides } m^{b} .$

Show that $\sim$ is an equivalence relation, and show that it has infinitely many equivalence classes, all but one of which are infinite.

comment

• # Paper 4, Section I, $2 \mathrm{E}$

Define the binomial coefficients $\left(\begin{array}{l}n \\ k\end{array}\right)$, for integers $n, k$ satisfying $n \geqslant k \geqslant 0$. Prove directly from your definition that if $n>k \geqslant 0$ then

$\left(\begin{array}{l} n \\ k \end{array}\right)+\left(\begin{array}{c} n \\ k+1 \end{array}\right)=\left(\begin{array}{c} n+1 \\ k+1 \end{array}\right)$

and that for every $m \geqslant 0$ and $n \geqslant 0$,

$\sum_{k=0}^{m}\left(\begin{array}{c} n+k \\ k \end{array}\right)=\left(\begin{array}{c} n+m+1 \\ m \end{array}\right)$

comment
• # Paper 4, Section I, E

Use Euclid's algorithm to determine $d$, the greatest common divisor of 203 and 147 , and to express it in the form $203 x+147 y$ for integers $x, y$. Hence find all solutions in integers $x, y$ of the equation $203 x+147 y=d$.

How many integers $n$ are there with $1 \leqslant n \leqslant 2014$ and $21 n \equiv 25(\bmod 29) ?$

comment
• # Paper 4, Section II, E

(i) State and prove the Inclusion-Exclusion Principle.

(ii) Let $n>1$ be an integer. Denote by $\mathbb{Z} / n \mathbb{Z}$ the integers modulo $n$. Let $X$ be the set of all functions $f: \mathbb{Z} / n \mathbb{Z} \rightarrow \mathbb{Z} / n \mathbb{Z}$ such that for every $j \in \mathbb{Z} / n \mathbb{Z}, f(j)-f(j-1) \not \equiv j$ $(\bmod n)$. Show that

$|X|= \begin{cases}(n-1)^{n}+1-n & \text { if } n \text { is odd } \\ (n-1)^{n}-1 & \text { if } n \text { is even }\end{cases}$

comment
• # Paper 4, Section II, E

(i) What does it mean to say that a set $X$ is countable? Show directly that the set of sequences $\left(x_{n}\right)_{n \in \mathbb{N}}$, with $x_{n} \in\{0,1\}$ for all $n$, is uncountable.

(ii) Let $S$ be any subset of $\mathbb{N}$. Show that there exists a bijection $f: \mathbb{N} \rightarrow \mathbb{N}$ such that $f(S)=2 \mathbb{N}$ (the set of even natural numbers) if and only if both $S$ and its complement are infinite.

(iii) Let $\sqrt{2}=1 \cdot a_{1} a_{2} a_{3} \ldots$ be the binary expansion of $\sqrt{2}$. Let $X$ be the set of all sequences $\left(x_{n}\right)$ with $x_{n} \in\{0,1\}$ such that for infinitely many $n, x_{n}=0$. Let $Y$ be the set of all $\left(x_{n}\right) \in X$ such that for infinitely many $n, x_{n}=a_{n}$. Show that $Y$ is uncountable.

comment
• # Paper 4, Section II, E

(i) State and prove the Fermat-Euler Theorem.

(ii) Let $p$ be an odd prime number, and $x$ an integer coprime to $p$. Show that $x^{(p-1) / 2} \equiv \pm 1(\bmod p)$, and that if the congruence $y^{2} \equiv x(\bmod p)$ has a solution then $x^{(p-1) / 2} \equiv 1(\bmod p)$.

(iii) By arranging the residue classes coprime to $p$ into pairs $\{a, b x\}$ with $a b \equiv 1(\bmod p)$, or otherwise, show that if the congruence $y^{2} \equiv x(\bmod p)$ has no solution then $x^{(p-1) / 2} \equiv-1(\bmod p) .$

(iv) Show that $5^{5^{5}} \equiv 5(\bmod 23)$.

comment
• # Paper 4, Section II, E

What does it mean to say that the sequence of real numbers $\left(x_{n}\right)$ converges to the limit $x ?$ What does it mean to say that the series $\sum_{n=1}^{\infty} x_{n}$ converges to $s$ ?

Let $\sum_{n=1}^{\infty} a_{n}$ and $\sum_{n=1}^{\infty} b_{n}$ be convergent series of positive real numbers. Suppose that $\left(x_{n}\right)$ is a sequence of positive real numbers such that for every $n \geqslant 1$, either $x_{n} \leqslant a_{n}$ or $x_{n} \leqslant b_{n}$. Show that $\sum_{n=1}^{\infty} x_{n}$ is convergent.

Show that $\sum_{n=1}^{\infty} 1 / n^{2}$ is convergent, and that $\sum_{n=1}^{\infty} 1 / n^{\alpha}$ is divergent if $\alpha \leqslant 1$.

Let $\left(x_{n}\right)$ be a sequence of positive real numbers such that $\sum_{n=1}^{\infty} n^{2} x_{n}^{2}$ is convergent. Show that $\sum_{n=1}^{\infty} x_{n}$ is convergent. Determine (with proof or counterexample) whether or not the converse statement holds.

comment

• # Paper 4, Section I, E

Let $\left(x_{n}\right)_{n=1}^{\infty}$ be a sequence of real numbers. What does it mean to say that the sequence $\left(x_{n}\right)$ is convergent? What does it mean to say the series $\sum x_{n}$ is convergent? Show that if $\sum x_{n}$ is convergent, then the sequence $\left(x_{n}\right)$ converges to zero. Show that the converse is not necessarily true.

comment
• # Paper 4, Section I, E

Let $m$ and $n$ be positive integers. State what is meant by the greatest common divisor $\operatorname{gcd}(m, n)$ of $m$ and $n$, and show that there exist integers $a$ and $b$ such that $\operatorname{gcd}(m, n)=a m+b n$. Deduce that an integer $k$ divides both $m$ and $n$ only if $k$ divides $\operatorname{gcd}(m, n)$.

Prove (without using the Fundamental Theorem of Arithmetic) that for any positive integer $k, \operatorname{gcd}(k m, k n)=k \operatorname{gcd}(m, n)$.

comment
• # Paper 4, Section II, $7 \mathrm{E}$

(i) What does it mean to say that a set is countable? Show directly from your definition that any subset of a countable set is countable, and that a countable union of countable sets is countable.

(ii) Let $X$ be either $\mathbb{Z}$ or $\mathbb{Q}$. A function $f: X \rightarrow \mathbb{Z}$ is said to be periodic if there exists a positive integer $n$ such that for every $x \in X, f(x+n)=f(x)$. Show that the set of periodic functions from $\mathbb{Z}$ to itself is countable. Is the set of periodic functions $f: \mathbb{Q} \rightarrow \mathbb{Z}$ countable? Justify your answer.

(iii) Show that $\mathbb{R}^{2}$ is not the union of a countable collection of lines.

[You may assume that $\mathbb{R}$ and the power set of $\mathbb{N}$ are uncountable.]

comment
• # Paper 4, Section II, E

Let $p$ be a prime number, and $x, n$ integers with $n \geqslant 1$.

(i) Prove Fermat's Little Theorem: for any integer $x, x^{p} \equiv x(\bmod p)$.

(ii) Show that if $y$ is an integer such that $x \equiv y\left(\bmod p^{n}\right)$, then for every integer $r \geqslant 0$,

$x^{p^{r}} \equiv y^{p^{r}}\left(\bmod p^{n+r}\right)$

Deduce that $x^{p^{n}} \equiv x^{p^{n-1}}\left(\bmod p^{n}\right) .$

(iii) Show that there exists a unique integer $y \in\left\{0,1, \ldots, p^{n}-1\right\}$ such that

$y \equiv x \quad(\bmod p) \quad \text { and } \quad y^{p} \equiv y \quad\left(\bmod p^{n}\right)$

comment
• # Paper 4, Section II, E

(i) Let $N$ and $r$ be integers with $N \geqslant 0, r \geqslant 1$. Let $S$ be the set of $(r+1)$-tuples $\left(n_{0}, n_{1}, \ldots, n_{r}\right)$ of non-negative integers satisfying the equation $n_{0}+\cdots+n_{r}=N$. By mapping elements of $S$ to suitable subsets of $\{1, \ldots, N+r\}$ of size $r$, or otherwise, show that the number of elements of $S$ equals

$\left(\begin{array}{c} N+r \\ r \end{array}\right)$

(ii) State the Inclusion-Exclusion principle.

(iii) Let $a_{0}, \ldots, a_{r}$ be positive integers. Show that the number of $(r+1)$-tuples $\left(n_{i}\right)$ of integers satisfying

$n_{0}+\cdots+n_{r}=N, \quad 0 \leqslant n_{i}

$\begin{array}{rl}\left(\begin{array}{c}N+r\\ r\end{array}\right)& -\sum _{0⩽i⩽r}\left(\begin{array}{c}N+r-{a}_{i}\\ r\end{array}\right)+\sum _{0⩽i