A functional ecuation using divizors

80 Views Asked by At

It’s a functional equation. We have a function f defined on pozitive integers (greater than 0) with values on real numbers. Also,enter image description here for any pozitive (and non zero) integer n. It asks to find function f.

In their solution, they found f(1)=1 and by substituting n with p^n where p is a pozitive prime number, they also found f(p^n)=p^n - p^(n-1) for any prime p and for any pozitive integer n>0. Next they said they prove by induction by s=mn that f(mn)=f(m)f(n) for any relatively prime positive integers m and n. So proof by induction by s=mn. For s=1 it is clear that it’s true. Suppose the statement is true for any s<=t where t>=1 and prove the statement for s+1. So, let m,n relatively prime positive integers such that mn=t+1. We have enter image description here But I didn’t understand anything starting from mn=..... . Could you please help me understand what they did here? I don’t know sigma sum symbol well.. so could you please explain step by step what they did? Thank you! Also if it helps, the result is f(n)= Euler’s totient function of n.

1

There are 1 best solutions below

0
On BEST ANSWER

The divisors $d$ of $nm$ are of the form $d_1 d_2$ with $d_1\mid m$ and $d_2\mid n$. Thus $$mn=\sum_{d\mid nm} f(d)=\sum_{d_1\mid n, d_2\mid m} f(d_1 d_2)= \sum_{d_1\mid n} \sum_{ d_2\mid m} f(d_1 d_2)=\\\sum_{d_1\mid n, d_1\not=n} \sum_{ d_2\mid m} f(d_1 d_2)+\sum_{ d_2\mid m} f(n d_2)=\sum_{d_1\mid n, d_1\not=n} \sum_{ d_2\mid m} f(d_1 d_2)+\sum_{ d_2\mid m, d_2\not=m} f(n d_2)+f(nm).$$ By induction hypotheses (should be $f(uv)=f(u)f(v)$ for all coprime $u,v$ with $uv<nm$) this simplifies to $$nm=\sum_{d_1\mid n, d_1\not=n} \sum_{ d_2\mid m} f(d_1)f(d_2)+\sum_{ d_2\mid m, d_2\not=m} f(n)f( d_2)+f(nm)=\\ \sum_{d_1\mid n, d_1\not=n} f(d_1)\sum_{ d_2\mid m}f(d_2)+f(n)\sum_{ d_2\mid m, d_2\not=m} f( d_2)+f(nm)= \\ \left(\sum_{d_1\mid n} f(d_1)-f(n)\right)\sum_{ d_2\mid m}f(d_2)+f(n)\left(\sum_{ d_2\mid m} f( d_2)-f(m)\right)+f(nm)=\\ (n-f(n))m+f(n)(m-f(m))+f(nm)=nm-f(n)f(m)+f(mn), $$ the desired result.