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(1200)$?
What is $\phi(181)$?
What is $\phi(212)$?
Euler's Totient Function! The savior!
Let's look at 1200 first.
First, let me explain the process.
We must prime factorize every number first. For 1200, we have
\(1200 = 12 * 5^2 * 2^2 = 2^4 * 3 * 5^2\)
Now, to summarize what we do, we essentially
\(\frac{\text{number we start with}}{\text{product of the prime factors}} \cdot \text{product of every prime factor -1}\)
So for 1200, we have \(\phi{1200} = 1200 / ( 2 * 3 * 5) * (2-1)(3-1) (5-1) = 40 (1)(2)(4) = 320\)
Meaning the answer is 320.
Now, let's do the same for the other two numbers.
First off, 181. It's a prime number, so the only prime factor is 181. Thus, we have
\(\phi 181 = \frac{181}{181}\cdot (181-1) = 180\). So 180 is the answer.
Now, let's also do 212. We have that \(212 = 2^2*53\)
Thus, using Euler's Totient Function, we have
\(\phi212 = \frac{212}{2*53} \cdot (2-1)(53-1) = 2*52 = 104\) so 104 is the answer.
Thus, the 3 answers are
\(\phi1200 = 320\\ \phi 181 = 180\\ \phi 212 = 104\)
Thanks! :)
Euler's Totient Function! The savior!
Let's look at 1200 first.
First, let me explain the process.
We must prime factorize every number first. For 1200, we have
\(1200 = 12 * 5^2 * 2^2 = 2^4 * 3 * 5^2\)
Now, to summarize what we do, we essentially
\(\frac{\text{number we start with}}{\text{product of the prime factors}} \cdot \text{product of every prime factor -1}\)
So for 1200, we have \(\phi{1200} = 1200 / ( 2 * 3 * 5) * (2-1)(3-1) (5-1) = 40 (1)(2)(4) = 320\)
Meaning the answer is 320.
Now, let's do the same for the other two numbers.
First off, 181. It's a prime number, so the only prime factor is 181. Thus, we have
\(\phi 181 = \frac{181}{181}\cdot (181-1) = 180\). So 180 is the answer.
Now, let's also do 212. We have that \(212 = 2^2*53\)
Thus, using Euler's Totient Function, we have
\(\phi212 = \frac{212}{2*53} \cdot (2-1)(53-1) = 2*52 = 104\) so 104 is the answer.
Thus, the 3 answers are
\(\phi1200 = 320\\ \phi 181 = 180\\ \phi 212 = 104\)
Thanks! :)
Excellent, NTS !!!!
{Without the Totient Function , this would be very tedious.... Euler was a pretty smart guy......!!! }
"Hey, it's still possible to do it without the function" - famous last words 😂
Thanks, CPhill!
~NTS