Paper 4, Section II, E

Numbers and Sets | Part IA, 2019

State the inclusion-exclusion principle.

Let n2n \geqslant 2 be an integer. Let X={0,1,2,,n1}X=\{0,1,2, \ldots, n-1\} and

Y={(a,b)X2gcd(a,b,n)=1}Y=\left\{(a, b) \in X^{2} \mid \operatorname{gcd}(a, b, n)=1\right\}

where gcd(x1,,xk)\operatorname{gcd}\left(x_{1}, \ldots, x_{k}\right) is the largest number dividing all of x1,,xkx_{1}, \ldots, x_{k}. Let RR be the relation on YY where (a,b)R(c,d)(a, b) R(c, d) if adbc0(modn)a d-b c \equiv 0(\bmod n).

(a) Show that

Y=n2pn(11p2)|Y|=n^{2} \prod_{p \mid n}\left(1-\frac{1}{p^{2}}\right)

where the product is over all primes pp dividing nn.

(b) Show that if gcd(a,b,n)=1\operatorname{gcd}(a, b, n)=1 then there exist integers r,s,tr, s, t with ra+sb+tn=1r a+s b+t n=1.

(c) Show that if (a,b)R(c,d)(a, b) R(c, d) then there exists an integer λ\lambda with λac(modn)\lambda a \equiv c(\bmod n) and λbd(modn)\lambda b \equiv d(\bmod n). [Hint: Consider λ=rc+sd\lambda=r c+s d, where r,sr, s are as in part (b).] Deduce that RR is an equivalence relation.

(d) What is the size of the equivalence class containing (1,1)?(1,1) ? Show that all equivalence classes have the same size, and deduce that the number of equivalence classes is

npn(1+1p)n \prod_{p \mid n}\left(1+\frac{1}{p}\right) \text {. }

Typos? Please submit corrections to this page on GitHub.