2.3: Problem 12: Find the number of positive integers \(\leq 7200\) that are prime to \(3600\).
Solution
We already computed the number of positive numbers that are prime to \(3600\) in problem \(10\).
$$
\begin{align*}
\phi(3600) &= 3600 \cdot \left( 1- \frac{1}{2}\right) \cdot \left(1- \frac{1}{3}\right) \cdot \left(1- \frac{1}{5} \right) = 960 \\
\end{align*}
$$
But since \(7200 = 2 \cdot 3600\). Then, we have an additional block of \(3600\) numbers. The first block comprises of numbers in \(1 \cdots 3600\). The second block comprises of numbers in \(3601 \cdots 7200\). Recall now that if \(m\) and \(n\) are integers such that \(m = kn + a\). Then
$$
\begin{align*}
\gcd(m, n) &= \gcd(a + kn, n) \\
&= \gcd(a, n) \quad \text{(By Euclid's Algorithm)}\\
&= \gcd(m \bmod n, n)
\end{align*}
$$
This means that for any number \(m\) in the second block, we have:
$$
\begin{align*}
\gcd(m, 3600) &= \gcd(m \bmod 3600, 3600)
\end{align*}
$$
So, every number in the second block has the same gcd with \(3600\) as some number in the first block. Therefore, the number of integers less than or equal to \(7200\) that are coprime to \(3600\) is exactly
$$
\begin{align*}
\phi(3600) + \phi(3600) &= 960 + 960 = 1920
\end{align*}
$$