This is question 6E from the 2019 Cambridge Mathematics Tripos paper 1A (which can be accessed at https://www.maths.cam.ac.uk/undergrad/pastpapers/files/2019/paperia_4_2019.pdf).
"Let $n\geq 2$ be an integer. Let $X = \{0,1,2,…,n-1\}$ and $Y=\{(a,b) \in X^2\mid \operatorname{gcd}(a,b,n)=1\}$.
Show that $$|Y|=n^2 \prod_{p \mid n}(1-\frac{1}{p^2})$$ where the product is over all primes $p$ dividing $n$."
The previous part of the question asks respondents to state the inclusion-exclusion principle, so I believe that this is supposed to be a hint.
My thoughts on the solution include the following:
If we have $\operatorname{gcd}(a,n)=k$ and $\operatorname{gcd}(b,n)=j$, then the condition that $\operatorname{gcd}(a,b,n)=1$ seems to imply that:
- $k$ and $j$ must be relatively prime
- $\operatorname{gcd}(a,b)=m$, where $\operatorname{gcd}(m,k) = \operatorname{gcd}(m,j)=1$.
In fact, these two conditions collectively seem to imply that $\operatorname{gcd}(a,b,n)=1$. But I could not get anywhere with this. I am also aware of the totient function $\phi(n)$, and I've tried to extend the proof that $$\phi(n)=\prod_{p\mid n} n(1-\frac{1}{p})$$ but was unable to. I noticed that the desired form in the question is actually equivalent to $\phi(n^2)$, but was unable to use this to generate a proof.
Any hints / solutions would be appreciated.
Best Answer
Consider first the case of $n$ having just one prime factor $p$, so $n = p^e$ for some integer $e \ge 1$. As you surmised, the inclusion-exclusion principle can be used. To get the elements $(a,b) \in Y$, first include those where $\gcd(a, p) = 1$, with this being $n\left(\frac{p - 1}{p}\right)$ integers, and with $b$ being any integer in $X$, i.e., $n$ of them, for a combined total of $\left(n\left(\frac{p - 1}{p}\right)\right)n$ ordered pairs. Next, include the $(a,b)$ where the roles of $a$ and $b$ are switched, i.e., $a$ is any integer in $X$ and $\gcd(b, p) = 1$, with this resulting in the same product. However, we've double-counted where both $a$ and $b$ are relatively prime to $p$, with this being $n\left(\frac{p - 1}{p}\right)n\left(\frac{p - 1}{p}\right)$ pairs, so these need to be excluded from the sum. Putting this together gives
$$\begin{equation}\begin{aligned} \left| Y \right| & = 2n^2\left(\frac{p - 1}{p}\right) - n^2\left(\frac{p - 1}{p}\right)^2 \\ & = n^2\left(\frac{2p}{p}\left(\frac{p - 1}{p}\right) - \frac{p^2 - 2p + 1}{p^2}\right) \\ & = \frac{n^2}{p^2}\left(2p^2 - 2p - p^2 + 2p - 1\right) \\ & = \frac{n^2}{p^2}\left(p^2 - 1\right) \\ & = n^2\left(1 - \frac{1}{p^2}\right) \end{aligned}\end{equation}\tag{1}\label{eq1A}$$
This proves your statement for the case where $n$ has only one prime factor. Next, let
$$f(n) = \left| Y \right| \tag{2}\label{eq2A}$$
Since you've written you're willing to accept just hints, I'll leave it to you to extend \eqref{eq1A} to get the result you're asking to prove where $n$ has any number of distinct prime factors, such as by proving & using that $f(n)$ is a multiplicative function (e.g., by using a similar argument outlined in Euler's totient function of proving a bijection between sets using the Chinese remainder theorem).