Number Theory

2021

• Paper 1, Section I, 1I

  Number Theory | Part II, 2021

  State Euler's criterion.

  Let $p$ be an odd prime. Show that every primitive root modulo $p$ is a quadratic non-residue modulo $p$.

  Let $p$ be a Fermat prime, that is, a prime of the form $2^{2^{k}}+1$ for some $k \geqslant 1$. By evaluating $\phi(p-1)$, or otherwise, show that every quadratic non-residue modulo $p$ is a primitive root modulo $p$. Deduce that 3 is a primitive root modulo $p$ for every Fermat prime $p$.

  comment

• Paper 2, Section $I$, I

  Number Theory | Part II, 2021

  Define the Möbius function $\mu$, and explain what it means for it to be multiplicative.

  Show that for every positive integer $n$

  $$\sum_{d \mid n} \frac{\mu(d)^{2}}{\phi(d)}=\frac{n}{\phi(n)}$$

  where $\phi$ is the Euler totient function.

  Fix an integer $k \geqslant 1$. Use the Chinese remainder theorem to show that there are infinitely many positive integers $n$ for which

  $$\mu(n)=\mu(n+1)=\cdots=\mu(n+k)$$

  comment

• Paper 3, Section I, I

  Number Theory | Part II, 2021

  Define the continued fraction expansion of $\theta \in \mathbb{R}$, and show that this expansion terminates if and only if $\theta \in \mathbb{Q}$.

  Define the convergents $\left(p_{n} / q_{n}\right)_{n \geqslant-1}$ of the continued fraction expansion of $\theta$, and show that for all $n \geqslant 0$,

  $$p_{n} q_{n-1}-p_{n-1} q_{n}=(-1)^{n-1} .$$

  Deduce that if $\theta \in \mathbb{R} \backslash \mathbb{Q}$, then for all $n \geqslant 0$, at least one of

  $$\left|\theta-\frac{p_{n}}{q_{n}}\right|<\frac{1}{2 q_{n}^{2}} \quad \text { and } \quad\left|\theta-\frac{p_{n+1}}{q_{n+1}}\right|<\frac{1}{2 q_{n+1}^{2}}$$

  must hold.

  [You may assume that $\theta$ lies strictly between $p_{n} / q_{n}$ and $p_{n+1} / q_{n+1}$ for all $n \geqslant 0 .$ ]

  comment

• Paper 3, Section II, I

  Number Theory | Part II, 2021

  State what it means for two binary quadratic forms to be equivalent, and define the class number $h(d)$.

  Let $m$ be a positive integer, and let $f$ be a binary quadratic form. Show that $f$ properly represents $m$ if and only if $f$ is equivalent to a binary quadratic form

  $$m x^{2}+b x y+c y^{2}$$

  for some integers $b$ and $c$.

  Let $d<0$ be an integer such that $d \equiv 0$ or $1 \bmod 4$. Show that $m$ is properly represented by some binary quadratic form of discriminant $d$ if and only if $d$ is a square modulo $4 m$.

  Fix a positive integer $A \geqslant 2$. Show that $n^{2}+n+A$ is composite for some integer $n$ such that $0 \leqslant n \leqslant A-2$ if and only if $d=1-4 A$ is a square modulo $4 p$ for some prime $p<A$.

  Deduce that $h(1-4 A)=1$ if and only if $n^{2}+n+A$ is prime for all $n=0,1, \ldots, A-2$.

  comment

• Paper 4, Section I, I

  Number Theory | Part II, 2021

  Let $p$ be a prime, and let $N=\left(\begin{array}{c}2 n \\ n\end{array}\right)$ for some positive integer $n$.

  Show that if a prime power $p^{k}$ divides $N$ for some $k \geqslant 1$, then $p^{k} \leqslant 2 n$.

  Given a positive real $x$, define $\psi(x)=\sum_{n \leqslant x} \Lambda(n)$, where $\Lambda(n)$ is the von Mangoldt function, taking the value $\log p$ if $n=p^{k}$ for some prime $p$ and integer $k \geqslant 1$, and 0 otherwise. Show that

  $$\psi(x)=\sum_{p \leqslant x, p \text { prime }}\left\lfloor\frac{\log x}{\log p}\right\rfloor \log p$$

  Deduce that for all integers $n>1, \psi(2 n) \geqslant n \log 2$.

  comment

• Paper 4, Section II, I

  Number Theory | Part II, 2021

  (a) Let $N \geqslant 3$ be an odd integer and $b$ an integer with $(b, N)=1$. What does it mean to say that $N$ is a (Fermat) pseudoprime to base b?

  Let $b, k \geqslant 2$ be integers. Show that if $N \geqslant 3$ is an odd composite integer dividing $b^{k}-1$ and satisfying $N \equiv 1 \bmod k$, then $N$ is a pseudoprime to base $b$.

  (b) Fix $b \geqslant 2$. Let $p$ be an odd prime not dividing $b^{2}-1$, and let

  $$n=\frac{b^{p}-1}{b-1} \quad \text { and } \quad m=\frac{b^{p}+1}{b+1} .$$

  Use the conclusion of part (a) to show that $N=n m$ is a pseudoprime to base $b$. Deduce that there are infinitely many pseudoprimes to base $b$.

  (c) Let $b, k \geqslant 2$ be integers, and let $n=p_{1} \cdots p_{k}$, where $p_{1}, p_{2}, \ldots, p_{k}$ are distinct primes not dividing $2 b$. For each $j=1,2, \ldots, k$, let $r_{j}=n / p_{j}$. Show that $n$ is a pseudoprime to base $b$ if and only if for all $j=1,2, \ldots, k$, the order of $b$ modulo $p_{j}$ divides $r_{j}-1$.

  (d) By considering products of prime factors of $2^{k}-1$ and $2^{k}+1$ for primes $k \geqslant 5$, deduce that there are infinitely many pseudoprimes to base 2 with two prime factors.

  [Hint: You may assume that $\operatorname{gcd}(j, k)=1$ for $j, k \geqslant 1$ implies $\operatorname{gcd}\left(2^{j}-1,2^{k}-1\right)=1$, and that for $k>3,2^{k}+1$ is not a power of 3.]

  comment

2020

• Paper 1, Section I, H

  Number Theory | Part II, 2020

  What does it mean to say that a positive definite binary quadratic form is reduced?

  Find all reduced binary quadratic forms of discriminant $-20$.

  Prove that if a prime $p \neq 5$ is represented by $x^{2}+5 y^{2}$, then $p \equiv 1,3,7$ or $9 \bmod 20$.

  comment

• Paper 2, Section I, $1 \mathbf{H}$

  Number Theory | Part II, 2020

  Let $\theta \in \mathbb{R}$.

  For each integer $n \geqslant-1$, define the convergents $p_{n} / q_{n}$ of the continued fraction expansion of $\theta$. Show that for all $n \geqslant 0, p_{n} q_{n-1}-p_{n-1} q_{n}=(-1)^{n-1}$. Deduce that if $q \in \mathbb{N}$ and $p \in \mathbb{Z}$ satisfy

  $$\left|\theta-\frac{p}{q}\right|<\left|\theta-\frac{p_{n}}{q_{n}}\right|$$

  then $q>q_{n}$.

  Compute the continued fraction expansion of $\sqrt{12}$. Hence or otherwise find a solution in positive integers $x$ and $y$ to the equation $x^{2}-12 y^{2}=1$.

  comment

• Paper 3, Section I, $1 \mathrm{H}$

  Number Theory | Part II, 2020

  Let $N \geqslant 3$ be an odd integer and $b$ an integer with $(b, N)=1$. What does it mean to say that $N$ is an Euler pseudoprime to base $b$ ?

  Show that if $N$ is not an Euler pseudoprime to some base $b_{0}$, then it is not an Euler pseudoprime to at least half the bases $\{1 \leqslant b<N:(b, N)=1\}$.

  Show that if $N$ is odd and composite, then there exists an integer $b$ such that $N$ is not an Euler pseudoprime to base $b$.

  comment

• Paper 3, Section II, 11H

  Number Theory | Part II, 2020

  Let $p$ be an odd prime.

  (i) Define the Legendre symbol $\left(\frac{x}{p}\right)$, and show that when $(x, p)=1$, then $\left(\frac{x^{-1}}{p}\right)=\left(\frac{x}{p}\right)$.

  (ii) State and prove Gauss's lemma, and use it to evaluate $\left(\frac{-1}{p}\right)$. [You may assume Euler's criterion.]

  (iii) Prove that

  $$\sum_{x=1}^{p}\left(\frac{x}{p}\right)=0$$

  and deduce that

  $$\sum_{x=1}^{p}\left(\frac{x(x+1)}{p}\right)=-1$$

  Hence or otherwise determine the number of pairs of consecutive integers $z, z+1$ such that $1 \leqslant z, z+1 \leqslant p-1$ and both $z$ and $z+1$ are quadratic residues $\bmod p$.

  comment

