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

The Euclidean algorithm repeatedly replaces a pair $(a,b)$ by $(b,a-qb)$ without changing its greatest common divisor. Reversing the divisions expresses $\gcd (a,b)$ as an integer linear combination $\alpha a+\beta b$, which is Bézout's identity.

Here $3=3(15)-2(21)$, and thereforeOne solution is $(x,y,z)=(36,-24,-1)$. It is not unique: for every $t\in \mathbb{Z}$, $(x,y,z)=(36+7t,-24-5t,-1)$ is another solution.

Because $\gcd (m,n)=1$, choose $u,v\in \mathbb{Z}$ with $um+vn=1$ by Bézout's identity. Thensatisfies $c\equiv a(\mathrm{mod}m)$ and $c\equiv b(\mathrm{mod}n)$. Any two simultaneous solutions differ by a multiple of both coprime integers and hence by a multiple of $mn$. This proves the two-modulus Chinese remainder theorem.

The three congruences reduce toThe first two give $x\equiv 17(\mathrm{mod}35)$; imposing the last gives

The inclusion-exclusion principle says that the size of a finite union is the alternating sum of the sizes of all nonempty intersections of its constituent sets.

For each prime number $p\mid n$, let $A_p$ consist of the tuples for which $p$ divides every $x_i$. Exactly $(n/p{)}^r$ tuples lie in $A_p$, and for distinct primes $p_1,\dots ,p_j\mid n$, exactly $(n/(p_1\cdots p_j){)}^r$ lie in their intersection. A tuple has greatest common divisor greater than one with $n$ exactly when it belongs to some $A_p$. Inclusion-exclusion therefore gives the Jordan totient function