# Representation of Euler phi function

Reading through Strayer's 'Elementary Number Theory', after the following theorems are proved:

• If $$f$$ is a multiplicative arithmetic function, then so is $$F(n)=\sum_{d|n, d>0}f(d)$$.

• Euler's phi function $$\varphi(n)$$ is multiplicative.

there is a remark that the proof that $$\varphi(n)$$ is multiplicative is longer than some other proofs of multiplicativity because $$\varphi$$ cannot be represented by $$\sum_{d|n, d>0}f(d)$$ for some multiplicative $$f$$.

Is this actually a theorem? Or just some offhand remark that $$\varphi$$ isn't easily seen to have such a representation?

• Try it out! What is $f(1)$? And $f(2)$? And... – RghtHndSd Jun 12 at 2:11
• Moreover, $\varphi(n)$ cannot be represented by $\sum_{d|n, d>0}f(d)$ for some FUNCTION $f$. – Zongxiang Yi Jun 12 at 2:31
• – nmasanta Jun 12 at 4:42

Theorem: $$\varphi$$ cannot be represented by $$\sum_{d|n, d>0}f(d)$$ for some funtion $$f$$.

Proof: Assume that there exists a function $$f$$, such that $$\varphi(n)=\sum_{d|n, d>0}f(d)$$. Consider some special cases.

1) For $$n=1$$, we have $$\{d\in \mathbb{Z} : d\mid 1, d>0\}=\{1\}$$ and $$\varphi(1)=f(1)=1$$

2) For a prime number $$p$$, we have $$\{d\in \mathbb{Z} : d\mid p, d>0\}=\{1,p\}$$. Thus $$\varphi(p)=f(1)+f(p)=1+f(p)=p-1.$$ So $$f(p)=p-2$$.

3) For $$n=pq$$, where $$p,q$$ are prime numbers, we have $$\{d\in \mathbb{Z} : d\mid pq, d>0\}=\{1,p,q,pq\}$$, $$\varphi(pq)=\varphi(p) \varphi(q)=(p-1)(q-1)=pq-p-q+1,$$ and $$\sum_{d|n, d>0}f(d)=f(1)+f(p)+f(q)+f(pq)=f(pq)+p-2+q-2+1=f(pq)+p+q-3.$$ If $$\varphi(pq)=\sum_{d|n, d>0}f(d)$$ then $$f(pq)+p+q-3=pq-p-q+1$$ and thus $$f(pq)=pq-2p-2q+4=f(p)f(q).$$ 4)For $$n=p^k$$ where $$k\ge 1$$, we have $$\{d\in \mathbb{Z} : d\mid p^k, d>0\}=\{p^i\mid i=0,\cdots,k\}$$, $$\varphi(p^k)=p^{k-1}(p-1)$$ and $$\sum_{d|n, d>0}f(d)=\sum_{i=0}^{k}f(p^i).$$ If $$\varphi(p^k)=\sum_{d|n, d>0}f(d)$$ then $$p^{k-1}(p-1)=\sum_{i=0}^{k}f(p^i)$$ and thus $$p^{k}(p-1)=\sum_{i=0}^{k+1}f(p^i).$$ Hence $$f(p^{k+1})=p^k(p-1)-p^{k-1}(p-1)=p^{k-1}(p-1)^2.$$

To sum up, for any $$n=p^k\ge 1$$, we have $$f(p^k)=\begin{cases} 1, &k=0, \\ p-2, &k=1, \\ p^{k-2}(p-1)^2, &k\ge 2. \end{cases}$$

Thans for @Francis Adams 's comment. The rest is to discuss the case $$n=p^sq^t$$ where $$p\ne q$$ are two primes. To be continued...

• Rereading this, don't you use that f is multiplicative, saying in the second to last line that f(pq)=pq? Also, what seems to be a smaller error, it should be that f(p)=p-2. In bullet point 2) you seem to introduce an extra minus sign. – Francis Adams Aug 12 at 16:04