Numbers And Sets

2021

• Paper 4 , Section I, E

  Numbers and Sets | Part IA, 2021

  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<n$, 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$

  Numbers and Sets | Part IA, 2021

  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}$

  Numbers and Sets | Part IA, 2021

  (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$$

  Is your solution unique?

  (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}$

  Numbers and Sets | Part IA, 2021

  (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

  Numbers and Sets | Part IA, 2021

  (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}$$

  Justify your answers.

  (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

  Numbers and Sets | Part IA, 2021

  (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

2020

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

  Numbers and Sets | Part IA, 2020

  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

  Numbers and Sets | Part IA, 2020

  (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

  Numbers and Sets | Part IA, 2020

  (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

2019

• Paper 4, Section $I$, E

  Numbers and Sets | Part IA, 2019

  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

  Numbers and Sets | Part IA, 2019

  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}$

  Numbers and Sets | Part IA, 2019

  (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

  Numbers and Sets | Part IA, 2019

  (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

  Numbers and Sets | Part IA, 2019

  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

  Numbers and Sets | Part IA, 2019

  (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

2018

• Paper 4, Section I, E

  Numbers and Sets | Part IA, 2018

  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

  Numbers and Sets | Part IA, 2018

  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$

  Numbers and Sets | Part IA, 2018

  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<k<p^{m}$. 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}$

  Numbers and Sets | Part IA, 2018

  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

  Numbers and Sets | Part IA, 2018

  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

  Numbers and Sets | Part IA, 2018

  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

2017

• Paper 4, Section I, D

  Numbers and Sets | Part IA, 2017

  (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

  Numbers and Sets | Part IA, 2017

  (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

  Numbers and Sets | Part IA, 2017

  (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

  Numbers and Sets | Part IA, 2017

  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

  Numbers and Sets | Part IA, 2017

  (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

  Numbers and Sets | Part IA, 2017

  (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

2016

• Paper 4, Section I, E

  Numbers and Sets | Part IA, 2016

  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

  Numbers and Sets | Part IA, 2016

  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}$

  Numbers and Sets | Part IA, 2016

  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}<b_{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}<p_{i}^{n_{i}}$ and $n \in \mathbb{Z}$. Express $\frac{a}{b}=\frac{1}{315}$ in this form.

  comment

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

  Numbers and Sets | Part IA, 2016

  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<k$ or $a_{j+i} \equiv a_{j}-i(\bmod 10)$ for all $0 \leqslant i<k$. 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

  Numbers and Sets | Part IA, 2016

  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<n$. Evaluate $S_{n}(n)$.

  comment

• Paper 4, Section II, E

  Numbers and Sets | Part IA, 2016

  (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

2015

• Paper 4 , Section I, E

  Numbers and Sets | Part IA, 2015

  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

  Numbers and Sets | Part IA, 2015

  (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

  Numbers and Sets | Part IA, 2015

  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

  Numbers and Sets | Part IA, 2015

  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<j \leqslant n$ 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

  Numbers and Sets | Part IA, 2015

  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}<p$ 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<j<p$$

  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<j<p^{i}$$

  (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

  Numbers and Sets | Part IA, 2015

  (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

2014

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

  Numbers and Sets | Part IA, 2014

  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

  Numbers and Sets | Part IA, 2014

  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

  Numbers and Sets | Part IA, 2014

  (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

  Numbers and Sets | Part IA, 2014

  (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

  Numbers and Sets | Part IA, 2014

  (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

  Numbers and Sets | Part IA, 2014

  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

2013

• Paper 4, Section I, E

  Numbers and Sets | Part IA, 2013

  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

  Numbers and Sets | Part IA, 2013

  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}$

  Numbers and Sets | Part IA, 2013

  (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

  Numbers and Sets | Part IA, 2013

  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

  Numbers and Sets | Part IA, 2013

  (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}<a_{i} \text { for all } i$$

  $$\begin{aligned} \left(\begin{array}{c} N+r \\ r \end{array}\right) &-\sum_{0 \leqslant i \leqslant r}\left(\begin{array}{c} N+r-a_{i} \\ r \end{array}\right)+\sum_{0 \leqslant i<j \leqslant r}\left(\begin{array}{c} N+r-a_{i}-a_{j} \\ r \end{array}\right) \\ &-\sum_{0 \leqslant i<j<k \leqslant r}\left(\begin{array}{c} N+r-a_{i}-a_{j}-a_{k} \\ r \end{array}\right)+\cdots \end{aligned}$$

  where the binomial coefficient $\left(\begin{array}{c}m \\ r\end{array}\right)$ is defined to be zero if $m<r$.

  comment

• Paper 4, Section II, E

  Numbers and Sets | Part IA, 2013

  (i) What does it mean to say that a function $f: X \rightarrow Y$ is injective? What does it mean to say that $f$ is surjective? Let $g: Y \rightarrow Z$ be a function. Show that if $g \circ f$ is injective, then so is $f$, and that if $g \circ f$ is surjective, then so is $g$.

  (ii) Let $X_{1}, X_{2}$ be two sets. Their product $X_{1} \times X_{2}$ is the set of ordered pairs $\left(x_{1}, x_{2}\right)$ with $x_{i} \in X_{i}(i=1,2)$. Let $p_{i}$ (for $\left.i=1,2\right)$ be the function

  $$p_{i}: X_{1} \times X_{2} \rightarrow X_{i}, \quad p_{i}\left(x_{1}, x_{2}\right)=x_{i}$$

  When is $p_{i}$ surjective? When is $p_{i}$ injective?

  (iii) Now let $Y$ be any set, and let $f_{1}: Y \rightarrow X_{1}, f_{2}: Y \rightarrow X_{2}$ be functions. Show that there exists a unique $g: Y \rightarrow X_{1} \times X_{2}$ such that $f_{1}=p_{1} \circ g$ and $f_{2}=p_{2} \circ g$.

  Show that if $f_{1}$ or $f_{2}$ is injective, then $g$ is injective. Is the converse true? Justify your answer.

  Show that if $g$ is surjective then both $f_{1}$ and $f_{2}$ are surjective. Is the converse true? Justify your answer.

  comment

2012

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

  Numbers and Sets | Part IA, 2012

  What is an equivalence relation on a set $X$ ? If $R$ is an equivalence relation on $X$, what is an equivalence class of $R$ ? Prove that the equivalence classes of $R$ form a partition of $X$.

  Let $R$ and $S$ be equivalence relations on a set $X$. Which of the following are always equivalence relations? Give proofs or counterexamples as appropriate.

  (i) The relation $V$ on $X$ given by $x V y$ if both $x R y$ and $x S y$.

  (ii) The relation $W$ on $X$ given by $x W y$ if $x R y$ or $x S y$.

  comment

• Paper 4, Section I, D

  Numbers and Sets | Part IA, 2012

  (i) Find integers $x$ and $y$ such that $18 x+23 y=101$.

  (ii) Find an integer $x$ such that $x \equiv 3(\bmod 18)$ and $x \equiv 2(\bmod 23)$.

  comment

• Paper 4, Section II, D

  Numbers and Sets | Part IA, 2012

  Show that there is no injection from the power-set of $\mathbb{R}$ to $\mathbb{R}$. Show also that there is an injection from $\mathbb{R}^{2}$ to $\mathbb{R}$.

  Let $X$ be the set of all functions $f$ from $\mathbb{R}$ to $\mathbb{R}$ such that $f(x)=x$ for all but finitely many $x$. Determine whether or not there exists an injection from $X$ to $\mathbb{R}$.

  comment

• Paper 4, Section II, D

  Numbers and Sets | Part IA, 2012

  Prove that each of the following numbers is irrational: (i) $\sqrt{2}+\sqrt{3}$ (ii) $e$ (iii) The real root of the equation $x^{3}+4 x-7=0$ (iv) $\log _{2} 3$.

  comment

• Paper 4, Section II, D

  Numbers and Sets | Part IA, 2012

  State Fermat's Theorem and Wilson's Theorem.

  For which prime numbers $p$ does the equation $x^{2} \equiv-1(\bmod p)$ have a solution? Justify your answer.

  For a prime number $p$, and an integer $x$ that is not a multiple of $p$, the order of $x$ $(\bmod p)$ is the least positive integer $d$ such that $x^{d} \equiv 1(\bmod p)$. Show that if $x$ has order $d$ and also $x^{k} \equiv 1(\bmod p)$ then $d$ must divide $k$.

  For a positive integer $n$, let $F_{n}=2^{2^{n}}+1$. If $p$ is a prime factor of $F_{n}$, determine the order of $2(\bmod p)$. Hence show that the $F_{n}$ are pairwise coprime.

  Show that if $p$ is a prime of the form $4 k+3$ then $p$ cannot be a factor of any $F_{n}$. Give, with justification, a prime $p$ of the form $4 k+1$ such that $p$ is not a factor of any $F_{n}$.

  comment

• Paper 4, Section II, D

  Numbers and Sets | Part IA, 2012

  Let $X$ be a set, and let $f$ and $g$ be functions from $X$ to $X$. Which of the following are always true and which can be false? Give proofs or counterexamples as appropriate.

  (i) If $f g$ is the identity map then $g f$ is the identity map.

  (ii) If $f g=g$ then $f$ is the identity map.

  (iii) If $f g=f$ then $g$ is the identity map.

  How (if at all) do your answers change if we are given that $X$ is finite?

  Determine which sets $X$ have the following property: if $f$ is a function from $X$ to $X$ such that for every $x \in X$ there exists a positive integer $n$ with $f^{n}(x)=x$, then there exists a positive integer $n$ such that $f^{n}$ is the identity map. [Here $f^{n}$ denotes the $n$-fold composition of $f$ with itself.]

  comment

2011

• Paper 4, Section I, E

  Numbers and Sets | Part IA, 2011

  What is an equivalence relation on a set $X ?$ If $\sim$ is an equivalence relation on $X$, what is an equivalence class of $\sim$ ? Prove that the equivalence classes of $\sim$ form a partition of $X$.

  Let $\sim$ be the relation on the positive integers defined by $x \sim y$ if either $x$ divides $y$ or $y$ divides $x$. Is $\sim$ an equivalence relation? Justify your answer.

  Write down an equivalence relation on the positive integers that has exactly four equivalence classes, of which two are infinite and two are finite.

  comment

• Paper 4, Section I, E

  Numbers and Sets | Part IA, 2011

  What does it mean to say that a function $f: X \rightarrow Y$ has an inverse? Show that a function has an inverse if and only if it is a bijection.

  Let $f$ and $g$ be functions from a set $X$ to itself. Which of the following are always true, and which can be false? Give proofs or counterexamples as appropriate.

  (i) If $f$ and $g$ are bijections then $f \circ g$ is a bijection.

  (ii) If $f \circ g$ is a bijection then $f$ and $g$ are bijections.

  comment

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

  Numbers and Sets | Part IA, 2011

  Define the binomial coefficient $\left(\begin{array}{l}n \\ i\end{array}\right)$, where $n$ is a positive integer and $i$ is an integer with $0 \leqslant i \leqslant n$. Arguing from your definition, show that $\sum_{i=0}^{n}\left(\begin{array}{l}n \\ i\end{array}\right)=2^{n}$.

  Prove the binomial theorem, that $(1+x)^{n}=\sum_{i=0}^{n}\left(\begin{array}{l}n \\ i\end{array}\right) x^{i}$ for any real number $x$.

  By differentiating this expression, or otherwise, evaluate $\sum_{i=0}^{n} i\left(\begin{array}{l}n \\ i\end{array}\right)$ and $\sum_{i=0}^{n} i^{2}\left(\begin{array}{l}n \\ i\end{array}\right)$. By considering the identity $(1+x)^{n}(1+x)^{n}=(1+x)^{2 n}$, or otherwise, show that

  $$\sum_{i=0}^{n}\left(\begin{array}{l} n \\ i \end{array}\right)^{2}=\left(\begin{array}{c} 2 n \\ n \end{array}\right)$$

  Show that $\sum_{i=0}^{n} i\left(\begin{array}{c}n \\ i\end{array}\right)^{2}=\frac{n}{2}\left(\begin{array}{c}2 n \\ n\end{array}\right)$

  comment

• Paper 4, Section II, E

  Numbers and Sets | Part IA, 2011

  Show that, for any set $X$, there is no surjection from $X$ to the power-set of $X$.

  Show that there exists an injection from $\mathbb{R}^{2}$ to $\mathbb{R}$.

  Let $A$ be a subset of $\mathbb{R}^{2}$. A section of $A$ is a subset of $\mathbb{R}$ of the form

  $$\{t \in \mathbb{R}: a+t b \in A\},$$

  where $a \in \mathbb{R}^{2}$ and $b \in \mathbb{R}^{2}$ with $b \neq 0$. Prove that there does not exist a set $A \subset \mathbb{R}^{2}$ such that every set $S \subset \mathbb{R}$ is a section of $A$.

  Does there exist a set $A \subset \mathbb{R}^{2}$ such that every countable set $S \subset \mathbb{R}$ is a section of $A ? \quad$ [There is no requirement that every section of $A$ should be countable.] Justify your answer.

  comment

• Paper 4, Section II, E

  Numbers and Sets | Part IA, 2011

  State Fermat's Theorem and Wilson's Theorem.

  Let $p$ be a prime.

  (a) Show that if $p \equiv 3(\bmod 4)$ then the equation $x^{2} \equiv-1(\bmod p)$ has no solution.

  (b) By considering $\left(\frac{p-1}{2}\right)$ !, or otherwise, show that if $p \equiv 1(\bmod 4)$ then the equation $x^{2} \equiv-1(\bmod p)$ does have a solution.

  (c) Show that if $p \equiv 2(\bmod 3)$ then the equation $x^{3} \equiv-1(\bmod p)$ has no solution other than $-1(\bmod p)$.

  (d) Using the fact that $14^{2} \equiv-3(\bmod 199)$, find a solution of $x^{3} \equiv-1(\bmod 199)$ that is not $-1(\bmod 199)$.

  [Hint: how are the complex numbers $\sqrt{-3}$ and $\sqrt[3]{-1}$ related?]

  comment

• Paper 4, Section II, E

  Numbers and Sets | Part IA, 2011

  (a) What is the highest common factor of two positive integers $a$ and $b$ ? Show that the highest common factor may always be expressed in the form $\lambda a+\mu b$, where $\lambda$ and $\mu$ are integers.

  Which positive integers $n$ have the property that, for any positive integers $a$ and $b$, if $n$ divides $a b$ then $n$ divides $a$ or $n$ divides $b$ ? Justify your answer.

  Let $a, b, c, d$ be distinct prime numbers. Explain carefully why $a b$ cannot equal $c d$.

  [No form of the Fundamental Theorem of Arithmetic may be assumed without proof.]

  (b) Now let $S$ be the set of positive integers that are congruent to 1 mod 10 . We say that $x \in S$ is irreducible if $x>1$ and whenever $a, b \in S$ satisfy $a b=x$ then $a=1$ or $b=1$. Do there exist distinct irreducibles $a, b, c, d$ with $a b=c d ?$

  comment

2010

• Paper 4 , Section II, E

  Numbers and Sets | Part IA, 2010

  What does it mean for a set to be countable ?

  Show that $\mathbb{Q}$ is countable, but $\mathbb{R}$ is not. Show also that the union of two countable sets is countable.

  A subset $A$ of $\mathbb{R}$ has the property that, given $\epsilon>0$ and $x \in \mathbb{R}$, there exist reals $a, b$ with $a \in A$ and $b \notin A$ with $|x-a|<\epsilon$ and $|x-b|<\epsilon$. Can $A$ be countable ? Can $A$ be uncountable ? Justify your answers.

  A subset $B$ of $\mathbb{R}$ has the property that given $b \in B$ there exists $\epsilon>0$ such that if $0<|b-x|<\epsilon$ for some $x \in \mathbb{R}$, then $x \notin B$. Is $B$ countable ? Justify your answer.

  comment

• Paper 4, Section I, $2 E$

  Numbers and Sets | Part IA, 2010

  (a) Let $r$ be a real root of the polynomial $f(x)=x^{n}+a_{n-1} x^{n-1}+\cdots+a_{0}$, with integer coefficients $a_{i}$ and leading coefficient 1 . Show that if $r$ is rational, then $r$ is an integer.

  (b) Write down a series for $e$. By considering $q ! e$ for every natural number $q$, show that $e$ is irrational.

  comment

• Paper 4, Section I, E

  Numbers and Sets | Part IA, 2010

  (a) Find the smallest residue $x$ which equals $28 ! 13^{28}(\bmod 31)$.

  [You may use any standard theorems provided you state them correctly.]

  (b) Find all integers $x$ which satisfy the system of congruences

  $$\begin{aligned} x & \equiv 1(\bmod 2) \\ 2 x & \equiv 1(\bmod 3) \\ 2 x & \equiv 4(\bmod 10) \\ x & \equiv 10(\bmod 67) \end{aligned}$$

  comment

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

  Numbers and Sets | Part IA, 2010

  State and prove Fermat's Little Theorem.

  Let $p$ be an odd prime. If $p \neq 5$, show that $p$ divides $10^{n}-1$ for infinitely many natural numbers $n$.

  Hence show that $p$ divides infinitely many of the integers

  $$5,55, \quad 555, \quad 5555, \quad \ldots .$$

  comment

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

  Numbers and Sets | Part IA, 2010

  (a) Let $A, B$ be finite non-empty sets, with $|A|=a,|B|=b$. Show that there are $b^{a}$ mappings from $A$ to $B$. How many of these are injective ?

  (b) State the Inclusion-Exclusion principle.

  (c) Prove that the number of surjective mappings from a set of size $n$ onto a set of size $k$ is

  $$\sum_{i=0}^{k}(-1)^{i}\left(\begin{array}{c} k \\ i \end{array}\right)(k-i)^{n} \quad \text { for } n \geqslant k \geqslant 1$$

  Deduce that

  $$n !=\sum_{i=0}^{n}(-1)^{i}\left(\begin{array}{c} n \\ i \end{array}\right)(n-i)^{n}$$

  comment

• Paper 4, Section II, E

  Numbers and Sets | Part IA, 2010

  The Fibonacci numbers $F_{n}$ are defined for all natural numbers $n$ by the rules

  $$F_{1}=1, \quad F_{2}=1, \quad F_{n}=F_{n-1}+F_{n-2} \quad \text { for } n \geqslant 3$$

  Prove by induction on $k$ that, for any $n$,

  $$F_{n+k}=F_{k} F_{n+1}+F_{k-1} F_{n} \text { for all } k \geqslant 2 \text {. }$$

  Deduce that

  $$F_{2 n}=F_{n}\left(F_{n+1}+F_{n-1}\right) \quad \text { for all } n \geqslant 2$$

  Put $L_{1}=1$ and $L_{n}=F_{n+1}+F_{n-1}$ for $n>1$. Show that these (Lucas) numbers $L_{n}$ satisfy

  $$L_{1}=1, \quad L_{2}=3, \quad L_{n}=L_{n-1}+L_{n-2} \quad \text { for } n \geqslant 3$$

  Show also that, for all $n$, the greatest common divisor $\left(F_{n}, F_{n+1}\right)$ is 1 , and that the greatest common divisor $\left(F_{n}, L_{n}\right)$ is at most 2 .

  comment

2009

• Paper 4, Section I, $2 E$

  Numbers and Sets | Part IA, 2009

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

  $$9 x+12 y \equiv 4 \quad(\bmod 47) \quad \text { and } \quad 6 x+7 y \equiv 14 \quad(\bmod 47)$$

  (b) Calculate $43^{135}(\bmod 137)$.

  comment

• Paper 4, Section I, E

  Numbers and Sets | Part IA, 2009

  Let $R_{1}$ and $R_{2}$ be relations on a set $A$. Let us say that $R_{2}$ extends $R_{1}$ if $x R_{1} y$ implies that $x R_{2} y$. If $R_{2}$ extends $R_{1}$, then let us call $R_{2}$ an extension of $R_{1}$.

  Let $Q$ be a relation on a set $A$. Let $R$ be the extension of $Q$ defined by taking $x R y$ if and only if $x Q y$ or $x=y$. Let $S$ be the extension of $R$ defined by taking $x S y$ if and only if $x R y$ or $y R x$. Finally, let $T$ be the extension of $S$ defined by taking $x T y$ if and only if there is a positive integer $n$ and a sequence $\left(x_{0}, x_{1}, \ldots, x_{n}\right)$ such that $x_{0}=x, x_{n}=y$, and $x_{i-1} S x_{i}$ for each $i$ from 1 to $n$.

  Prove that $R$ is reflexive, $S$ is reflexive and symmetric, and $T$ is an equivalence relation.

  Let $E$ be any equivalence relation that extends $Q$. Prove that $E$ extends $T$.

  comment

• Paper 4, Section II, E

  Numbers and Sets | Part IA, 2009

  Prove that the set of all infinite sequences $\left(\epsilon_{1}, \epsilon_{2}, \ldots\right)$ with every $\epsilon_{i}$ equal to 0 or 1 is uncountable. Deduce that the closed interval $[0,1]$ is uncountable.

  For an ordered set $X$ let $\Sigma(X)$ denote the set of increasing (but not necessarily strictly increasing) sequences in $X$ that are bounded above. For each of $\Sigma(\mathbb{Z}), \Sigma(\mathbb{Q})$ and $\Sigma(\mathbb{R})$, determine (with proof) whether it is uncountable.

  comment

• Paper 4, Section II, E

  Numbers and Sets | Part IA, 2009

  Let $p$ be a prime number and let $\mathbb{Z}_{p}$ denote the set of integers modulo $p$. Let $k$ be an integer with $0 \leqslant k \leqslant p$ and let $A$ be a subset of $\mathbb{Z}_{p}$ of size $k$.

  Let $t$ be a non-zero element of $\mathbb{Z}_{p}$. Show that if $a+t \in A$ whenever $a \in A$ then $k=0$ or $k=p$. Deduce that if $1 \leqslant k \leqslant p-1$, then the sets $A, A+1, \ldots, A+p-1$ are all distinct, where $A+t$ denotes the set $\{a+t: a \in A\}$. Deduce from this that $\left(\begin{array}{l}p \\ k\end{array}\right)$ is a multiple of $p$ whenever $1 \leqslant k \leqslant p-1$.

  Now prove that $(a+1)^{p}=a^{p}+1$ for any $a \in \mathbb{Z}_{p}$, and use this to prove Fermat's little theorem. Prove further that if $Q(x)=a_{n} x^{n}+a_{n-1} x^{n-1}+\ldots+a_{1} x+a_{0}$ is a polynomial in $x$ with coefficients in $\mathbb{Z}_{p}$, then the polynomial $(Q(x))^{p}$ is equal to $a_{n} x^{p n}+a_{n-1} x^{p(n-1)}+\ldots+a_{1} x^{p}+a_{0} .$

  comment

• Paper 4, Section II, E

  Numbers and Sets | Part IA, 2009

  (a) State and prove the inclusion-exclusion formula.

  (b) Let $k$ and $m$ be positive integers, let $n=k m$, let $A_{1}, \ldots, A_{k}$ be disjoint sets of size $m$, and let $A=A_{1} \cup \ldots \cup A_{k}$. Let $\mathcal{B}$ be the collection of all subsets $B \subset A$ with the following two properties:

  (i) $|B|=k$;

  (ii) there is at least one $i$ such that $\left|B \cap A_{i}\right|=3$.

  Prove that the number of sets in $\mathcal{B}$ is given by the formula

  $$\sum_{r=1}^{\lfloor k / 3\rfloor}(-1)^{r-1}\left(\begin{array}{c} k \\ r \end{array}\right)\left(\begin{array}{c} m \\ 3 \end{array}\right)^{r}\left(\begin{array}{c} n-r m \\ k-3 r \end{array}\right)$$

  comment

• Paper 4, Section II, E

  Numbers and Sets | Part IA, 2009

  (a) Let $A$ and $B$ be non-empty sets and let $f: A \rightarrow B$.

  Prove that $f$ is an injection if and only if $f$ has a left inverse.

  Prove that $f$ is a surjection if and only if $f$ has a right inverse.

  (b) Let $A, B$ and $C$ be sets and let $f: B \rightarrow A$ and $g: B \rightarrow C$ be functions. Suppose that $f$ is a surjection. Prove that there is a function $h: A \rightarrow C$ such that for every $a \in A$ there exists $b \in B$ with $f(b)=a$ and $g(b)=h(a)$.

  Prove that $h$ is unique if and only if $g(b)=g\left(b^{\prime}\right)$ whenever $f(b)=f\left(b^{\prime}\right)$.

  comment

2008

• 4.I.1D

  Numbers and Sets | Part IA, 2008

  Let $A, B$ and $C$ be non-empty sets and let $f: A \rightarrow B$ and $g: B \rightarrow C$ be two functions. For each of the following statements, give either a brief justification or a counterexample.

  (i) If $f$ is an injection and $g$ is a surjection, then $g \circ f$ is a surjection.

  (ii) If $f$ is an injection and $g$ is an injection, then there exists a function $h: C \rightarrow A$ such that $h \circ g \circ f$ is equal to the identity function on $A$.

  (iii) If $X$ and $Y$ are subsets of $A$ then $f(X \cap Y)=f(X) \cap f(Y)$.

  (iv) If $Z$ and $W$ are subsets of $B$ then $f^{-1}(Z \cap W)=f^{-1}(Z) \cap f^{-1}(W)$.

  comment

• 4.I.2D

  Numbers and Sets | Part IA, 2008

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

  (b) Let $\mathbb{Z}^{+}$be the set of all positive integers. Let a relation $\sim$ be defined on $\mathbb{Z}^{+}$by setting $m \sim n$ if and only if $m / n=2^{k}$ for some (not necessarily positive) integer $k$. Prove that $\sim$ is an equivalence relation, and give an example of a set $A \subset \mathbb{Z}^{+}$that contains precisely one element of each equivalence class.

  comment

• 4.II.5D

  Numbers and Sets | Part IA, 2008

  (a) Define the notion of a countable set, and prove that the set $\mathbb{N} \times \mathbb{N}$ is countable. Deduce that if $X$ and $Y$ are countable sets then $X \times Y$ is countable, and also that a countable union of countable sets is countable.

  (b) If $A$ is any set of real numbers, define $\phi(A)$ to be the set of all real roots of non-zero polynomials that have coefficients in $A$. Now suppose that $A_{0}$ is a countable set of real numbers and define a sequence $A_{1}, A_{2}, A_{3}, \ldots$ by letting each $A_{n}$ be equal to $\phi\left(A_{n-1}\right)$. Prove that the union $\bigcup_{n=1}^{\infty} A_{n}$ is countable.

  (c) Deduce that there is a countable set $X$ that contains the real numbers 1 and $\pi$ and has the further property that if $P$ is any non-zero polynomial with coefficients in $X$, then all real roots of $P$ belong to $X$.

  comment

• 4.II.6D

  Numbers and Sets | Part IA, 2008

  (a) Let $a$ and $m$ be integers with $1 \leqslant a<m$ and let $d=(a, m)$ be their highest common factor. For any integer $b$, prove that $b$ is a multiple of $d$ if and only if there exists an integer $r$ satisfying the equation $a r \equiv b \operatorname{(\operatorname {mod}m)\text {,andshowthatinthiscasethereare}}$ exactly $d$ solutions to the equation that are distinct $\bmod m$.

  Deduce that the equation $a r \equiv b(\bmod m)$ has a solution if and only if $b(m / d) \equiv 0$ $(\bmod m)$.

  (b) Let $p$ be a prime and let $\mathbb{Z}_{p}^{*}$ be the multiplicative group of non-zero integers $\bmod p$. An element $x$ of $\mathbb{Z}_{p}^{*}$ is called a $k$ th power $(\bmod p)$ if $x \equiv y^{k}(\bmod p)$ for some integer $y$. It can be shown that $\mathbb{Z}_{p}^{*}$ has a generator: that is, an element $u$ such that every element of $\mathbb{Z}_{p}^{*}$ is a power of $u$. Assuming this result, deduce that an element $x$ of $\mathbb{Z}_{p}^{*}$ is a $k$ th power $(\bmod p)$ if and only if $x^{(p-1) / d} \equiv 1(\bmod p)$, where $d$ is now the highest common factor of $k$ and $p-1$.

  (c) How many 437th powers are there mod 1013? [You may assume that 1013 is a prime number.]

  comment

• 4.II.7D

  Numbers and Sets | Part IA, 2008

  (a) Let $\mathbb{F}$ be a field such that the equation $x^{2}=-1$ has no solution in $\mathbb{F}$. Prove that if $x$ and $y$ are elements of $\mathbb{F}$ such that $x^{2}+y^{2}=0$, then both $x$ and $y$ must equal 0 .

  Prove that $\mathbb{F}^{2}$ can be made into a field, with operations

  $$(x, y)+(z, w)=(x+z, y+w)$$

  and

  $$(x, y) \cdot(z, w)=(x z-y w, x w+y z) .$$

  (b) Let $p$ be a prime of the form $4 m+3$. Prove that $-1$ is not a square $(\bmod p)$, and deduce that there exists a field with exactly $p^{2}$ elements.

  comment

• 4.II.8D

  Numbers and Sets | Part IA, 2008

  Let $q$ be a positive integer. For every positive integer $k$, define a number $c_{k}$ by the formula

  $$c_{k}=(q+k-1) \frac{q !}{(q+k) !}$$

  Prove by induction that

  $$\sum_{k=1}^{n} c_{k}=1-\frac{q !}{(q+n) !}$$

  for every $n \geqslant 1$, and hence evaluate the infinite $\operatorname{sum} \sum_{k=1}^{\infty} c_{k}$.

  Let $a_{1}, a_{2}, a_{3}, \ldots$ be a sequence of integers satisfying the inequality $0 \leqslant a_{n}<n$ for every $n$. Prove that the series $\sum_{n=1}^{\infty} a_{n} / n$ ! is convergent. Prove also that its limit is irrational if and only if $a_{n} \leqslant n-2$ for infinitely many $n$ and $a_{m}>0$ for infinitely many $m$.

  comment

2007

• Paper 4 , Section II, E

  Numbers and Sets | Part IA, 2007

  State and prove the Inclusion-Exclusion principle.

  The keypad on a cash dispenser is broken. To withdraw money, a customer is required to key in a 4-digit number. However, the key numbered 0 will only function if either the immediately preceding two keypresses were both 1 , or the very first key pressed was 2. Explaining your reasoning clearly, use the Inclusion-Exclusion Principle to find the number of 4-digit codes which can be entered.

  comment

• Paper 4, Section I, $1 E$

  Numbers and Sets | Part IA, 2007

  (i) Use Euclid's algorithm to find all pairs of integers $x$ and $y$ such that

  $$7 x+18 y=1$$

  (ii) Show that, if $n$ is odd, then $n^{3}-n$ is divisible by 24 .

  comment

• Paper 4, Section I, $2 E$

  Numbers and Sets | Part IA, 2007

  For integers $k$ and $n$ with $0 \leqslant k \leqslant n$, define $\left(\begin{array}{l}n \\ k\end{array}\right)$. Arguing from your definition, show that

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

  for all integers $k$ and $n$ with $1 \leqslant k \leqslant n-1$.

  Use induction on $k$ to prove that

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

  for all non-negative integers $k$ and $n$.

  comment

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

  Numbers and Sets | Part IA, 2007

  Stating carefully any results about countability you use, show that for any $d \geqslant 1$ the set $\mathbb{Z}\left[X_{1}, \ldots, X_{d}\right]$ of polynomials with integer coefficients in $d$ variables is countable. By taking $d=1$, deduce that there exist uncountably many transcendental numbers.

  Show that there exists a sequence $x_{1}, x_{2}, \ldots$ of real numbers with the property that $f\left(x_{1}, \ldots, x_{d}\right) \neq 0$ for every $d \geqslant 1$ and for every non-zero polynomial $f \in \mathbb{Z}\left[X_{1}, \ldots, X_{d}\right]$.

  [You may assume without proof that $\mathbb{R}$ is uncountable.]

  comment

• Paper 4, Section II, $7 \mathbf{E}$

  Numbers and Sets | Part IA, 2007

  Let $x_{n}(n=1,2, \ldots)$ be real numbers.

  What does it mean to say that the sequence $\left(x_{n}\right)_{n=1}^{\infty}$ converges?

  What does it mean to say that the series $\sum_{n=1}^{\infty} x_{n}$ converges?

  Show that if $\sum_{n=1}^{\infty} x_{n}$ is convergent, then $x_{n} \rightarrow 0$. Show that the converse can be false.

  Sequences of positive real numbers $x_{n}, y_{n}(n \geqslant 1)$ are given, such that the inequality

  $$y_{n+1} \leqslant y_{n}-\frac{1}{2} \min \left(x_{n}, y_{n}\right)$$

  holds for all $n \geqslant 1$. Show that, if $\sum_{n=1}^{\infty} x_{n}$ diverges, then $y_{n} \rightarrow 0$.

  comment

• Paper 4, Section II, E

  Numbers and Sets | Part IA, 2007

  (i) Let $p$ be a prime number, and let $x$ and $y$ be integers such that $p$ divides $x y$. Show that at least one of $x$ and $y$ is divisible by $p$. Explain how this enables one to prove the Fundamental Theorem of Arithmetic.

  [Standard properties of highest common factors may be assumed without proof.]

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

  Let $1 / 359$ have decimal expansion $0 \cdot a_{1} a_{2} \ldots$ with $a_{n} \in\{0,1, \ldots, 9\}$. Use the fact that $60^{2} \equiv 10(\bmod 359)$ to show that, for every $n, a_{n}=a_{n+179}$.

  comment

2006

• 4.I.1E

  Numbers and Sets | Part IA, 2006

  Explain what is meant by a prime number.

  By considering numbers of the form $6 p_{1} p_{2} \cdots p_{n}-1$, show that there are infinitely many prime numbers of the form $6 k-1$.

  By considering numbers of the form $\left(2 p_{1} p_{2} \cdots p_{n}\right)^{2}+3$, show that there are infinitely many prime numbers of the form $6 k+1$. [You may assume the result that, for a prime $p>3$, the congruence $x^{2} \equiv-3(\bmod p)$ is soluble only if $\left.p \equiv 1(\bmod 6) .\right]$

  comment

• 4.I.2E

  Numbers and Sets | Part IA, 2006

  Define the binomial coefficient $\left(\begin{array}{l}n \\ r\end{array}\right)$ and prove that

  $$\left(\begin{array}{c} n+1 \\ r \end{array}\right)=\left(\begin{array}{c} n \\ r \end{array}\right)+\left(\begin{array}{c} n \\ r-1 \end{array}\right) \quad \text { for } 0<r \leqslant n$$

  Show also that if $p$ is prime then $\left(\begin{array}{l}p \\ r\end{array}\right)$ is divisible by $p$ for $0<r<p$.

  Deduce that if $0 \leqslant k<p$ and $0 \leqslant r \leqslant k$ then

  $$\left(\begin{array}{c} p+k \\ r \end{array}\right) \equiv\left(\begin{array}{c} k \\ r \end{array}\right) \quad(\bmod p) .$$

  comment

• 4.II.5E

  Numbers and Sets | Part IA, 2006

  Explain what is meant by an equivalence relation on a set $A$.

  If $R$ and $S$ are two equivalence relations on the same set $A$, we define

  $R \circ S=\{(x, z) \in A \times A:$ there exists $y \in A$ such that $(x, y) \in R$ and $(y, z) \in S\} .$

  Show that the following conditions are equivalent:

  (i) $R \circ S$ is a symmetric relation on $A$;

  (ii) $R \circ S$ is a transitive relation on $A$;

  (iii) $S \circ R \subseteq R \circ S$;

  (iv) $R \circ S$ is the unique smallest equivalence relation on $A$ containing both $R$ and $S$.

  Show also that these conditions hold if $A=\mathbb{Z}$ and $R$ and $S$ are the relations of congruence modulo $m$ and modulo $n$, for some positive integers $m$ and $n$.

  comment

• 4.II.6E

  Numbers and Sets | Part IA, 2006

  State and prove the Inclusion-Exclusion Principle.

  A permutation $\sigma$ of $\{1,2, \ldots, n\}$ is called a derangement if $\sigma(j) \neq j$ for every $j \leqslant n$. Use the Inclusion-Exclusion Principle to find a formula for the number $f(n)$ of derangements of $\{1,2, \ldots, n\}$. Show also that $f(n) / n$ ! converges to $1 / e$ as $n \rightarrow \infty$.

  comment

• 4.II.7E

  Numbers and Sets | Part IA, 2006

  State and prove Fermat's Little Theorem.

  An odd number $n$ is called a Carmichael number if it is not prime, but every positive integer $a$ satisfies $a^{n} \equiv a(\bmod n)$. Show that a Carmichael number cannot be divisible by the square of a prime. Show also that a product of two distinct odd primes cannot be a Carmichael number, and that a product of three distinct odd primes $p, q, r$ is a Carmichael number if and only if $p-1$ divides $q r-1, q-1$ divides $p r-1$ and $r-1$ divides $p q-1$. Deduce that 1729 is a Carmichael number.

  [You may assume the result that, for any prime $p$, there exists a number g prime to $p$ such that the congruence $g^{d} \equiv 1(\bmod p)$ holds only when $d$ is a multiple of $p-1$. The prime factors of 1729 are 7,13 and 19.]

  comment

• 4.II.8E

  Numbers and Sets | Part IA, 2006

  Explain what it means for a set to be countable. Prove that a countable union of countable sets is countable, and that the set of all subsets of $\mathbb{N}$ is uncountable.

  A function $f: \mathbb{N} \rightarrow \mathbb{N}$ is said to be increasing if $f(m) \leqslant f(n)$ whenever $m \leqslant n$, and decreasing if $f(m) \geqslant f(n)$ whenever $m \leqslant n$. Show that the set of all increasing functions $\mathbb{N} \rightarrow \mathbb{N}$ is uncountable, but that the set of decreasing functions is countable.

  [Standard results on countability, other than those you are asked to prove, may be assumed.]

  comment

2005

• 4.I.1E

  Numbers and Sets | Part IA, 2005

  Find the unique positive integer $a$ with $a \leq 19$, for which

  $$17 ! \cdot 3^{16} \equiv a(\bmod 19) \text {. }$$

  Results used should be stated but need not be proved.

  Solve the system of simultaneous congruences

  $$\begin{aligned} &x \equiv 1(\bmod 2), \\ &x \equiv 1(\bmod 3) \\ &x \equiv 3(\bmod 4) \\ &x \equiv 4(\bmod 5) \end{aligned}$$

  Explain very briefly your reasoning.

  comment

• 4.I.2E

  Numbers and Sets | Part IA, 2005

  Give a combinatorial definition of the binomial coefficient $\left(\begin{array}{l}n \\ m\end{array}\right)$ for any non-negative integers $n, m$.

  Prove that $\left(\begin{array}{c}n \\ m\end{array}\right)=\left(\begin{array}{c}n \\ n-m\end{array}\right)$ for $0 \leq m \leq n$.

  Prove the identities

  $$\left(\begin{array}{l} n \\ k \end{array}\right)\left(\begin{array}{l} k \\ l \end{array}\right)=\left(\begin{array}{l} n \\ l \end{array}\right)\left(\begin{array}{l} n-l \\ k-l \end{array}\right)$$

  and

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

  comment

• 4.II $. 7 \mathrm{E} \quad$

  Numbers and Sets | Part IA, 2005

  State and prove the Principle of Inclusion and Exclusion.

  Use the Principle to show that the Euler totient function $\phi$ satisfies

  $$\phi\left(p_{1}^{c_{1}} \cdots p_{r}^{c_{r}}\right)=p_{1}^{c_{1}-1}\left(p_{1}-1\right) \cdots p_{r}^{c_{r}-1}\left(p_{r}-1\right) .$$

  Deduce that if $a$ and $b$ are coprime integers, then $\phi(a b)=\phi(a) \phi(b)$, and more generally, that if $d$ is any divisor of $n$ then $\phi(d)$ divides $\phi(n)$.

  Show that if $\phi(n)$ divides $n$ then $n=2^{c} 3^{d}$ for some non-negative integers $c, d$.

  comment

• 4.II.5E

  Numbers and Sets | Part IA, 2005

  What does it mean for a set to be countable? Show that $\mathbb{Q} \times \mathbb{Q}$ is countable, and $\mathbb{R}$ is not countable.

  Let $D$ be any set of non-trivial discs in a plane, any two discs being disjoint. Show that $D$ is countable.

  Give an example of a set $C$ of non-trivial circles in a plane, any two circles being disjoint, which is not countable.

  comment

• 4.II.6E

  Numbers and Sets | Part IA, 2005

  Let $R$ be a relation on the set $S$. What does it mean for $R$ to be an equivalence relation on $S$ ? Show that if $R$ is an equivalence relation on $S$, the set of equivalence classes forms a partition of $S$.

  Let $G$ be a group, and let $H$ be a subgroup of $G$. Define a relation $R$ on $G$ by $a R b$ if $a^{-1} b \in H$. Show that $R$ is an equivalence relation on $G$, and that the equivalence classes are precisely the left cosets $g H$ of $H$ in $G$. Find a bijection from $H$ to any other coset $g H$. Deduce that if $G$ is finite then the order of $H$ divides the order of $G$.

  Let $g$ be an element of the finite group $G$. The order $o(g)$ of $g$ is the least positive integer $n$ for which $g^{n}=1$, the identity of $G$. If $o(g)=n$, then $G$ has a subgroup of order $n$; deduce that $g^{|G|}=1$ for all $g \in G$.

  Let $m$ be a natural number. Show that the set of integers in $\{1,2, \ldots, m\}$ which are prime to $m$ is a group under multiplication modulo $m$. [You may use any properties of multiplication and divisibility of integers without proof, provided you state them clearly.]

  Deduce that if $a$ is any integer prime to $m$ then $a^{\phi(m)} \equiv 1(\bmod \mathrm{m})$, where $\phi$ is the Euler totient function.

  comment

• 4.II.8E

  Numbers and Sets | Part IA, 2005

  The Fibonacci numbers are defined by the equations $F_{0}=0, F_{1}=1$ and $F_{n+1}=F_{n}+F_{n-1}$ for any positive integer $n$. Show that the highest common factor $\left(F_{n+1}, F_{n}\right)$ is $1 .$

  Let $n$ be a natural number. Prove by induction on $k$ that for all positive integers $k$,

  $$F_{n+k}=F_{k} F_{n+1}+F_{k-1} F_{n} .$$

  Deduce that $F_{n}$ divides $F_{n l}$ for all positive integers $l$. Deduce also that if $m \geq n$ then

  $$\left(F_{m}, F_{n}\right)=\left(F_{m-n}, F_{n}\right) .$$

  comment

2004

• 4.I.1E

  Numbers and Sets | Part IA, 2004

  (a) Use Euclid's algorithm to find positive integers $m, n$ such that $79 m-100 n=1$.

  (b) Determine all integer solutions of the congruence

  $$237 x \equiv 21(\bmod 300)$$

  (c) Find the set of all integers $x$ satisfying the simultaneous congruences

  $$\begin{aligned} &x \equiv 8(\bmod 79) \\ &x \equiv 11(\bmod 100) \end{aligned}$$

  comment

• 4.I.2E

  Numbers and Sets | Part IA, 2004

  Prove by induction the following statements:

  i) For every integer $n \geq 1$,

  $$1^{2}+3^{2}+\cdots+(2 n-1)^{2}=\frac{1}{3}\left(4 n^{3}-n\right)$$

  ii) For every integer $n \geq 1, n^{3}+5 n$ is divisible by 6 .

  comment

• 4.II.5E

  Numbers and Sets | Part IA, 2004

  Show that the set of all subsets of $\mathbb{N}$ is uncountable, and that the set of all finite subsets of $\mathbb{N}$ is countable.

  Let $X$ be the set of all bijections from $\mathbb{N}$ to $\mathbb{N}$, and let $Y \subset X$ be the set

  $$Y=\{f \in X \mid \text { for all but finitely many } n \in \mathbb{N}, f(n)=n\}$$

  Show that $X$ is uncountable, but that $Y$ is countable.

  comment

• 4.II.6E

  Numbers and Sets | Part IA, 2004

  Prove Fermat's Theorem: if $p$ is prime and $(x, p)=1$ then $x^{p-1} \equiv 1(\bmod p)$.

  Let $n$ and $x$ be positive integers with $(x, n)=1$. Show that if $n=m p$ where $p$ is prime and $(m, p)=1$, then

  $$x^{n-1} \equiv 1 \quad(\bmod p) \quad \text { if and only if } \quad x^{m-1} \equiv 1 \quad(\bmod p)$$

  Now assume that $n$ is a product of distinct primes. Show that $x^{n-1} \equiv 1(\bmod n)$ if and only if, for every prime divisor $p$ of $n$,

  $$x^{(n / p)-1} \equiv 1 \quad(\bmod p) .$$

  Deduce that if every prime divisor $p$ of $n$ satisfies $(p-1) \mid(n-1)$, then for every $x$ with $(x, n)=1$, the congruence

  $$x^{n-1} \equiv 1 \quad(\bmod n)$$

  holds.

  comment

• 4.II.7E

  Numbers and Sets | Part IA, 2004

  Polynomials $P_{r}(X)$ for $r \geq 0$ are defined by

  $$\begin{aligned} &P_{0}(X)=1 \\ &P_{r}(X)=\frac{X(X-1) \cdots(X-r+1)}{r !}=\prod_{i=1}^{r} \frac{X-i+1}{i} \quad \text { for } r \geq 1 \end{aligned}$$

  Show that $P_{r}(n) \in \mathbb{Z}$ for every $n \in \mathbb{Z}$, and that if $r \geq 1$ then $P_{r}(X)-P_{r}(X-1)=$ $P_{r-1}(X-1)$.

  Prove that if $F$ is any polynomial of degree $d$ with rational coefficients, then there are unique rational numbers $c_{r}(F)(0 \leq r \leq d)$ for which

  $$F(X)=\sum_{r=0}^{d} c_{r}(F) P_{r}(X)$$

  Let $\Delta F(X)=F(X+1)-F(X)$. Show that

  $$\Delta F(X)=\sum_{r=0}^{d-1} c_{r+1}(F) P_{r}(X)$$

  Show also that, if $F$ and $G$ are polynomials such that $\Delta F=\Delta G$, then $F-G$ is a constant.

  By induction on the degree of $F$, or otherwise, show that if $F(n) \in \mathbb{Z}$ for every $n \in \mathbb{Z}$, then $c_{r}(F) \in \mathbb{Z}$ for all $r$.

  comment

• 4.II.8E

  Numbers and Sets | Part IA, 2004

  Let $X$ be a finite set, $X_{1}, \ldots, X_{m}$ subsets of $X$ and $Y=X \backslash \bigcup X_{i}$. Let $g_{i}$ be the characteristic function of $X_{i}$, so that

  $$g_{i}(x)= \begin{cases}1 & \text { if } x \in X_{i} \\ 0 & \text { otherwise }\end{cases}$$

  Let $f: X \rightarrow \mathbb{R}$ be any function. By considering the expression

  $$\sum_{x \in X} f(x) \prod_{i=1}^{m}\left(1-g_{i}(x)\right)$$

  or otherwise, prove the Inclusion-Exclusion Principle in the form

  $$\sum_{x \in Y} f(x)=\sum_{r \geq 0}(-1)^{r} \sum_{i_{1}<\cdots<i_{r}}\left(\sum_{x \in X_{i_{1}} \cap \cdots \cap X_{i_{r}}} f(x)\right)$$

  Let $n>1$ be an integer. For an integer $m$ dividing $n$ let

  $$X_{m}=\{0 \leq x<n \mid x \equiv 0(\bmod m)\}$$

  By considering the sets $X_{p}$ for prime divisors $p$ of $n$, show that

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

  (where $\phi$ is Euler's function) and

  $$\sum_{\substack{0<x<n \\(x, n)=1}} x=\frac{n^{2}}{2} \prod_{p \mid n}\left(1-\frac{1}{p}\right) .$$

  comment

2003

• 4.I.1C

  Numbers and Sets | Part IA, 2003

  (i) Prove by induction or otherwise that for every $n \geqslant 1$,

  $$\sum_{r=1}^{n} r^{3}=\left(\sum_{r=1}^{n} r\right)^{2}$$

  (ii) Show that the sum of the first $n$ positive cubes is divisible by 4 if and only if $n \equiv 0$ or $3(\bmod 4)$.

  comment

• 4.I.2C

  Numbers and Sets | Part IA, 2003

  What is an equivalence relation? For each of the following pairs $(X, \sim)$, determine whether or not $\sim$ is an equivalence relation on $X$ :

  (i) $X=\mathbb{R}, x \sim y$ iff $x-y$ is an even integer;

  (ii) $X=\mathbb{C} \backslash\{0\}, x \sim y$ iff $x \bar{y} \in \mathbb{R}$;

  (iii) $X=\mathbb{C} \backslash\{0\}, x \sim y$ iff $x \bar{y} \in \mathbb{Z}$;

  (iv) $X=\mathbb{Z} \backslash\{0\}, x \sim y$ iff $x^{2}-y^{2}$ is $\pm 1$ times a perfect square.

  comment

• 4.II.5C

  Numbers and Sets | Part IA, 2003

  Define what is meant by the term countable. Show directly from your definition that if $X$ is countable, then so is any subset of $X$.

  Show that $\mathbb{N} \times \mathbb{N}$ is countable. Hence or otherwise, show that a countable union of countable sets is countable. Show also that for any $n \geqslant 1, \mathbb{N}^{n}$ is countable.

  A function $f: \mathbb{Z} \rightarrow \mathbb{N}$ is periodic if there exists a positive integer $m$ such that, for every $x \in \mathbb{Z}, f(x+m)=f(x)$. Show that the set of periodic functions $f: \mathbb{Z} \rightarrow \mathbb{N}$ is countable.

  comment

• 4.II.6C

  Numbers and Sets | Part IA, 2003

  (i) Prove Wilson's theorem: if $p$ is prime then $(p-1) ! \equiv-1(\bmod p)$.

  Deduce that if $p \equiv 1(\bmod 4)$ then

  $$\left(\left(\frac{p-1}{2}\right) !\right)^{2} \equiv-1 \quad(\bmod p)$$

  (ii) Suppose that $p$ is a prime of the form $4 k+3$. Show that if $x^{4} \equiv 1(\bmod p)$ then $x^{2} \equiv 1(\bmod p)$.

  (iii) Deduce that if $p$ is an odd prime, then the congruence

  $$x^{2} \equiv-1 \quad(\bmod p)$$

  has exactly two solutions ( $\operatorname{modulo} p)$ if $p \equiv 1(\bmod 4)$, and none otherwise.

  comment

• 4.II.7C

  Numbers and Sets | Part IA, 2003

  Let $m, n$ be integers. Explain what is their greatest common divisor $(m, n)$. Show from your definition that, for any integer $k, \quad(m, n)=(m+k n, n)$.

  State Bezout's theorem, and use it to show that if $p$ is prime and $p$ divides $m n$, then $p$ divides at least one of $m$ and $n$.

  The Fibonacci sequence $0,1,1,2,3,5,8, \ldots$ is defined by $x_{0}=0, x_{1}=1$ and $x_{n+1}=x_{n}+x_{n-1}$ for $n \geqslant 1$. Prove:

  (i) $\left(x_{n+1}, x_{n}\right)=1$ and $\left(x_{n+2}, x_{n}\right)=1$ for every $n \geqslant 0$;

  (ii) $x_{n+3} \equiv x_{n}(\bmod 2)$ and $x_{n+8} \equiv x_{n}(\bmod 3)$ for every $n \geqslant 0$;

  (iii) if $n \equiv 0(\bmod 5)$ then $x_{n} \equiv 0(\bmod 5)$.

  comment

• 4.II.8C

  Numbers and Sets | Part IA, 2003

  Let $X$ be a finite set with $n$ elements. How many functions are there from $X$ to $X$ ? How many relations are there on $X$ ?

  Show that the number of relations $R$ on $X$ such that, for each $y \in X$, there exists at least one $x \in X$ with $x R y$, is $\left(2^{n}-1\right)^{n}$.

  Using the inclusion-exclusion principle or otherwise, deduce that the number of such relations $R$ for which, in addition, for each $x \in X$, there exists at least one $y \in X$ with $x R y$, is

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

  comment

2002

• 4.I.1C

  Numbers and Sets | Part IA, 2002

  What does it mean to say that a function $f: A \rightarrow B$ is injective? What does it mean to say that a function $g: A \rightarrow B$ is surjective?

  Consider the functions $f: A \rightarrow B, g: B \rightarrow C$ and their composition $g \circ f: A \rightarrow C$ given by $g \circ f(a)=g(f(a))$. Prove the following results.

  (i) If $f$ and $g$ are surjective, then so is $g \circ f$.

  (ii) If $f$ and $g$ are injective, then so is $g \circ f$.

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

  (iv) If $g \circ f$ is surjective, then so is $g$.

  Give an example where $g \circ f$ is injective and surjective but $f$ is not surjective and $g$ is not injective.

  comment

• 4.I.2C

  Numbers and Sets | Part IA, 2002

  If $f, g: \mathbb{R} \rightarrow \mathbb{R}$ are infinitely differentiable, Leibniz's rule states that, if $n \geqslant 1$,

  $$\frac{d^{n}}{d x^{n}}(f(x) g(x))=\sum_{r=0}^{n}\left(\begin{array}{c} n \\ r \end{array}\right) f^{(n-r)}(x) g^{(r)}(x)$$

  Prove this result by induction. (You should prove any results on binomial coefficients that you need.)

  comment

• 4.II $. 7 \mathrm{~B} \quad$

  Numbers and Sets | Part IA, 2002

  (a) Suppose that $p$ is an odd prime. Find $1^{p}+2^{p}+\ldots+(p-1)^{p}$ modulo $p$.

  (b) Find $(p-1)$ ! modulo $(1+2+\ldots+(p-1))$, when $p$ is an odd prime.

  comment

• 4.II.5F

  Numbers and Sets | Part IA, 2002

  What is meant by saying that a set is countable?

  Prove that the union of countably many countable sets is itself countable.

  Let $\left\{J_{i}: i \in I\right\}$ be a collection of disjoint intervals of the real line, each having strictly positive length. Prove that the index set $I$ is countable.

  comment

• 4.II.6F

  Numbers and Sets | Part IA, 2002

  (a) Let $S$ be a finite set, and let $\mathbb{P}(S)$ be the power set of $S$, that is, the set of all subsets of $S$. Let $f: \mathbb{P}(S) \rightarrow \mathbb{R}$ be additive in the sense that $f(A \cup B)=f(A)+f(B)$ whenever $A \cap B=\varnothing$. Show that, for $A_{1}, A_{2}, \ldots, A_{n} \in \mathbb{P}(S)$,

  $$\begin{aligned} f\left(\bigcup_{i} A_{i}\right)=\sum_{i} f\left(A_{i}\right)-\sum_{i<j} f\left(A_{i} \cap A_{j}\right) &+\sum_{i<j<k} f\left(A_{i} \cap A_{j} \cap A_{k}\right) \\ &-\cdots+(-1)^{n+1} f\left(\bigcap_{i} A_{i}\right) \end{aligned}$$

  (b) Let $A_{1}, A_{2}, \ldots, A_{n}$ be finite sets. Deduce from part (a) the inclusion-exclusion formula for the size (or cardinality) of $\bigcup_{i} A_{i}$.

  (c) A derangement of the set $S=\{1,2, \ldots, n\}$ is a permutation $\pi$ (that is, a bijection from $S$ to itself) in which no member of the set is fixed (that is, $\pi(i) \neq i$ for all $i$ ). Using the inclusion-exclusion formula, show that the number $d_{n}$ of derangements satisfies $d_{n} / n ! \rightarrow e^{-1}$ as $n \rightarrow \infty$.

  comment

• 4.II.8B

  Numbers and Sets | Part IA, 2002

  Suppose that $a, b$ are coprime positive integers. Write down an integer $d>0$ such that $a^{d} \equiv 1$ modulo $b$. The least such $d$ is the order of $a$ modulo $b$. Show that if the order of $a$ modulo $b$ is $y$, and $a^{x} \equiv 1$ modulo $b$, then $y$ divides $x$.

  Let $n \geqslant 2$ and $F_{n}=2^{2^{n}}+1$. Suppose that $p$ is a prime factor of $F_{n}$. Find the order of 2 modulo $p$, and show that $p \equiv 1$ modulo $2^{n+1}$.

  comment

2001

• 4.I.1E

  Numbers and Sets | Part IA, 2001

  (a) Show that, given a set $X$, there is no bijection between $X$ and its power set.

  (b) Does there exist a set whose members are precisely those sets that are not members of themselves? Justify your answer.

  comment

• 4.I.2E

  Numbers and Sets | Part IA, 2001

  Prove, by induction or otherwise, that

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

  Find the number of sequences consisting of zeroes and ones that contain exactly $n$ zeroes and at most $m$ ones.

  comment

• 4.II.5E

  Numbers and Sets | Part IA, 2001

  (a) Prove Wilson's theorem, that $(p-1) ! \equiv-1(\bmod p)$, where $p$ is prime.

  (b) Suppose that $p$ is an odd prime. Express $1^{2} .3^{2} .5^{2} \ldots(p-2)^{2}(\bmod p)$ as a power of $-1$.

  [Hint: $k \equiv-(p-k)(\bmod p)$.]

  comment

• 4.II.6E

  Numbers and Sets | Part IA, 2001

  State and prove the principle of inclusion-exclusion. Use it to calculate $\phi(4199)$, where $\phi$ is Euler's $\phi$-function.

  In a certain large college, a survey revealed that $90 \%$ of the fellows detest at least one of the pop stars Hairy, Dirty and Screamer. $45 \%$ detest Hairy, $28 \%$ detest Dirty and $46 \%$ detest Screamer. If $27 \%$ detest only Screamer and $6 \%$ detest all three, what proportion detest Hairy and Dirty but not Screamer?

  comment

• 4.II.7E

  Numbers and Sets | Part IA, 2001

  (a) Prove that, if $p$ is prime and $a$ is not a multiple of $p$, then $a^{p-1} \equiv 1(\bmod p)$.

  (b) The order of $a(\bmod p)$ is the least positive integer $d$ such that $a^{d} \equiv 1(\bmod p)$. Suppose now that $a^{x} \equiv 1(\bmod p)$; what can you say about $x$ in terms of $d$ ? Show that $p \equiv 1(\bmod d)$.

  (c) Suppose that $p$ is an odd prime. What is the order of $x(\bmod p)$ if $x^{2} \equiv-1(\bmod p)$ ? Find a condition on $p(\bmod 4)$ that is equivalent to the existence of an integer $x$ with $x^{2} \equiv-1(\bmod p)$.

  comment

• 4.II.8E

  Numbers and Sets | Part IA, 2001

  What is the Principle of Mathematical Induction? Derive it from the statement that every non-empty set of positive integers has a least element.

  Prove, by induction on $n$, that $9^{n} \equiv 2^{n}(\bmod 7)$ for all $n \geq 1$.

  What is wrong with the following argument?

  "Theorem: $\sum_{i=1}^{n} i=n(n+1) / 2+126$.

  Proof: Assume that $m \geq 1$ and $\sum_{i=1}^{m} i=m(m+1) / 2+126$. Add $m+1$ to both sides to get

  $$\sum_{i=1}^{m+1} i=m(m+1) / 2+m+1+126=(m+1)(m+2) / 2+126$$

  So, by induction, the theorem is proved."

  comment