• Paper 4 , Section II, 11H

  Number Theory | Part II, 2020

  (a) What does it mean to say that a function $f: \mathbb{N} \rightarrow \mathbb{C}$ is multiplicative? Show that if $f, g: \mathbb{N} \rightarrow \mathbb{C}$ are both multiplicative, then so is $f \star g: \mathbb{N} \rightarrow \mathbb{C}$, defined for all $n \in \mathbb{N}$ by

  $$f \star g(n)=\sum_{d \mid n} f(d) g\left(\frac{n}{d}\right)$$

  Show that if $f=\mu \star g$, where $\mu$ is the Möbius function, then $g=f \star 1$, where 1 denotes the constant function 1 .

  (b) Let $\tau(n)$ denote the number of positive divisors of $n$. Find $f, g: \mathbb{N} \rightarrow \mathbb{C}$ such that $\tau=f \star g$, and deduce that $\tau$ is multiplicative. Hence or otherwise show that for all $s \in \mathbb{C}$ with $\operatorname{Re}(s)>1$,

  $$\sum_{n=1}^{\infty} \frac{\tau(n)}{n^{s}}=\zeta(s)^{2}$$

  where $\zeta$ is the Riemann zeta function.

  (c) Fix $k \in \mathbb{N}$. By considering suitable powers of the product of the first $k+1$ primes, show that

  $$\tau(n) \geqslant(\log n)^{k}$$

  for infinitely many $n \in \mathbb{N}$.

  (d) Fix $\epsilon>0$. Show that

  $$\frac{\tau(n)}{n^{\epsilon}}=\prod_{p \text { prime, } p^{\alpha}|| n} \frac{(\alpha+1)}{p^{\alpha \epsilon}}$$

  where $p^{\alpha} \| n$ denotes the fact that $\alpha \in \mathbb{N}$ is such that $p^{\alpha} \mid n$ but $p^{\alpha+1} \nmid n$. Deduce that there exists a positive constant $C(\epsilon)$ depending only on $\epsilon$ such that for all $n \in \mathbb{N}, \tau(n) \leqslant C(\epsilon) n^{\epsilon} .$

  comment

• Paper 4, Section I, H

  Number Theory | Part II, 2020

  Let $p$ be a prime.

  State and prove Lagrange's theorem on the number of solutions of a polynomial congruence modulo $p$. Deduce that $(p-1) ! \equiv-1 \bmod p$.

  Let $k$ be a positive integer such that $k \mid(p-1)$. Show that the congruence

  $$x^{k} \equiv 1 \quad \bmod p$$

  has precisely $k$ solutions modulo $p$.

  comment

2019

• Paper 1, Section I, I

  Number Theory | Part II, 2019

  (a) State and prove the Chinese remainder theorem.

  (b) Let $N$ be an odd positive composite integer, and $b$ a positive integer with $(b, N)=1$. What does it mean to say that $N$ is a Fermat pseudoprime to base b? Show that 35 is a Fermat pseudoprime to base $b$ if and only if $b$ is congruent to one of $1,6,29$ or $34(\bmod 35)$.

  comment

• Paper 2, Section I, I

  Number Theory | Part II, 2019

  Define the Jacobi symbol $\left(\frac{a}{n}\right)$, where $a, n \in \mathbb{Z}$ and $n$ is odd and positive.

  State and prove the Law of Quadratic Reciprocity for the Jacobi symbol. [You may use Quadratic Reciprocity for the Legendre symbol without proof but should state it clearly.]

  Compute the Jacobi symbol $\left(\frac{503}{2019}\right)$.

  comment

• Paper 3, Section I, I

  Number Theory | Part II, 2019

  Let $f=(a, b, c)$ be a positive definite binary quadratic form with integer coefficients. What does it mean to say that $f$ is reduced? Show that if $f$ is reduced and has discriminant $d$, then $|b| \leqslant a \leqslant \sqrt{|d| / 3}$ and $b \equiv d(\bmod 2)$. Deduce that for fixed $d<0$, there are only finitely many reduced $f$ of discriminant $d$.

  Find all reduced positive definite binary quadratic forms of discriminant $-15$.

  comment

• Paper 3, Section II, I

  Number Theory | Part II, 2019

  Let $p>2$ be a prime.

  (a) What does it mean to say that an integer $g$ is a primitive root $\bmod p$ ?

  (b) Let $k$ be an integer with $0 \leqslant k<p-1$. Let

  $$S_{k}=\sum_{x=0}^{p-1} x^{k}$$

  Show that $S_{k} \equiv 0(\bmod p)$. [Recall that by convention $0^{0}=1$.]

  (c) Let $f(X, Y, Z)=a X^{2}+b Y^{2}+c Z^{2}$ for some $a, b, c \in \mathbb{Z}$, and let $g=1-f^{p-1}$. Show that for any $x, y, z \in \mathbb{Z}, g(x, y, z) \equiv 0$ or $1(\bmod p)$, and that

  $$\sum_{x, y, z \in\{0,1, \ldots, p-1\}} g(x, y, z) \equiv 0 \quad(\bmod p) .$$

  Hence show that there exist integers $x, y, z$, not all divisible by $p$, such that $f(x, y, z) \equiv 0$ $(\bmod p)$.

  comment

• Paper 4, Section I, I

  Number Theory | Part II, 2019

  Show that the product

  $$\prod_{p \text { prime }}\left(1-\frac{1}{p}\right)^{-1}$$

  and the series

  $$\sum_{p \text { prime }} \frac{1}{p}$$

  are both divergent.

  comment

• Paper 4, Section II, I

  Number Theory | Part II, 2019

  (a) Let $a_{0}, a_{1}, \ldots$ be positive integers, and $\beta>0$ a positive real number. Show that for every $n \geqslant 0$, if $\theta_{n}=\left[a_{0}, \ldots, a_{n}, \beta\right]$, then $\theta_{n}=\left(\beta p_{n}+p_{n-1}\right) /\left(\beta q_{n}+q_{n-1}\right)$, where $\left(p_{n}\right)$, $\left(q_{n}\right)(n \geqslant-1)$ are sequences of integers satisfying

  $$\begin{aligned} &p_{0}=a_{0}, q_{0}=1, \quad p_{-1}=1, \quad q_{-1}=0 \quad \text { and } \\ &\left(\begin{array}{cc} p_{n} & p_{n-1} \\ q_{n} & q_{n-1} \end{array}\right)=\left(\begin{array}{cc} p_{n-1} & p_{n-2} \\ q_{n-1} & q_{n-2} \end{array}\right)\left(\begin{array}{cc} a_{n} & 1 \\ 1 & 0 \end{array}\right) \quad(n \geqslant 1) \end{aligned}$$

  Show that $p_{n} q_{n-1}-p_{n-1} q_{n}=(-1)^{n-1}$, and that $\theta_{n}$ lies between $p_{n} / q_{n}$ and $p_{n-1} / q_{n-1}$.

  (b) Show that if $\left[a_{0}, a_{1}, \ldots\right]$ is the continued fraction expansion of a positive irrational $\theta$, then $p_{n} / q_{n} \rightarrow \theta$ as $n \rightarrow \infty$.

  (c) Let the convergents of the continued fraction $\left[a_{0}, a_{1}, \ldots, a_{n}\right]$ be $p_{j} / q_{j}(0 \leqslant$ $j \leqslant n)$. Using part (a) or otherwise, show that the $n$-th and $(n-1)$-th convergents of $\left[a_{n}, a_{n-1}, \ldots, a_{0}\right]$ are $p_{n} / p_{n-1}$ and $q_{n} / q_{n-1}$ respectively.

  (d) Show that if $\theta=\left[\overline{a_{0}, a_{1}, \ldots, a_{n}}\right]$ is a purely periodic continued fraction with convergents $p_{j} / q_{j}$, then $f(\theta)=0$, where $f(X)=q_{n} X^{2}+\left(q_{n-1}-p_{n}\right) X-p_{n-1}$. Deduce that if $\theta^{\prime}$ is the other root of $f(X)$, then $-1 / \theta^{\prime}=\left[\overline{a_{n}, a_{n-1}, \ldots, a_{0}}\right]$.

  comment

2018

• Paper 1, Section I, G

  Number Theory | Part II, 2018

  (a) State and prove the Chinese remainder theorem.

  (b) An integer $n$ is squarefull if whenever $p$ is prime and $p \mid n$, then $p^{2} \mid n$. Show that there exist 1000 consecutive positive integers, none of which are squarefull.

  comment

