Online Course Discussion Forum

Self-Paced MC II-A Number Theory Question

 
 
Picture of David Reynoso
Re: Self-Paced MC II-A Number Theory Question
by David Reynoso - Monday, October 29, 2018, 10:53 AM
 

Recall $\phi(n)$ counts how many number are relatively prime with $n$.

Say $n=10$. Since $10 = 2 \times 5$, it has divisors $1$, $2$, $5$ and $10$. We have that $\phi(1) = 1$, $\phi(2) = 1$, $\phi(5) = 4$, and $\phi(10) = \phi(2) \phi(5) = 4$. Thus, $\phi(1) + \phi(2) + \phi(5) + \phi(10) = 1 + 1 + 4 + 4 = 10$.

You want to show this is true for any integer $n$.