1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.