• Paper 2, Section I, G

  Number Theory | Part II, 2018

  Define the Legendre symbol, and state Gauss's lemma. Show that if $p$ is an odd prime, then

  $$\left(\frac{2}{p}\right)=(-1)^{\left(p^{2}-1\right) / 8}$$

  Use the law of quadratic reciprocity to compute $\left(\frac{105}{149}\right)$.

  comment

• Paper 3, Section I, G

  Number Theory | Part II, 2018

  What is a multiplicative function? Show that if $f(n)$ is a multiplicative function, then so is $g(n)=\sum_{d \mid n} f(d)$.

  Define the Möbius function $\mu(n)$, and show that it is multiplicative. Deduce that

  $$\sum_{d \mid n} \mu(d)= \begin{cases}1 & \text { if } n=1 \\ 0 & \text { if } n>1\end{cases}$$

  and that

  $$f(n)=\sum_{e \mid n} \mu(e) g\left(\frac{n}{e}\right) .$$

  What is $g(n)$ if $f(n)=n ?$ What is $f(n)$ if $g(n)=n ?$

  comment

• Paper 3, Section II, G

  Number Theory | Part II, 2018

  What does it mean to say that a positive definite binary quadratic form is reduced? What does it mean to say that two binary quadratic forms are equivalent? Show that every positive definite binary quadratic form is equivalent to some reduced form.

  Show that the reduced positive definite binary quadratic forms of discriminant $-35$ are $f_{1}=x^{2}+x y+9 y^{2}$ and $f_{2}=3 x^{2}+x y+3 y^{2}$. Show also that a prime $p>7$ is represented by $f_{i}$ if and only if

  $$\left(\frac{p}{5}\right)=\left(\frac{p}{7}\right)= \begin{cases}+1 & (i=1) \\ -1 & (i=2)\end{cases}$$

  comment

• Paper 4, Section I, G

  Number Theory | Part II, 2018

  Show that if a continued fraction is periodic, then it represents a quadratic irrational. What number is represented by the continued fraction $[7,7,7, \ldots]$ ?

  Compute the continued fraction expansion of $\sqrt{23}$. Hence or otherwise find a solution in positive integers to the equation $x^{2}-23 y^{2}=1$.

  comment

• Paper 4, Section II, G

  Number Theory | Part II, 2018

  (a) State and prove the Fermat-Euler theorem. Let $p$ be a prime and $k$ a positive integer. Show that $b^{k} \equiv b(\bmod p)$ holds for every integer $b$ if and only if $k \equiv 1(\bmod p-1)$.

  (b) Let $N \geqslant 3$ be an odd integer and $b$ be an integer with $(b, N)=1$. What does it mean to say that $N$ is a Fermat pseudoprime to base $b$ ? What does it mean to say that $N$ is a Carmichael number?

  Show that every Carmichael number is squarefree, and that if $N$ is squarefree, then $N$ is a Carmichael number if and only if $N \equiv 1(\bmod p-1)$ for every prime divisor $p$ of $N$. Deduce that a Carmichael number is a product of at least three primes.

  (c) Let $r$ be a fixed odd prime. Show that there are only finitely many pairs of primes $p, q$ for which $N=p q r$ is a Carmichael number.

  [You may assume throughout that $\left(\mathbb{Z} / p^{n} \mathbb{Z}\right)^{*}$ is cyclic for every odd prime $p$ and every integer $n \geqslant 1 .]$

  comment

2017

• Paper 1, Section $I$, G

  Number Theory | Part II, 2017

  Define the Legendre symbol $\left(\frac{a}{p}\right)$.

  State Gauss' lemma and use it to compute $\left(\frac{2}{p}\right)$ where $p$ is an odd prime.

  Show that if $m \geqslant 4$ is a power of 2 , and $p$ is a prime dividing $2^{m}+1$, then $p \equiv 1(\bmod 4 m)$.

  comment

• Paper 2, Section I, G

  Number Theory | Part II, 2017

  State and prove Legendre's formula for $\pi(x)$. Use it to compute $\pi(42)$.

  comment

• Paper 3, Section I, G

  Number Theory | Part II, 2017

  Explain what is meant by an Euler pseudoprime and a strong pseudoprime. Show that 65 is an Euler pseudoprime to the base $b$ if and only if $b^{2} \equiv \pm 1(\bmod 65)$. How many such bases are there? Show that the bases for which 65 is a strong pseudoprime do not form a subgroup of $(\mathbb{Z} / 65 \mathbb{Z})^{\times}$.

  comment

• Paper 3, Section II, G

  Number Theory | Part II, 2017

  Let $d$ be a positive integer which is not a square. Assume that the continued fraction expansion of $\sqrt{d}$ takes the form $\left[a_{0}, \overline{a_{1}, a_{2}, \ldots, a_{m}}\right]$.

  (a) Define the convergents $p_{n} / q_{n}$, and show that $p_{n}$ and $q_{n}$ are coprime.

  (b) The complete quotients $\theta_{n}$ may be written in the form $\left(\sqrt{d}+r_{n}\right) / s_{n}$, where $r_{n}$ and $s_{n}$ are rational numbers. Use the relation

  $$\sqrt{d}=\frac{\theta_{n} p_{n-1}+p_{n-2}}{\theta_{n} q_{n-1}+q_{n-2}}$$

  to find formulae for $r_{n}$ and $s_{n}$ in terms of the $p$ 's and $q$ 's. Deduce that $r_{n}$ and $s_{n}$ are integers.

  (c) Prove that Pell's equation $x^{2}-d y^{2}=1$ has infinitely many solutions in integers $x$ and $y$.

  (d) Find integers $x$ and $y$ satisfying $x^{2}-67 y^{2}=-2$.

  comment

• Paper 4, Section I, G

  Number Theory | Part II, 2017

  Show that, for $x \geqslant 2$ a real number,

  $$\prod_{\substack{p \leqslant x \\ p \text { is prime }}}\left(1-\frac{1}{p}\right)^{-1}>\log x$$

  Hence prove that

  $$\sum_{\substack{p \leqslant x, p \text { is prime }}} \frac{1}{p}>\log \log x+c,$$

  where $c$ is a constant you should make explicit.

  comment

• Paper 4, Section II, 10G

  Number Theory | Part II, 2017

  (a) State Dirichlet's theorem on primes in arithmetic progression.

  (b) Let $d$ be the discriminant of a binary quadratic form, and let $p$ be an odd prime. Show that $p$ is represented by some binary quadratic form of discriminant $d$ if and only if $x^{2} \equiv d(\bmod p)$ is soluble.

  (c) Let $f(x, y)=x^{2}+15 y^{2}$ and $g(x, y)=3 x^{2}+5 y^{2}$. Show that $f$ and $g$ each represent infinitely many primes. Are there any primes represented by both $f$ and $g$ ?

  comment

2016

• Paper 1, Section I, I

  Number Theory | Part II, 2016

  Define the Riemann zeta function $\zeta(s)$ for $\operatorname{Re}(s)>1$. State and prove the alternative formula for $\zeta(s)$ as an Euler product. Hence or otherwise show that $\zeta(s) \neq 0$ for $\operatorname{Re}(s)>1$.

  comment

• Paper 2, Section I, I

  Number Theory | Part II, 2016

  Define the Legendre symbol and the Jacobi symbol. Compute the Jacobi symbols $\left(\frac{202}{11189}\right)$ and $\left(\frac{974}{1001}\right)$, stating clearly any properties of these symbols that you use.

  comment

• Paper 3, Section I, I

  Number Theory | Part II, 2016

  Show that the exact power of a prime $p$ dividing $N !$ is $\sum_{j=1}^{\infty}\left\lfloor\frac{N}{p^{j}}\right\rfloor$. By considering the prime factorisation of $\left(\begin{array}{c}2 n \\ n\end{array}\right)$, show that

  $$\frac{4^{n}}{2 n+1} \leqslant\left(\begin{array}{c} 2 n \\ n \end{array}\right) \leqslant(2 n)^{\pi(2 n)}$$

  Setting $n=\left\lfloor\frac{x}{2}\right\rfloor$, deduce that for $x$ sufficiently large

  $$\pi(x)>\frac{\left\lfloor\frac{x}{2}\right\rfloor \log 3}{\log x}>\frac{x}{2 \log x}$$

  comment

• Paper 3, Section II, I

  Number Theory | Part II, 2016

  What does it mean for a positive definite binary quadratic form to be reduced?

  Prove that every positive definite binary quadratic form is equivalent to a reduced form, and that there are only finitely many reduced forms with given discriminant.

  State a criterion for a positive integer $n$ to be represented by a positive definite binary quadratic form with discriminant $d<0$, and hence determine which primes $p$ are represented by $x^{2}+x y+7 y^{2}$.

  comment

