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?


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...

  • 1
    $\begingroup$ 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. $\endgroup$ – Francis Adams Aug 12 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.