Crux 4882

Crux Mathematicorum, Problem 4882

A pair \((m,n)\) will generate \(\mathbb{Z}\) as group, that is \(m\mathbb{Z}+n\mathbb{Z}=\mathbb{Z}\) iff \(m,n\) are relatively prime, i.e. \(gcd(m,n)=1\).
If \(m=n\), then that happens only if \(m=n=1\).
We notice the following:
Fact 1 \(gcd(m,n)=1\) iff \(gcd(n,m)=1\), therefore for each pair \((m,n)\) that contributes to \(G\), there is other pair \((n,m)\) that contributes to \(G\).
For each \(n\), the number of integers less than \(n\) that are coprime with \(n\) is given by
\(\begin{equation*} \phi(n)=n\prod_{p|n,p\text{ prime}}\left(\frac{p-1}{p}\right) \end{equation*}\) Then by what we have discussed, we have that
\(\begin{equation*} G=1+2\cdot \sum_{n=2}^{2023}\phi(n) \end{equation*}\)

We prove part \(ii)\) which would imply \(i)\), that is \(G\equiv -1\equiv 7 \pmod{8}\).
Fact 2 We note that if \(4|\phi(n)\), then \(8|(2\phi(n))\), so its contribution to \(G\) is \(0\) mod \(8\), so we can exclude it for our purpose.
We will use this fact repeatedly.
We have the following cases
1)\(n=2\) or \(n=4\)
2) \(n=4pA\), where \(p\) is prime, \(A\) integer.
3) \(n=pqA\), where \(p,q\) are primes, \(A\) integer
4) \(n=8A\) where \(A\) is integer.
In all 2),3),4) cases we notice that \(4|\phi(n)\), so we exclude these cases by Fact 2.
We are left with the cases:
5) \(n=p^k\), where \(p\) is prime , \(k\) integer
6) \(n=2p^k\), where \(p\) is prime, \(k\) integer
Now we note that \(\phi(p^k)=\phi(2p^k)=p^{k-1}(p-1)\), so \(4|(\phi(p^k)+\phi(2p^k))\). Then \(p^k\) together with its double are \(0\) mod \(8\). Thus we can exclude them and we only have to count cases bigger than \(2022/2=1011\). Thus
\(\begin{equation*} G\equiv 1+2\cdot \sum_{n=1012..2023,n=p^k}\phi(n)\pmod{8} \end{equation*}\)
Now, consider subcase \(k=1\). We are only interested on primes of the form \(4s+3\), because if \(p=4s+1\), then \(\phi(p)=4s\). There are 70 prime numbers between 1012 and 2023. Each one contributes a 2 modulo 8, so in total
\(\begin{equation*} 2\cdot \sum_{n=1012..2023,n=p}\phi(n)\equiv 0 \pmod{8} \end{equation*}\)
For the subcase \(k>1\) we verify the only possibilities are \(11^3,37^2,41^2,43^2\), and we have that \(4|(\phi(11^3)+\phi(37^2)+\phi(41^2)+\phi(43^2))\).
In conclusion, only case 1) is under consideration for calculating \(G\) modulo \(8\), thus
\(G\equiv 1+2(\phi(2)+\phi(4))=1+2(1+2)\equiv 7\).