• Paper 4 , Section I, I

  Number Theory | Part II, 2016

  Compute the continued fraction expansion of $\sqrt{14}$, and use it to find two solutions to $x^{2}-14 y^{2}=2$ where $x$ and $y$ are positive integers.

  comment

• Paper 4, Section II, 10I

  Number Theory | Part II, 2016

  (a) Define Euler's totient function $\phi(n)$ and show that $\sum_{d \mid n} \phi(d)=n$.

  (b) State Lagrange's theorem concerning roots of polynomials mod $p$.

  (c) Let $p$ be a prime. Proving any results you need about primitive roots, show that $x^{m} \equiv 1(\bmod p)$ has exactly $(m, p-1)$ roots.

  (d) Show that if $p$ and $3 p-2$ are both primes then $N=p(3 p-2)$ is a Fermat pseudoprime for precisely a third of all bases.

  comment

2015

• Paper 1, Section I, H

  Number Theory | Part II, 2015

  Define the Legendre symbol $\left(\frac{a}{p}\right)$. State and prove Euler's criterion, assuming if you wish the existence of primitive roots $\bmod p$.

  By considering the prime factors of $n^{2}+4$ for $n$ an odd integer, prove that there are infinitely many primes $p$ with $p \equiv 5(\bmod 8)$.

  comment

• Paper 2, Section I, H

  Number Theory | Part II, 2015

  Define the Euler totient function $\phi$ and the Möbius function $\mu$. Suppose $f$ and $g$ are functions defined on the natural numbers satisfying $f(n)=\sum_{d \mid n} g(d)$. State and prove a formula for $g$ in terms of $f$. Find a relationship between $\mu$ and $\phi$.

  Define the Riemann zeta function $\zeta(s)$. Find a Dirichlet series for $\zeta(s-1) / \zeta(s)$ valid for $\operatorname{Re}(s)>2$.

  comment

• Paper 3, Section I, H

  Number Theory | Part II, 2015

  What does it mean to say that a positive definite binary quadratic form is reduced? Find the three smallest positive integers properly represented by each of the forms $f(x, y)=3 x^{2}+8 x y+9 y^{2}$ and $g(x, y)=15 x^{2}+34 x y+20 y^{2}$. Show that every odd integer represented by some positive definite binary quadratic form with discriminant $-44$ is represented by at least one of the forms $f$ and $g$.

  comment

• Paper 3, Section II, H

  Number Theory | Part II, 2015

  Let $\theta$ be a real number with continued fraction expansion $\left[a_{0}, a_{1}, a_{2}, \ldots\right]$. Define the convergents $p_{n} / q_{n}$ (by means of recurrence relations) and show that for $\beta>0$ we have

  $$\left[a_{0}, a_{1}, \ldots, a_{n-1}, \beta\right]=\frac{\beta p_{n-1}+p_{n-2}}{\beta q_{n-1}+q_{n-2}}$$

  Show that

  $$\left|\theta-\frac{p_{n}}{q_{n}}\right|<\frac{1}{q_{n} q_{n+1}}$$

  and deduce that $p_{n} / q_{n} \rightarrow \theta$ as $n \rightarrow \infty$.

  By computing a suitable continued fraction expansion, find solutions in positive integers $x$ and $y$ to each of the equations $x^{2}-53 y^{2}=4$ and $x^{2}-53 y^{2}=-7$.

  comment

• Paper 4, Section I, H

  Number Theory | Part II, 2015

  Show that if $10^{n}+1$ is prime then $n$ must be a power of 2 . Now assuming $n$ is a power of 2 , show that if $p$ is a prime factor of $10^{n}+1$ then $p \equiv 1(\bmod 2 n)$.

  Explain the method of Fermat factorization, and use it to factor $10^{4}+1$.

  comment

• Paper 4, Section II, H

  Number Theory | Part II, 2015

  State the Chinese Remainder Theorem.

  Let $N$ be an odd positive integer. Define the Jacobi symbol $\left(\frac{a}{N}\right)$. Which of the following statements are true, and which are false? Give a proof or counterexample as appropriate.

  (i) If $\left(\frac{a}{N}\right)=1$ then the congruence $x^{2} \equiv a(\bmod N)$ is soluble.

  (ii) If $N$ is not a square then $\sum_{a=1}^{N}\left(\frac{a}{N}\right)=0$.

  (iii) If $N$ is composite then there exists an integer a coprime to $N$ with

  $$a^{N-1} \not \equiv 1 \quad(\bmod N)$$

  (iv) If $N$ is composite then there exists an integer $a$ coprime to $N$ with

  $$a^{(N-1) / 2} \not \equiv\left(\frac{a}{N}\right) \quad(\bmod N)$$

  comment

2014

• Paper 1, Section I, $1 F$

  Number Theory | Part II, 2014

  Define what it means for a number $N$ to be a pseudoprime to the base $b$.

  Show that if there is a base $b$ to which $N$ is not a pseudoprime, then $N$ is a pseudoprime to at most half of all possible bases.

  Let $n$ be an integer greater than 1 such that $F_{n}=2^{2^{n}}+1$ is composite. Show that $F_{n}$ is a pseudoprime to the base 2 .

  comment

• Paper 2, Section I, F

  Number Theory | Part II, 2014

  Show that

  $$\sum_{p \leqslant x} \frac{1}{p} \geqslant \log \log x-\frac{1}{2}$$

  Deduce that there are infinitely many primes.

  comment

• Paper 3, Section I, $1 F$

  Number Theory | Part II, 2014

  Show that the continued fraction for $\sqrt{51}$ is $[7 ; \overline{7,14}]$.

  Hence, or otherwise, find positive integers $x$ and $y$ that satisfy the equation $x^{2}-51 y^{2}=1 .$

  Are there integers $x$ and $y$ such that $x^{2}-51 y^{2}=-1$ ?

  comment

• Paper 3, Section II, F

  Number Theory | Part II, 2014

  State and prove Lagrange's theorem about polynomial congruences modulo a prime.

  Define the Euler totient function $\phi$.

  Let $p$ be a prime and let $d$ be a positive divisor of $p-1$. Show that there are exactly $\phi(d)$ elements of $(\mathbb{Z} / p \mathbb{Z})^{\times}$with order $d .$

  Deduce that $(\mathbb{Z} / p \mathbb{Z})^{\times}$is cyclic.

  Let $g$ be a primitive root modulo $p^{2}$. Show that $g$ must be a primitive root modulo $p$.

  Let $g$ be a primitive root modulo $p$. Must it be a primitive root modulo $p^{2}$ ? Give a proof or a counterexample.

  comment

• Paper 4, Section I, F

  Number Theory | Part II, 2014

  State the Chinese Remainder Theorem.

  Find all solutions to the simultaneous congruences

  $$\begin{aligned} &x \equiv 2 \quad(\bmod 3) \\ &x \equiv 3(\bmod 5) \\ &x \equiv 5(\bmod 7) \end{aligned}$$

  A positive integer is said to be square-free if it is the product of distinct primes. Show that there are 100 consecutive numbers that are not square-free.

  comment

• Paper 4, Section II, F

  Number Theory | Part II, 2014

  Define the Legendre and Jacobi symbols.

  State the law of quadratic reciprocity for the Legendre symbol.

  State the law of quadratic reciprocity for the Jacobi symbol, and deduce it from the corresponding result for the Legendre symbol.

  Let $p$ be a prime with $p \equiv 1(\bmod 4)$. Prove that the sum of the quadratic residues in the set $\{1,2, \ldots, p-1\}$ is equal to the sum of the quadratic non-residues in this set.

  For which primes $p$ is 7 a quadratic residue?

  comment

2013

• Paper 1, Section I, I

  Number Theory | Part II, 2013

  State and prove Gauss's Lemma for the Legendre symbol $\left(\frac{a}{p}\right)$. For which odd primes $p$ is 2 a quadratic residue modulo $p ?$ Justify your answer.

  comment

• Paper 2, Section I, I

  Number Theory | Part II, 2013

  Define Euler's totient function $\phi(n)$, and show that $\sum_{d \mid n} \phi(d)=n$. Hence or otherwise prove that for any prime $p$ the multiplicative group $(\mathbb{Z} / p \mathbb{Z})^{\times}$is cyclic.

  comment

• Paper 3, Section I, I

  Number Theory | Part II, 2013

  State the Chinese Remainder Theorem.

  A composite number $n$ is defined to be a Carmichael number if $b^{n-1} \equiv 1 \bmod n$ whenever $(b, n)=1$. Show that a composite $n$ is Carmichael if and only if $n$ is square-free and $(p-1)$ divides $(n-1)$ for all prime factors $p$ of $n$. [You may assume that, for $p$ an odd prime and $\alpha \geqslant 1$ an integer, $\left(\mathbb{Z} / p^{\alpha} \mathbb{Z}\right)^{\times}$is a cyclic group.]

  Show that if $n=(6 t+1)(12 t+1)(18 t+1)$ with all three factors prime, then $n$ is Carmichael.

  comment

