Calculating $\phi(100)$ where $\phi$ is the totient function

Question

---

The Question:

---

Calculate $\phi(100)$

---

My Attempt:

---

I attempted to calculate the totient function at the value 100, i.e.:

$$\phi(100)$$

To do this, I used the product rule of the totient function:

$\phi(ab)$ = $\phi(a)$ $\times$ $\phi(b)$

So $\phi(100)$ = $\phi(25)$ $\times$ $\phi(4)$

= $\phi(5)$ $\times$ $\phi(5)$ $\times$ $\phi(2)$ $\times$ $\phi(2)$

= 4 $\times$ 4 $\times$ 1 $\times$ 1

= 16.

---

The Confusion (if you will)

---

However, when I searched up the totient function of 100 online, it consistently came up with 40. This seems to me like a more appropriate answer, but I'm not quite sure where I went wrong on my attempt. Could you please tell me where I went wrong?

---

Thanks!

---

Answer 1

Well, @Arthur cleared this up for me in the comments, so I'll answer my own question:

$\phi(ab)$ = $\phi(a)$ $\times$ $\phi(b)$, only if a and b are co-prime.

So, while $\phi(100)$ = $\phi(25)$ $\times$ $\phi(4)$ because 25 and 4 are co-primes, $\phi(100)$ = $\phi(5)$ $\times$ $\phi(5)$ $\times$ $\phi(2)$ $\times$ $\phi(2)$ is not true because the 2s are not coprime, and the 5s are not co-prime either.

So, $\phi(100)$ = $\phi(25)$ $\times$ $\phi(4)$.

$\phi(25)$ = 20 (We can evaluate this through the formula $\phi(p^n) = p^{n-1}(p-1)$, so $\phi(5^2) = 5^{1}(4) = 5 \times 4 = 20$.

$\phi(4)=2$.

$\implies \phi(100)$ = $20 \times 2= 40$.

Thanks to @Arthur and @DreiCleaner for clearing this up, and @J.W.Tanner for suggesting some ways to make this answer better!

Answer 2

As pointed out in the comments, $5$ and $5$ are not coprime, so you cannot use the product rule there. Same for $2$ and $2$. I suggest simply counting directly, as it's rather small numbers involved.

There is, however, also a simple rule for $\phi(a^n)$ you can use, either at that stage for $\phi(4)$ and $\phi(25)$, or immediately for $100=10^2$. If you haven't seen that rule, here is a small pointer to get you started:

How many numbers from 0 to 10 are coprime to 10? How about from 10 to 20? What about from 20 to 30? What about [and so on...]

Finally, is there a difference between being coprime to 10 and coprime to 100?

Answer 3

Okay... rule 1:

If $p$ is prime $\phi(p) = p-1$. That should be clear as as $1$ to $p-1$ are all relatively prime to $p$.

Rule 2:

If $n = p^k$ then $\phi(p) = p^{k-1}(p-1)$.

Not so obvious on the outset but if you consider than all numbers between $1$ and $p^k-1$ are of the form $q*p + r; 0\le r < p$ than $p*p + r$ relatively prime if an only if $r\ne 0$ and so then numbers $q*p + 1, q*p+2, ....q*p+(n-1)$ are relatively prime while $q*p + 0$ is not. For every $q$ there are $p-1$ of these $q*p + r; r\ne 0$ and the question remains how many $q$s are there? Well, $q$ can be as little as $0$ for $n=1,...., p-1$ and as big as $p^{k-2}$ for $p^{k-1} +1=p*p^{k-1}+1,.., $ to $p^k-1 = p*p{k-1} + (p-1)$. so there are $p^{k-1}$ possible $q$s and so there are $(p-1)\times p^{k-1}$ or $p^{k-1}(p-1)$ numbers relatively prime to $p^k$.

The final rule is

rule 3: If $\gcd(a,b)=1$ then $\phi(ab) = \phi(a)\phi(b)$. This with the other rules can determine $\phi(n)$ for all positive integer $n$ by considering the prime factorization of $n$. If $n = \prod p_i^{k_i}$ then $\phi (n) = \prod \phi(p_i^{k_i}) = \prod( (p-1)p_i^{k_i-1})$.

So $\phi (100) = \phi (4)\phi (25)=\phi(2^2) \phi(5^2) = (2-1)2^{2-1}(5-1)25^{2-1} = 2*20 = 40$.

Now the reason for rule 3: is similar two the first to rules but a bit more of a headache to derive. But it can be done.

Here's rough argument:

Out of every $a$ numbers $\phi(a)$ of them will be relatively prime to $a$ and $(a-\phi(a))$ of them will not.

So out of $ab$ numbers $b\phi(a)$ of the will be relatively prime to $a$ and $(ab - b\phi(a)$ will not be.

Out of every $b$ numbers $\phi(b)$ of them will be relatively prime to $b$ and $(b-\phi(b))$ of them will not.

So out of $ab$ numbers $a\phi(b)$ of the will be relatively prime to $a$ and $(ab - a\phi(b))$ will not be.

And out of $ab$ numbers $(b-\phi(b))(a-\phi(a))$ will not be relatively prime to either $a$ nor $b$.

Using inclusion/exclusion

$\phi(ab) =$ the number of numbers relatively prime to $ab$ less than $ab=$

the number of numbers that are relatively prime to both $a$ and to $b=$

The total number of numbers up to $ab$ minus the numbers that are not relatively prime to $a$ minus the number that are not relatively prime to $b$ plus (to avoid double counting) the numbers number that are not relatively prime to either $=$

$ab - (a-\phi(a))b - (b-\phi(b))a + (a-\phi(a))(b-\phi(b) =$

$ab - ab +b\phi(a) -ab +a\phi(b) +ab - b\phi(a) -a\phi(b) + \phi(a)\phi(b) =$

$\phi(a)\phi(b)$

Ta-da.