A functional ecuation using divizors
up vote
1
down vote
favorite
It’s a functional equation. We have a function f defined on pozitive integers (greater than 0) with values on real numbers. Also,
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 
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.
number-theory divisor-sum mobius-inversion
edited Nov 30 at 11:22
Ivan Neretin
8,76021535
asked Nov 24 at 19:56
furfur
854
add a comment |
up vote
1
down vote
favorite
It’s a functional equation. We have a function f defined on pozitive integers (greater than 0) with values on real numbers. Also, 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
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.
number-theory divisor-sum mobius-inversion
edited Nov 30 at 11:22
Ivan Neretin
8,76021535
asked Nov 24 at 19:56
furfur
854
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
It’s a functional equation. We have a function f defined on pozitive integers (greater than 0) with values on real numbers. Also, 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
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.
number-theory divisor-sum mobius-inversion
edited Nov 30 at 11:22
Ivan Neretin
8,76021535
asked Nov 24 at 19:56
furfur
854
It’s a functional equation. We have a function f defined on pozitive integers (greater than 0) with values on real numbers. Also, 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
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.
number-theory divisor-sum mobius-inversion
number-theory divisor-sum mobius-inversion
edited Nov 30 at 11:22
Ivan Neretin
8,76021535
asked Nov 24 at 19:56
furfur
854
edited Nov 30 at 11:22
Ivan Neretin
8,76021535
asked Nov 24 at 19:56
furfur
854
edited Nov 30 at 11:22
Ivan Neretin
8,76021535
edited Nov 30 at 11:22
Ivan Neretin
8,76021535
edited Nov 30 at 11:22
Ivan Neretin
8,76021535
8,76021535
asked Nov 24 at 19:56
furfur
854
asked Nov 24 at 19:56
furfur
854
asked Nov 24 at 19:56
furfur
854
854
add a comment |
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3012012%2fa-functional-ecuation-using-divizors%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