• Paper 3, Section II, I

  Number Theory | Part II, 2013

  Define equivalence of binary quadratic forms and show that equivalent forms have the same discriminant.

  Show that an integer $n$ is properly represented by a binary quadratic form of discriminant $d$ if and only if $x^{2} \equiv d \bmod 4 n$ is soluble in integers. Which primes are represented by a form of discriminant $-20$ ?

  What does it mean for a positive definite form to be reduced? Find all reduced forms of discriminant $-20$. For each member of your list find the primes less than 100 represented by the form.

  comment

• Paper 4, Section I, I

  Number Theory | Part II, 2013

  Let $s=\sigma+i t$ with $\sigma, t \in \mathbb{R}$. Define the Riemann zeta function $\zeta(s)$ for $\sigma>1$. Show that for $\sigma>1$,

  $$\zeta(s)=\prod_{p}\left(1-p^{-s}\right)^{-1}$$

  where the product is taken over all primes. Deduce that there are infinitely many primes.

  comment

• Paper 4, Section II, I

  Number Theory | Part II, 2013

  (i) What is meant by the continued fraction expansion of a real number $\theta$ ? Suppose that $\theta$ has continued fraction $\left[a_{0}, a_{1}, a_{2}, \ldots\right]$. Define the convergents $p_{n} / q_{n}$ to $\theta$ and give the recurrence relations satisfied by the $p_{n}$ and $q_{n}$. Show that the convergents $p_{n} / q_{n}$ do indeed converge to $\theta$.

  [You need not justify the basic order properties of finite continued fractions.]

  (ii) Find two solutions in strictly positive integers to each of the equations

  $$x^{2}-10 y^{2}=1 \quad \text { and } \quad x^{2}-11 y^{2}=1$$

  comment

2012

• Paper 1, Section I, I

  Number Theory | Part II, 2012

  Show that the continued fraction for $\sqrt{13}$ is $[3 ; \overline{1,1,1,1,6}]$.

  Hence, or otherwise, find a solution to the equation $x^{2}-13 y^{2}=1$ in positive integers $x$ and $y$. Write down an expression for another solution.

  comment

• Paper 2, Section I, I

  Number Theory | Part II, 2012

  Define the Legendre symbol and the Jacobi symbol.

  State the law of quadratic reciprocity for the Jacobi symbol.

  Compute the value of the Jacobi symbol $\left(\frac{247}{321}\right)$, stating clearly any results you use.

  comment

• Paper 3 , Section II, I

  Number Theory | Part II, 2012

  Let $p$ be an odd prime. Prove that the multiplicative groups $\left(\mathbb{Z} / p^{n} \mathbb{Z}\right)^{\times}$are cyclic for $n \geqslant 2$. [You may assume that the multiplicative group $(\mathbb{Z} / p \mathbb{Z})^{\times}$is cyclic.]

  Find an integer which generates $\left(\mathbb{Z} / 7^{n} \mathbb{Z}\right)^{\times}$for all $n \geqslant 1$, justifying your answer.

  comment

• Paper 3, Section I, I

  Number Theory | Part II, 2012

  Define the discriminant of the binary quadratic form $f(x, y)=a x^{2}+b x y+c y^{2}$.

  Assuming that this form is positive definite, define what it means for $f$ to be reduced.

  Show that there are precisely two reduced positive definite binary quadratic forms of discriminant $-35$.

  comment

• Paper 4, Section I, I

  Number Theory | Part II, 2012

  Define what it means for the composite natural number $N$ to be a pseudoprime to the base $b$.

  Find the number of bases (less than 21) to which 21 is a pseudoprime. [You may, if you wish, assume the Chinese Remainder Theorem.]

  comment

• Paper 4, Section II, I

  Number Theory | Part II, 2012

  Let $f: \mathbb{N} \rightarrow \mathbb{R}$ be a function, where $\mathbb{N}$ denotes the (positive) natural numbers.

  Define what it means for $f$ to be a multiplicative function.

  Prove that if $f$ is a multiplicative function, then the function $g: \mathbb{N} \rightarrow \mathbb{R}$ defined by

  $$g(n)=\sum_{d \mid n} f(d)$$

  is also multiplicative.

  Define the Möbius function $\mu$. Is $\mu$ multiplicative? Briefly justify your answer.

  Compute

  $$\sum_{d \mid n} \mu(d)$$

  for all positive integers $n$.

  Define the Riemann zeta function $\zeta$ for complex numbers $s$ with $\Re(s)>1$.

  Prove that if $s$ is a complex number with $\Re(s)>1$, then

  $$\frac{1}{\zeta(s)}=\sum_{n=1}^{\infty} \frac{\mu(n)}{n^{s}}$$

  comment

2011

• Paper 1, Section I, I

  Number Theory | Part II, 2011

  Prove that, under the action of $\mathrm{SL}_{2}(\mathbb{Z})$, every positive definite binary quadratic form of discriminant $-163$, with integer coefficients, is equivalent to

  $$x^{2}+x y+41 y^{2} .$$

  comment

• Paper 2, Section I, I

  Number Theory | Part II, 2011

  (i) Find a primitive root modulo $17 .$

  (ii) Let $p$ be a prime of the form $2^{m}+1$ for some integer $m \geqslant 1$. Prove that every quadratic non-residue modulo $p$ is a primitive root modulo $p$.

  comment

• Paper 3, Section I, I

  Number Theory | Part II, 2011

  (i) State Lagrange's Theorem, and prove that, if $p$ is an odd prime,

  $$(p-1) ! \equiv-1 \quad \bmod p$$

  (ii) Still assuming $p$ is an odd prime, prove that

  $$3^{2} \cdot 5^{2} \cdots(p-2)^{2} \equiv(-1)^{\frac{p+1}{2}} \bmod p$$

  comment

• Paper 3, Section II, I

  Number Theory | Part II, 2011

  Let $\zeta(s)$ be the Riemann zeta function, and put $s=\sigma+i t$ with $\sigma, t \in \mathbb{R}$.

  (i) If $\sigma>1$, prove that

  $$\zeta(s)=\prod_{p}\left(1-p^{-s}\right)^{-1}$$

  where the product is taken over all primes $p$.

  (ii) Assuming that, for $\sigma>1$, we have

  $$\zeta(s)=\sum_{n=1}^{\infty} n\left(n^{-s}-(n+1)^{-s}\right)$$

  prove that $\zeta(s)-\frac{1}{s-1}$ has an analytic continuation to the half plane $\sigma>0$.

  comment

• Paper 4, Section $I$, I

  Number Theory | Part II, 2011

  (i) Prove that there are infinitely many primes.

  (ii) Prove that arbitrarily large gaps can occur between consecutive primes.

  comment

• Paper 4, Section II, I

  Number Theory | Part II, 2011

  (i) Prove the law of reciprocity for the Jacobi symbol. You may assume the law of reciprocity for the Legendre symbol.

  (ii) Let $n$ be an odd positive integer which is not a square. Prove that there exists an odd prime $p$ with $\left(\frac{n}{p}\right)=-1$.

  comment

2010

• Paper 1, Section I, G

  Number Theory | Part II, 2010

  (i) Let $N$ be an integer $\geqslant 2$. Define the addition and multiplication on the set of congruence classes modulo $N$.

  (ii) Let an integer $M \geqslant 1$ have expansion to the base 10 given by $a_{s} \ldots a_{0}$. Prove that 11 divides $M$ if and only if $\sum_{i=0}^{s}(-1)^{i} a_{i}$ is divisible by 11 .

  comment

• Paper 2, Section I, G

  Number Theory | Part II, 2010

  Let $p$ be an odd prime number. If $n$ is an integer prime to $p$, define $\left(\frac{n}{p}\right)$.

  (i) Prove that $\chi(n)=\left(\frac{n}{p}\right)$ defines a homomorphism from $(\mathbb{Z} / p \mathbb{Z})^{\times}$to the group $\{\pm 1\}$. What is the value of $\chi(-1) ?$

  (ii) If $p \equiv 1 \bmod 4$, prove that $\sum_{n=1}^{p-1} \chi(n) n=0$.

  comment

• Paper 3, Section I, G

  Number Theory | Part II, 2010

  (i) Let $M$ and $N$ be positive integers, such that $N$ is not a perfect square. If $M<\sqrt{N}$, show that every solution of the equation

  $$x^{2}-N y^{2}=M$$

  in positive integers $x, y$ comes from some convergent of the continued fraction of $\sqrt{N}$.

  (ii) Find a solution in positive integers $x, y$ of

  $$x^{2}-29 y^{2}=5$$

  comment

