+859 For a positive integer n, \phi(n) denotes the number of positive integers less than or equal to $n$ that are relatively prime to $n$. What is $\phi(2835)$?
+189 Yay, I took Number Theory recently, and I seem to remember how to solve problems like this. The key detail to know is that the phi function is multiplicative. Mathematically, this means that if m and n are relatively prime, then \(\phi(mn) = \phi(m)\phi(n)\). As a consequence, we can represent 2835 into a product of prime powers in the form of \(2835 = p_1^{e^1}p_2^{e_2} \cdots p_n^{e^n}\) where each pi is a unique prime and each ei is the corresponding exponent and then solve the easier resulting problem. Through some trial division, I discovered \(2835 = 3^4*5*7\), so the property of multiplicativity tells us that \(\phi(2835) = \phi(3^4)\phi(5)\phi(7)\). I could just use the formula to solve the rest, but I could not recall it, so I solved it intuitively instead.
\(\phi(5) = 4 \text{ and } \phi(7) = 6\) because the number of relatively prime positive integers less than or equal to a prime p is p - 1 because no integers under consideration, except p itself, will share a common factor.
\(\phi(3^4) = 3^4 - 3^3 = 81 - 27 = 54\) because the number of relatively prime positive integers less than or equal to pe is pe - pe - 1. There are pe integers under consideration and pe - 1 of them share a common factor with the prime p because pe / p = pe - 1, so the remaining integers are relatively prime.
Therefore, \(\begin{align*} \phi(2835) &= \phi(3^4)\phi(5)\phi(7) \\ &= 54 * 4 * 6 \\ &= 1296 \\ \end{align*}\).
