Question

show that
\[\sigma(n)= \sum\limits_{d\mid n} \tau(d)\phi(n/d)\]

Answer 1

i'm 12 and what is this

Answer 2

just tell me the definitions... maybe I'll try to figure out the rest.

sigma - sum of divisors
tau - number of divisors
phi - totient function

Answer 3

\(\tau(n)\) = number of positive divisors of \(n\)

\(\sigma(n)\) = sum of positive divisors of \(n\)

Answer 4

\(\phi(n)\) = number of positive integers less than \(n\) that are relatively prime to \(n\)

Answer 5

yes, alright. that's what I thought.

Answer 6

for example, every positive integer less than \(p\) is relatively prime to \(p\), so we have :

\(\phi(p)=p-1\)

Answer 7

\(p\) is a prime number ..

Answer 8

OK, this is great...

Answer 9

the sum \(\sum\limits_{d\mid n}f(d)\) is a short form for saying :

take the sum of \(f(d)\)'s where \(d\) is a positive divisor of \(n\)

Answer 10

yes, got it.

Answer 11

for example,
\[\sum\limits_{d\mid 15} f(d) = f(1)+f(3)+f(5)+f(15)\]

Answer 12

Let's start small by an example\[n = 2^3\cdot 3^4\]\[\sigma (n) = (1+ 2 + 2^2 + 2^3)(1+3+3^2+3^3+3^4)\]Now a typical term in the right-side sum would be, say, considering \(d = 2^a 3^b\) where a and b are in their respective limits...
\(\tau(d) = (a+1)(b+1) \)
Meanwhile \(\phi(n/d)=\phi(2^{3-a}\cdot 3^{4-b})=\phi (2^{3-a})\cdot \phi(3^{4-b} )=\cdots\)

Answer 13

Dunno if getting closer.\[\sum_{0\le a\le 3, 0 \le b \le 4}(a+1)(b+1)+\sum_{}\phi (2^{3-a})\phi(3^{4-b})\]

Answer 14

Is there a nice closed form expression for\[\phi( 1) + \phi(2) + \phi(4) + \cdots + \phi(2^n)\]

Answer 15

Nice ! there is :

\[n = \sum\limits_{d\mid n}\phi(d)\]

Answer 16

\[\phi( 1) + \phi(2) + \phi(4) + \cdots + \phi(2^n) = 2^n\]

Answer 17

but we need to take the sum of \(\tau(d)\phi(n/d)\) right

Answer 18

So wouldn't I get\[2^3 3^4 + \sum (a+1)(b+1)\]

Answer 19

Why have I added those two sums? lol!

Answer 20

exactly! i think it should be
\[\sigma(2^33^4)=\sum_{0\le a\le 3, 0 \le b \le 4}(a+1)(b+1)\phi (2^{3-a})\phi(3^{4-b})\]

Answer 21

yes, I'm really sorry.

Answer 22

so we haven't gotten any closer

Answer 23

number theory is interesting...

Answer 24

for sure it is interesting !
btw i don't have a proof for the problem i have posted... im still working on it..

Answer 25

i think we have worked on this before. let me check

Answer 26

nvm i don't have patient to search lol. lets try again.

Answer 27

Dare I...

\[\tau \star \varphi = (u \star u) \star (\mu \star N) = u \star (u \star \mu) \star N = u \star N = \sigma \]

Answer 28

Parenthesis are unnecessary, just trying to highlight the important stuff. Since the set of multiplicative functions with the Dirichlet convolution forms a group, it's automatically associative (since that's a requirement to be a group) and not only that, this is an Abelian group (commutative).

I also used the fact that \(\mu \star u = \delta\) is the identity. :D

Answer 29

\(\Large \text{let}~~ n=p_{1}^{k_1}p_{2}^{k_1}p_{3}^{k_3}...p_{i}^{k_i}\)
\(\Large \sigma(n)= \sum\limits_{d\mid n} \tau(d)\phi(n/d)\\
~~~~~~~~~~~~ \Large =\sum\limits_{d\mid n} \tau(n/d)\phi(d)=\sum\limits_{d\mid n} 1.d=\sum\limits_{d\mid n} d \)


i'm like daring as you kai ;)

Answer 30

i think i did nothing i should explain that
n=d .n/d =dd' blah blah ok i'll make it more simple

Answer 31

this is a quite interesting problem :)