• Paper 3, Section II, G

  Number Theory | Part II, 2010

  State precisely the Miller-Rabin primality test.

  (i) Let $p$ be a prime $\geqslant 5$, and define

  $$N=\frac{4^{p}-1}{3}$$

  Prove that $N$ is a composite odd integer, and that $N$ is a pseudo-prime to the base 2 .

  (ii) Let $M$ be an odd integer greater than 1 such that $M$ is a pseudo-prime to the base 2 . Prove that $2^{M}-1$ is always a strong pseudo-prime to the base 2 .

  comment

• Paper 4, Section I, G

  Number Theory | Part II, 2010

  Let $p$ be a prime number, and put

  $$a_{k}=k p, \quad N_{k}=a_{k}^{p}-1 \quad(k=1,2, \ldots)$$

  Prove that $a_{k}$ has exact order $p$ modulo $N_{k}$ for all $k \geqslant 1$, and deduce that $N_{k}$ must be divisible by a prime $q$ with $q \equiv 1 \quad(\bmod p)$. By making a suitable choice of $k$, prove that there are infinitely many primes $q$ with $q \equiv 1 \quad(\bmod p)$.

  comment

• Paper 4, Section II, G

  Number Theory | Part II, 2010

  Let $\mathcal{S}$ be the set of all positive definite binary quadratic forms with integer coefficients. Define the action of the group $S L_{2}(\mathbb{Z})$ on $\mathcal{S}$, and prove that equivalent forms under this action have the same discriminant.

  Find necessary and sufficient conditions for an odd positive integer $n$, prime to 35 , to be properly represented by at least one of the two forms

  $$x^{2}+x y+9 y^{2}, \quad 3 x^{2}+x y+3 y^{2}$$

  comment

2009

• Paper 1, Section I, G

  Number Theory | Part II, 2009

  State the Chinese Remainder Theorem.

  Determine all integers $x$ satisfying the congruences $x \equiv 2 \bmod 3, x \equiv 2 \bmod 5$, $x \equiv 6 \bmod 7 .$

  comment

• Paper 2, Section $\mathbf{I}$, $1 \mathrm{G}$

  Number Theory | Part II, 2009

  State the law of quadratic reciprocity for the Jacobi symbol $\left(\frac{m}{n}\right)$, where $m, n$ are odd positive integers, and prove this law using the reciprocity law for the Legendre symbol.

  Compute the Jacobi symbol $\left(\frac{261}{317}\right)$.

  comment

• Paper 3, Section I, G

  Number Theory | Part II, 2009

  For any integer $x \geqslant 2$, define $\theta(x)=\sum_{p \leqslant x} \log p$, where the sum is taken over all primes $p \leqslant x$. Put $\theta(1)=0$. By studying the integer

  $$\left(\begin{array}{c} 2 n \\ n \end{array}\right)$$

  where $n \geqslant 1$ is an integer, prove that

  $$\theta(2 n)-\theta(n)<2 n \log 2$$

  Deduce that

  $$\theta(x)<(4 \log 2) x$$

  for all $x \geqslant 1$.

  comment

• Paper 3, Section II, G

  Number Theory | Part II, 2009

  Let $p$ be an odd prime. Prove that there is an equal number of quadratic residues and non-residues in the set $\{1, \ldots, p-1\}$.

  If $n$ is an integer prime to $p$, let $m_{n}$ be an integer such that $n m_{n} \equiv 1 \bmod p$. Prove that

  $$n(n+1) \equiv n^{2}\left(1+m_{n}\right) \bmod p$$

  and deduce that

  $$\sum_{n=1}^{p-1}\left(\frac{n(n+1)}{p}\right)=-1$$

  comment

• Paper 4, Section I, G

  Number Theory | Part II, 2009

  Let $W$ denote the set of all positive definite binary quadratic forms, with integer coefficients, and having discriminant $-67$. Let $S L_{2}(\mathbb{Z})$ be the group of all $2 \times 2$ matrices with integer entries and determinant 1. Prove that $W$ is infinite, but that all elements of $W$ are equivalent under the action of the group $S L_{2}(\mathbb{Z})$

  comment

• Paper 4, Section II, G

  Number Theory | Part II, 2009

  Let $s=\sigma+i t$, where $\sigma$ and $t$ are real, and for $\sigma>1$ let

  $$\zeta(s)=\sum_{n=1}^{\infty} \frac{1}{n^{s}}$$

  Prove that $\zeta(s)$ has no zeros in the half plane $\sigma>1$. Show also that for $\sigma>1$,

  $$\frac{1}{\zeta(s)}=\sum_{n=1}^{\infty} \frac{\mu(n)}{n^{s}}$$

  where $\mu$ denotes the Möbius function. Assuming that $\zeta(s)-\frac{1}{s-1}$ has an analytic continuation to the half plane $\sigma>0$, show that if $s=1+i t$, with $t \neq 0$, and $\zeta(s)=0$ then $s$ is at most a simple zero of $\zeta$.

  comment

2008

• 1.I.1H

  Number Theory | Part II, 2008

  Define the continued fraction of a real number $\alpha$.

  Compute the continued fraction of $\sqrt{19}$.

  comment

• 2.I.1H

  Number Theory | Part II, 2008

  What does it mean for a positive definite quadratic form with integer coefficients to be reduced?

  Show that there are precisely three reduced forms of this type with discriminant equal to $-23$.

  Which odd primes are properly represented by some positive definite binary quadratic form (with integer coefficients) of discriminant $-23$ ?

  comment

