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)$?

AnswerscorrectIy Oct 11, 2024

#1**0 **

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 p_{i} is a unique prime and each e_{i} 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 p^{e} is p^{e} - p^{e - 1}. There are p^{e} integers under consideration and p^{e - 1} of them share a common factor with the prime p because p^{e} / p = p^{e - 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*}\).

The3Mathketeers Oct 11, 2024