Why is $I^1=\varphi*I^0$?

82 Views Asked by At

Why is $I^1=\varphi*I^0$ ?

where, $I^j(n)=n^j$ and $(f*g)(n)=\sum\limits_{d\in\mathbb N, d\mid n}f(d)g(\frac{n}d)$

$\varphi$ is the Euler-totient function, $\varphi(c)=\left(\prod\limits_{p\text{ prime},\atop p\mid c}\frac{p-1}{p}\right)c$

So $I^1(n)=n\overset!=\varphi*I^0(n)=\sum\limits_{d\in\mathbb N,\atop d\mid n}\left(\prod\limits_{p\text{ prime},\atop p\mid d}\frac{p-1}{p}\right)d\cdot \underbrace{I^0(\frac{n}d)}_{=1}$ now it becomes complicated can you help

(Latex question: How can I write several conditions under a product or sum one above the other)

1

There are 1 best solutions below

0
On BEST ANSWER

The convolution $\varphi * I^0$ is commutative, so

$$\varphi * I^0 =\sum_{d\mid n}\varphi(n)\left(\frac{n}{d} \right)^0= \sum_{d\mid n} \varphi\left(\frac{n}{d}\right).$$

It is conventient to look at the latter term, rather than the second one, because it is easier to see what is going on.

The Euler totient function counts the number of elements in $\Bbb{Z}/n\Bbb{Z}$ that are coprime with $n$, hence gives $\left| (\Bbb{Z}/n\Bbb{Z})^{\times}\right|$ as value for $\varphi(n)$, because each elements that is coprime with $n$ generates $\Bbb{Z}/n\Bbb{Z}$. The Euler totient function is therefore defined as

$$\varphi(n):= \sum_{m=1}^{n} \left\lfloor \frac{1}{\gcd(n,m)} \right\rfloor.$$

Generally if $\gcd(n,k)=d$ then $\gcd\left(\frac{n}{d},\frac{k}{d} \right)=1$, so $\varphi\left(\frac{n}{d}\right)$ counts the positive numbers $k \le n$ such that $\gcd(n,k)=d$. Now

$$\sum_{d\mid n}\varphi\left(\frac{n}{d}\right)$$

counts the number of positive integers $k\le n$ such that $\gcd(n,k)=d$ for all divisors of $n$ and this number is exactely $n = I^1 = \sum_{d\mid n} \varphi\left(\frac{n}{d}\right) = \sum_{d\mid n} \varphi(d)$.