Paper 4, Section II, 6E6 \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 aa and bb can be written in the form αa+βb\alpha a+\beta b for suitable integers α\alpha and β\beta. Find an integer solution of

15x+21y+35z=115 x+21 y+35 z=1

Is your solution unique?

(ii) Suppose that nn and mm are coprime. Show that the simultaneous congruences

xa(modn)xb(modm)\begin{array}{ll} x \equiv a & (\bmod n) \\ x \equiv b & (\bmod m) \end{array}

have the same set of solutions as xc(modmn)x \equiv c(\bmod m n) for some cNc \in \mathbb{N}. Hence solve (i.e. find all solutions of) the simultaneous congruences

3x1(mod5)5x1(mod7)7x1(mod3)\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,n1r, n \geqslant 1, denote by ϕr(n)\phi_{r}(n) the number of ordered r-tuples (x1,,xr)\left(x_{1}, \ldots, x_{r}\right) of integers xix_{i} satisfying 1xin1 \leqslant x_{i} \leqslant n for i=1,,ri=1, \ldots, r and such that the greatest common divisor of {n,x1,,xr}\left\{n, x_{1}, \ldots, x_{r}\right\} is 1 . Show that

ϕr(n)=nrpn(11pr)\phi_{r}(n)=n^{r} \prod_{p \mid n}\left(1-\frac{1}{p^{r}}\right)

where the product is over all prime numbers pp dividing nn.

Typos? Please submit corrections to this page on GitHub.