Representation of Euler phi function

110 Views Asked by At

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?

1

There are 1 best solutions below

1
On BEST ANSWER

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