• 3.I.1H

  Number Theory | Part II, 2008

  Prove that, for all $x \geqslant 2$, we have

  $$\sum_{p \leqslant x} \frac{1}{p}>\log \log x-\frac{1}{2}$$

  [You may assume that, for $0<u<1$,

  $$-\log (1-u)-u<\frac{u^{2}}{2(1-u)} .$$

  comment

• 3.II.11H

  Number Theory | Part II, 2008

  State the reciprocity law for the Jacobi symbol.

  Let $a$ be an odd integer $>1$, which is not a square. Prove that there exists a positive integer $n$ such that $n \equiv 1 \bmod 4$ and

  $$\left(\frac{n}{a}\right)=-1$$

  Prove further that there exist infinitely many prime numbers $p$ such that

  $$\left(\frac{a}{p}\right)=-1$$

  comment

• 4.I.1H

  Number Theory | Part II, 2008

  Let $p$ be an odd prime number. Assuming that the multiplicative group of $\mathbb{Z} / p \mathbb{Z}$ is cyclic, prove that the multiplicative group of units of $\mathbb{Z} / p^{n} \mathbb{Z}$ is cyclic for all $n \geqslant 1$.

  Find an integer $a$ such that its residue class in $\mathbb{Z} / 11^{n} \mathbb{Z}$ generates the multiplicative group of units for all $n \geqslant 1$.

  comment

• 4.II.11H

  Number Theory | Part II, 2008

  Let $N>1$ be an integer, which is not a square, and let $p_{k} / q_{k}(k=1,2, \ldots)$ be the convergents to $\sqrt{N}$. Prove that

  $$\left|p_{k}^{2}-q_{k}^{2} N\right|<2 \sqrt{N} \quad(k=1,2, \ldots)$$

  Explain briefly how this result can be used to generate a factor base $B$, and a set of $B$-numbers which may lead to a factorization of $N$.

  comment

2007

• $3 . \mathrm{I} . 1 \mathrm{~F} \quad$

  Number Theory | Part II, 2007

  Determine the continued fraction of $\sqrt{7}$. Deduce two pairs of solutions in positive integers $x, y$ of the equation

  $$x^{2}-7 y^{2}=1$$

  comment

• 1.I.1F

  Number Theory | Part II, 2007

  State the prime number theorem, and Bertrand's postulate.

  Let $S$ be a finite set of prime numbers, and write $f_{s}(x)$ for the number of positive integers no larger than $x$, all of whose prime factors belong to $S$. Prove that

  $$f_{s}(x) \leqslant 2^{\#(S)} \sqrt{x}$$

  where $\#(S)$ denotes the number of elements in $S$. Deduce that, if $x$ is a strictly positive integer, we have

  $$\pi(x) \geqslant \frac{\log x}{2 \log 2} .$$

  comment

• 2.I.1F

  Number Theory | Part II, 2007

  Let $p$ be an odd prime number. Prove that 2 is a quadratic residue modulo $p$ when $p \equiv 7 \quad(\bmod 8)$. Deduce that, if $q$ is a prime number strictly greater than 3 with $q \equiv 3$ $(\bmod 4)$ such that $2 q+1$ is also a prime number, then $2^{q}-1$ is necessarily composite. Why does the argument break down for $q=3$ ?

  comment

• 3.II.11F

  Number Theory | Part II, 2007

  State the Chinese remainder theorem. Let $n$ be an odd positive integer. If $n$ is divisible by the square of a prime number $p$, prove that there exists an integer $z$ such that $z^{p} \equiv 1(\bmod n)$ but $z \not \equiv 1(\bmod n)$.

  Define the Jacobi symbol

  $$\left(\frac{a}{n}\right)$$

  for any non-zero integer $a$. Give a numerical example to show that

  $$\left(\frac{a}{n}\right)=+1$$

  does not imply in general that $a$ is a square modulo $n$. State and prove the law of quadratic reciprocity for the Jacobi symbol.

  [You may assume the law of quadratic reciprocity for the Legendre symbol.]

  Assume now that $n$ is divisible by the square of a prime number. Prove that there exists an integer $a$ with $(a, n)=1$ such that the congruence

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

  does not hold. Show further that this congruence fails to hold for at least half of all relatively prime residue classes modulo $n$.

  comment

• 4.I.1F

  Number Theory | Part II, 2007

  Prove Legendre's formula relating $\pi(x)$ and $\pi(\sqrt{x})$ for any positive real number $x$. Use this formula to compute $\pi(48)$.

  comment

• 4.II.11F

  Number Theory | Part II, 2007

  Let $p$ be a prime number, and let $f(x)$ be a polynomial with integer coefficients, whose leading coefficient is not divisible by $p$. Prove that the congruence

  $$f(x) \equiv 0 \quad(\bmod p)$$

  has at most $d$ solutions, where $d$ is the degree of $f(x)$.

  Deduce that all coefficients of the polynomial

  $$x^{p-1}-1-((x-1)(x-2) \cdots(x-p+1))$$

  must be divisible by $p$, and prove that:

  (i) $(p-1) !+1 \equiv 0 \quad(\bmod p)$;

  (ii) if $p$ is odd, the numerator of the fraction

  $$u_{p}=1+\frac{1}{2}+\cdots+\frac{1}{p-1}$$

  is divisible by $p$.

  Assume now that $p \geqslant 5$. Show by example that (i) cannot be strengthened to $(p-1) !+1 \equiv 0 \quad\left(\bmod p^{2}\right)$.

  comment

2006

• 1.I.1H

  Number Theory | Part II, 2006

  State the theorem of the primitive root for an odd prime power modulus.

  Prove that 3 is a primitive root modulo $7^{n}$ for all integers $n \geqslant 1$. Is 2 a primitive root modulo $7^{n}$ for all integers $n \geqslant 1$ ?

  Prove that there is no primitive root modulo 8 .

  comment

• 2.I.1H

  Number Theory | Part II, 2006

  Prove that all binary quadratic forms of discriminant $-7$ are equivalent to $x^{2}+x y+2 y^{2} .$

  Determine which prime numbers $p$ are represented by $x^{2}+x y+2 y^{2}$.

  comment

• 3.I.1H

  Number Theory | Part II, 2006

  Let $N=p_{1} p_{2} \ldots p_{r}$ be a product of distinct primes, and let $\lambda(N)$ be the least common multiple of $p_{1}-1, p_{2}-1, \ldots, p_{r}-1$. Prove that

  $$a^{\lambda(N)} \equiv 1 \bmod N \quad \text { when } \quad(a, N)=1 .$$

  Now take $N=7 \times 13 \times 19$, and prove that

  $$a^{N-1} \equiv 1 \bmod N \quad \text { when } \quad(a, N)=1 .$$

  comment

• 3.II.11H

  Number Theory | Part II, 2006

  State the prime number theorem, and Dirichlet's theorem on primes in arithmetic progression.

  If $p$ is an odd prime number, prove that $-1$ is a quadratic residue modulo $p$ if and only if $p \equiv 1 \bmod 4$.

  Let $p_{1}, \ldots, p_{m}$ be distinct prime numbers, and define

  $$N_{1}=4 p_{1} \ldots p_{m}-1, \quad N_{2}=4\left(p_{1} \ldots p_{m}\right)^{2}+1$$

  Prove that $N_{1}$ has at least one prime factor which is congruent to $3 \bmod 4$, and that every prime factor of $N_{2}$ must be congruent to $1 \bmod 4$.

  Deduce that there are infinitely many primes which are congruent to $1 \bmod 4$, and infinitely many primes which are congruent to $3 \bmod 4$.

  comment

• 4.I.1H

  Number Theory | Part II, 2006

  Let $x$ be a real number greater than or equal to 2 , and define

  $$P(x)=\prod_{p \leqslant x}\left(1-\frac{1}{p}\right)$$

  where the product is taken over all primes $p$ which are less than or equal to $x$. Prove that $P(x) \rightarrow 0$ as $x \rightarrow \infty$, and deduce that $\sum_{p} \frac{1}{p}$ diverges when the summation is taken over all primes $p$.

  comment

• 4.II.11H

  Number Theory | Part II, 2006

  Define the notion of a Fermat, Euler, and strong pseudo-prime to the base $b$, where $b$ is an integer greater than $1 .$

  Let $N$ be an odd integer greater than 1. Prove that:

  (a) If $N$ is a prime number, then $N$ is a strong pseudo-prime for every base $b$ with $(b, N)=1$.

  (b) If there exists a base $b_{1}$ with $1<b_{1}<N$ and $\left(b_{1}, N\right)=1$ for which $N$ is not a pseudo-prime, then in fact $N$ is not a pseudo-prime for at least half of all bases $b$ with $1<b<N$ and $(b, N)=1$.

  Prove that 341 is a Fermat pseudo-prime, but not an Euler pseudo-prime, to the base $2 .$

  comment

2005

• 1.I.1H

  Number Theory | Part II, 2005

  Define the Legendre symbol $\left(\frac{a}{p}\right)$. Prove that, if $p$ is an odd prime, then

  $$\left(\frac{2}{p}\right)=(-1)^{\frac{p^{2}-1}{8}} .$$

  Use the law of quadratic reciprocity to calculate $\left(\frac{91}{167}\right)$.

  [You may use the Gauss Lemma without proof.]

  comment

• 2.I.1H

  Number Theory | Part II, 2005

  Recall that, if $p$ is an odd prime, a primitive root modulo $p$ is a generator of the cyclic (multiplicative) group $(\mathbb{Z} / p \mathbb{Z})^{\times}$. Let $p$ be an odd prime of the form $2^{2^{n}}+1$; show that $a$ is a primitive root $\bmod p$ if and only if $a$ is not a quadratic residue mod $p$. Use this result to prove that 7 is a primitive root modulo every such prime.

  comment

• 3.I.1H

  Number Theory | Part II, 2005

  Let $\pi(x)$ be the number of primes $p \leqslant x$. State the Legendre formula, and prove that

  $$\lim _{x \rightarrow \infty} \frac{\pi(x)}{x}=0 .$$

  [You may use the formula

  $$\prod_{p \leqslant x}(1-1 / p)^{-1} \geqslant \log x$$

  without proof.]

  comment

• 3.II.11H

  Number Theory | Part II, 2005

  Show that there are exactly two reduced positive definite integer binary quadratic forms with discriminant $-20$; write these forms down.

  State a criterion for an odd integer $n$ to be properly represented by a positive definite integer binary quadratic form of given discriminant $d$.

  Describe, in terms of congruences modulo 20, which primes other than 2,5 are properly represented by the form $x^{2}+5 y^{2}$, and justify your answer.

  comment

• 4.I.1H

  Number Theory | Part II, 2005

  If $n$ is an odd integer and $b$ is an integer prime with $n$, state what it means for $n$ to be a pseudoprime to the base $b$. What is a Carmichael number? State a criterion for $n$ to be a Carmichael number and use the criterion to show that:

  (i) Every Carmichael number is the product of at least three distinct primes.

  (ii) 561 is a Carmichael number.

  comment

• 4.II.11H

  Number Theory | Part II, 2005

  (a) Let $N$ be a non-square integer. Describe the integer solutions of the Pell equation $x^{2}-N y^{2}=1$ in terms of the convergents to $\sqrt{N}$. Show that the set of integer solutions forms an abelian group. Denote the addition law in this group by $\circ$; given solutions $\left(x_{0}, y_{0}\right)$ and $\left(x_{1}, y_{1}\right)$, write down an explicit formula for $\left(x_{0}, y_{0}\right) \circ\left(x_{1}, y_{1}\right)$. If $(x, y)$ is a solution, write down an explicit formula for $(x, y) \circ(x, y) \circ(x, y)$ in the group law.

  (b) Find the continued fraction expansion of $\sqrt{11}$. Find the smallest solution in integers $x, y>0$ of the Pell equation $x^{2}-11 y^{2}=1$. Use the formula in Part (a) to compute $(x, y) \circ(x, y) \circ(x, y)$.

  comment

2004

• A1.9

  Number Theory | Part II, 2004

  (i) State the law of quadratic reciprocity. For $p \neq 5$ an odd prime, evaluate the Legendre symbol

  $$\left(\frac{5}{p}\right)$$

  (ii) (a) Let $p_{1}, \ldots, p_{m}$ and $q_{1}, \ldots, q_{n}$ be distinct odd primes. Show that there exists an integer $x$ that is a quadratic residue modulo each of $p_{1}, \ldots, p_{m}$ and a quadratic non-residue modulo each of $q_{1}, \ldots, q_{n}$.

  (b) Let $p$ be an odd prime. Show that

  $$\sum_{a=1}^{p-1}\left(\frac{a}{p}\right)=0$$

  (c) Let $p$ be an odd prime. Using (b) or otherwise, evaluate

  $$\sum_{a=1}^{p-2}\left(\frac{a}{p}\right)\left(\frac{a+1}{p}\right)$$

  $\left[\right.$ Hint for $(c)$ : Use the equality $\left(\frac{x^{2} y}{p}\right)=\left(\frac{y}{p}\right)$, valid when $p$ does not divide $\left.x .\right]$

  comment

• A3.9

  Number Theory | Part II, 2004

  (i) Find a solution in integers of the Pell equation $x^{2}-17 y^{2}=1$.

  (ii) Define the continued fraction expansion of a real number $\theta>1$ and show that it converges to $\theta$.

  Show that if $N>0$ is a nonsquare integer and $x$ and $y$ are integer solutions of $x^{2}-N y^{2}=1$, then $x / y$ is a convergent of $\sqrt{N}$.

  comment

• A4.10

  Number Theory | Part II, 2004

  Write an essay on pseudoprimes and their role in primality testing. You should discuss pseudoprimes, Carmichael numbers, and Euler and strong pseudoprimes. Where appropriate, your essay should include small examples to illustrate your statements.

  comment

2003

• A1.9

  Number Theory | Part II, 2003

  (i) Let $p$ be an odd prime and $k$ a strictly positive integer. Prove that the multiplicative group of relatively prime residue classes modulo $p^{k}$ is cyclic.

  [You may assume that the result is true for $k=1$.]

  (ii) Let $n=p_{1} p_{2} \ldots p_{r}$, where $r \geqslant 2$ and $p_{1}, p_{2}, \ldots, p_{r}$ are distinct odd primes. Let $B$ denote the set of all integers which are relatively prime to $n$. We recall that $n$ is said to be an Euler pseudo-prime to the base $b \in B$ if

  $$b^{(n-1) / 2} \equiv\left(\frac{b}{n}\right) \bmod n .$$

  If $n$ is an Euler pseudo-prime to the base $b_{1} \in B$, but is not an Euler pseudo-prime to the base $b_{2} \in B$, prove that $n$ is not an Euler pseudo-prime to the base $b_{1} b_{2}$. Let $p$ denote any of the primes $p_{1}, p_{2}, \ldots, p_{r}$. Prove that there exists a $b \in B$ such that

  $$\left(\frac{b}{p}\right)=-1 \quad \text { and } \quad b \equiv 1 \bmod n / p$$

  and deduce that $n$ is not an Euler pseudo-prime to this base $b$. Hence prove that $n$ is not an Euler pseudo-prime to the base $b$ for at least half of all the relatively prime residue classes $b \bmod n$.

  comment

• A3.9

  Number Theory | Part II, 2003

  (i) Let $x \geqslant 2$ be a real number and let $P(x)=\prod_{p \leqslant x}\left(1-\frac{1}{p}\right)^{-1}$, where the product is taken over all primes $p \leqslant x$. Prove that $P(x)>\log x$.

  (ii) Define the continued fraction of any positive irrational real number $x$. Illustrate your definition by computing the continued fraction of $1+\sqrt{3}$.

  Suppose that $a, b, c$ are positive integers with $b=a c$ and that $x$ has the periodic continued fraction $[b, a, b, a, \ldots]$. Prove that $x=\frac{1}{2}\left(b+\sqrt{b^{2}+4 c}\right)$.

  comment

• A4.10

  Number Theory | Part II, 2003

  Write an essay describing the factor base method for factorising a large odd positive integer $n$. Your essay should include a detailed explanation of how the continued fraction of $\sqrt{n}$ can be used to find a suitable factor base.

  comment

2002

• A1.9

  Number Theory | Part II, 2002

  (i) Let $p$ be a prime number. Prove that the multiplicative group of the field with $p$ elements is cyclic.

  (ii) Let $p$ be an odd prime, and let $k \geqslant 1$ be an integer. Prove that we have $x^{2} \equiv 1 \bmod p^{k}$ if and only if either $x \equiv 1 \bmod p^{k}$ or $x \equiv-1 \bmod p^{k}$. Is this statement true when $p=2$ ?

  Let $m$ be an odd positive integer, and let $r$ be the number of distinct prime factors of $m$. Prove that there are precisely $2^{r}$ different integers $x$ satisfying $x^{2} \equiv 1 \bmod m$ and $0<x<m$.

  comment

• A3.9

  Number Theory | Part II, 2002

  (i) Let $\pi(x)$ denote the number of primes $\leqslant x$, where $x$ is a positive real number. State and prove Legendre's formula relating $\pi(x)$ to $\pi(\sqrt{x})$. Use this formula to compute $\pi(100)-\pi(10) .$

  (ii) Let $\zeta(s)=\sum_{n=1}^{\infty} n^{-s}$, where $s$ is a real number greater than 1 . Prove the following two assertions rigorously, assuming always that $s>1$. (a) $\zeta(s)=\prod_{p}\left(1-p^{-s}\right)^{-1}$, where the product is taken over all primes $p$; (b) $\zeta(s)=\frac{1}{1-2^{1-s}} \sum_{n=1}^{\infty} \frac{(-1)^{n-1}}{n^{s}}$.

  Explain why (b) enables us to define $\zeta(s)$ for $0<s<1$. Deduce from (b) that $\lim _{s \rightarrow 1}(s-1) \zeta(s)=1$.

  comment

• A4.10

  Number Theory | Part II, 2002

  Write an essay on quadratic reciprocity. Your essay should include (i) a proof of the law of quadratic reciprocity for the Legendre symbol, (ii) a proof of the law of quadratic reciprocity for the Jacobi symbol, and (iii) a comment on why this latter law is useful in primality testing.

  comment

2001

• A1.9

  Number Theory | Part II, 2001

  (i) Describe Euclid's algorithm.

  Find, in the RSA algorithm, the deciphering key corresponding to the enciphering key 7,527 .

  (ii) Explain what is meant by a primitive root modulo an odd prime $p$.

  Show that, if $g$ is a primitive root modulo $p$, then all primitive roots modulo $p$ are given by $g^{m}$, where $1 \leqslant m<p$ and $(m, p-1)=1$.

  Verify, by Euler's criterion, that 3 is a primitive root modulo 17 . Hence find all primitive roots modulo 17 .

  comment

• A3.9

  Number Theory | Part II, 2001

  (i) State the law of quadratic reciprocity.

  Prove that 5 is a quadratic residue modulo primes $p \equiv \pm 1 \quad(\bmod 10)$ and a quadratic non-residue modulo primes $p \equiv \pm 3 \quad(\bmod 10)$.

  Determine whether 5 is a quadratic residue or non-residue modulo 119 and modulo $539 .$

  (ii) Explain what is meant by the continued fraction of a real number $\theta$. Define the convergents to $\theta$ and write down the recurrence relations satisfied by their numerators and denominators.

  Use the continued fraction method to find two solutions in positive integers $x, y$ of the equation $x^{2}-15 y^{2}=1$.

  comment

• A4.10

  Number Theory | Part II, 2001

  Attempt one of the following:

  (i) Discuss pseudoprimes and primality testing. Find all bases for which 57 is a Fermat pseudoprime. Determine whether 57 is also an Euler pseudoprime for these bases.

  (ii) Write a brief account of various methods for factoring large numbers. Use Fermat factorization to find the factors of 10033. Would Pollard's $p-1$ method also be practical in this instance?

  (iii) Show that $\sum 1 / p_{n}$ is divergent, where $p_{n}$ denotes the $n$-th prime.

  Write a brief account of basic properties of the Riemann zeta-function.

  State the prime number theorem. Show that it implies that for all sufficiently large positive integers $n$ there is a prime $p$ satisfying $n<p \leqslant 2 n$.

  comment