Past exam of the mathematics course of the University of Cambridge / 2015 / ia / Paper 4 / 5E (Numbers and Sets)

For an equivalence relation $\sim$ on $X$, the equivalence class of $x\in X$ is $[x]=\{y\in X:y\sim x\}$. A set partition is a family of nonempty, pairwise disjoint subsets whose union is $X$.

Reflexivity ensures $x\in [x]$, so every equivalence class is nonempty and every element belongs to one. If $[x]\cap [y]$ contains $z$, then $z\sim x$ and $z\sim y$; symmetry and transitivity give $x\sim y$. If $w\in [x]$, transitivity gives $w\sim y$, so $w\in [y]$; interchanging $x,y$ gives the reverse inclusion. Thus intersecting equivalence classes are equal.

Taking the collection of distinct equivalence classes therefore produces a set partition of $X$. Every element lies in exactly one class. If $X$ is empty, the empty family is its set partition.

Reflexivity follows by taking the two exponents equal to $1$, and symmetry is built into the two divisibility conditions. For transitivity, suppose $m\mid n^a$, $n\mid m^b$, $n\mid {\ell }^c$ and $\ell \mid n^d$. Then $m\mid {\ell }^{ac}$ and $\ell \mid m^{bd}$, with positive exponents. Thus the relation is an equivalence relation.

Its equivalence classes have a useful description by prime factorization. Let $S(n)$ be the finite set of prime factors of $n$, with $S(1)=\varnothing$. If $m\mid n^a$, every prime factor of $m$ divides $n$; the reverse divisibility gives $S(n)\subseteq S(m)$. Conversely, if $S(m)=S(n)$, write $m={\prod }_{p\in S}{p}^{{\alpha }_p}$ and $n={\prod }_{p\in S}{p}^{{\beta }_p}$, with all exponents positive. Choosing $a\ge {\max }_p\lceil {\alpha }_p/{\beta }_p\rceil$ and $b\ge {\max }_p\lceil {\beta }_p/{\alpha }_p\rceil$ gives the required divisibilities. The empty case is exactly $m=n=1$.

Therefore the prime-support equivalence relation iswhere the radical of an integer is the product of its distinct prime factors. The class with empty support is $\{1\}$. For every nonempty finite support $S$, all positive exponent choices give one class, and varying just one exponent produces infinitely many different integers in it.

There are infinitely many classes because each prime number gives a different singleton support. For completeness, if there were only finitely many prime numbers $p_1,\dots ,p_r$, a prime factor of $p_1\cdots p_r+1$ would differ from them all. There are infinitely many classes; the unique finite class is $\{1\}$.