Past exam of the mathematics course of the University of Oxford / 2023 / Prelims / Mathematics I / 6 (Cosets and infinitely many primes)

The set $S_n$ is nonempty because $n\in S_n$. By the well-ordering principle for the natural numbers, it has a least element $p$. In particular $p>1$ and $p$ divides $n$.

If $p$ were not a prime number, it would have a positive integer divisor $d$ with $1<d<p$. Since $d$ divides $p$ and $p$ divides $n$, divisibility is transitive and $d$ divides $n$. This would put $d$ in $S_n$, contradicting the minimality of $p$. Hence $\boxed{p\text{ is prime}}$.

Neither $1$ nor $-1$ is divisible by a prime number, so both lie outside $U$. On the other hand, $0\in 2\mathbb{Z}\subseteq U$. If an integer $z$ has $|z|>1$, part (a)(i) supplies a prime number $p$ dividing the positive integer $|z|$; the same $p$ divides $z$, so $z\in p\mathbb{Z}\subseteq U$. These cases exhaust $\mathbb{Z}$, proving

For every $g\in G$, left multiplication gives a bijectionwhose inverse is $x\mapsto g^{-1}x$. Hence every left coset has the same cardinality as $H$. If $H$ is an infinite set, every left coset is infinite; if $H$ is a finite set, every left coset is finite. These are the only possibilities.

Suppose $H$ were finite, say $|H|=r$. There are at most $n$ left cosets, each with $r$ elements by part (i), and they partition $G$. Hence $G$ would be a finite set with at most $nr$ elements. This contradicts the assumption that $G$ is an infinite group. Therefore $\boxed{H\text{ is infinite}}$.

Every left coset $kH$ with $k\in K$ is also a left coset of $H$ in $G$. Moreover equality of two such cosets means the same thing in $K$ and in $G$:Thus the map from the set of left cosets of $H$ in $K$ to the set of left cosets of $H$ in $G$, taking $kH$ to itself, is injective. Consequently the index of a subgroup satisfiesThese are sets of cosets; no normal subgroup assumption is needed.

Define a map between sets of left cosets byIt is well defined: replacing $g$ by $gu$ for $u\in H\cap K$ changes neither component. It is injective becauseThe Cartesian product on the right has at most $nm$ elements. ThereforeThis proves the basic bound for a finite intersection of finite-index subgroups.

Put $L={\bigcap }_{i=1}^k{H}_i$. Repeated application of part (iv), or mathematical induction on $k$, givesPart (ii) therefore implies that $L$ is an infinite set. If $G\setminus U$ is nonempty, choose $g\notin U$. We claim its left coset $gL$ is wholly outside $U$. If $g\ell \in H_i$ for some $\ell \in L$, then $\ell \in H_i$ and closure under products and inverses would give $g=(g\ell ){\ell }^{-1}\in H_i$, a contradiction.

Thus $gL\subseteq G\setminus U$. Part (i) makes $gL$ infinite, so the complement is infinite. If there is no such $g$, the complement is empty. This proves the complement of a finite union of finite-index subgroups property:

Suppose there were only finitely many prime numbers, say $p_1,\dots ,p_k$. Work in the infinite group $(\mathbb{Z},+)$ and set $H_i=p_i\mathbb{Z}$. The left cosets are the $p_i$ residue classes modulo $p_i$, so each $H_i$ is a finite-index subgroup, with $|\mathbb{Z}/H_i|=p_i$.

By part (b)(v), $\mathbb{Z}\setminus {\bigcup }_i{p}_i\mathbb{Z}$ is empty or infinite. But part (a)(ii) identifies it as the nonempty two-element set $\{-1,1\}$. This contradiction proves Euclid's theorem: