- #1

- 446

- 1

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter icystrike
- Start date

- #1

- 446

- 1

- #2

- 430

- 3

[tex]\sum_{d|n} \frac{n}{d}\tau(d) = \sum_{d | n} d \tau(n/d)[/tex]

There is a bijective correspondence between divisors of n/d and multiples of d that divide n. Thus [itex]\tau(n/d)[/itex] equals the number of integers k such that d | k and k | n. Now [itex]\sigma(d)[/itex] equals the sum of all divisors of d so on the left-hand side we have [itex]\tau(n/d)[/itex] terms of d which shows the equality. To establish this through a somewhat more formal argument define:

[tex]S = \{(d,k) \,:\, d |k, k | n\}[/tex]

For a finite subset T of [itex]\mathbb{Z}^2[/itex] define:

[tex]w(T) = \sum_{(d,k) \in T} d[/tex]

This has the nice property that if [itex]A,B \subseteq \mathbb{Z}^2[/itex], then,

[tex]w(A \cup B) = w(A) + w(B) - w(A \cap B)[/tex]

We wish to show that both our sides of the equality equal w(S). To do this we decompose S in two ways. First define

[tex]S_d = \{(d,k) \,:\, d|k, k |n\}[/tex]

Then [itex]|S_d|=\tau(n/d)[/itex] so [itex]w(S_d) = d\tau(n/d)[/itex]. We can then show:

[tex]w(S) = \sum_{d|n} w(S_d) = \sum_{d|n} d\tau(n/d)[/tex]

This deal with the right-hand side. On the other hand let

[tex]T_k = \{(d,k) \,:\, d|k, k |n\}[/tex]

Then [itex]w(T_k) = \sum_{d|k} d = \sigma(k)[/itex], which shows:

[tex]w(S) = \sum_{d|n} w(T_d) = \sum_{d|n} \sigma(d)[/tex]

- #3

- 446

- 1

I am new to number theoretic function , i don't understand what do you mean by bijective correspondence and your sets notation.

I was given a hint to start of by starting to prove for the case of [tex]p^{k}[/tex] instead of n , such that p is a prime number. could you explain in a slightly elementary level.

Thanks in advance (=

- #4

- 430

- 3

Let us consider the case [itex]n=p^k[/itex] for some prime p and positive integer k. We have

[tex]\sigma(p^c) = 1+p+p^2+\cdots+p^c[/tex]

so for our left-hand side we have:

[tex]\begin{align*}

\sum_{d | p^k} \sigma(d) &= \sum_{i=0}^k \sigma(p^i) \\

&= \sum_{i=0}^k \sum_{j=0}^i p^j

\end{align*}[/tex]

It's clear that [itex]p^j[/itex] occurs in this sum once every time [itex]i \geq j[/itex] so the same number of times as the number of elements of [itex]\{j,j+1,\ldots,k\}[/itex] which is k-j+1 so:

[tex]\sum_{d | p^k} \sigma(d) = \sum_{j=0}^k (k-j+1)p^j[/tex]

On the other hand we have [itex]\tau(p^i) = i+1[/itex] which gives:

[tex]\begin{align*}

\sum_{d | n} \frac{n}{d}\tau(d) &= \sum_{i=0}^k \frac{p^k}{p^i} \tau(p^i) \\

&= \sum_{i=0}^k p^{k-i}(i+1)\\

&= \sum_{i=0}^k p^{i}(k-i+1) \\

&= \sum_{d | p^k} \sigma(d)

\end{align*}[/tex]

which shows the case when n is a prime power.

Now we need to use this knowledge to gain an understanding of the general case. Let us assume a and b are coprime and that the case has been proven for both a and b (for instance if a and b are different prime powers), and let us show that the result also holds for ab. Then the result will follow by induction. We know that [itex]\tau[/itex] and [itex]\sigma[/itex] are multiplicative so [itex]\tau(ab) = \tau(a)\tau(b)[/itex] and [itex]\sigma(ab)=\sigma(a)\sigma(b)[/itex]. If [itex]d_1 | a[/itex] and [itex]d_2 | b[/itex], then [itex]d_1d_2|ab[/itex]. Also if [itex]d | ab[/itex], then there exists unique positive integers [itex]d_1,d_2[/itex] such that [itex]d_1 | a[/itex] and [itex]d_2 | b[/itex] (since a and b are coprime). Thus we have:

[tex]\sum_{d |ab} \frac{ab}{d}\tau(d) = \sum_{d_1|a, d_2|b} \frac{ab}{d_1d_2}\tau(d_1d_2)[/tex]

[tex]\sum_{d |ab}\sigma(d) = \sum_{d_1|a, d_2|b} \sigma(d_1d_2)[/tex]

Now we use this to prove that both the left-hand side and the right hand side are multiplicative:

[tex]\begin{align*}

\sum_{d |ab}\sigma(d) &= \sum_{d_1|a, d_2|b} \sigma(d_1d_2) \\

&= \sum_{d_1|a, d_2|b} \sigma(d_1)\sigma(d_2) \\

&= \sum_{d_1|a}\sum_{d_2 | b}\sigma(d_1)\sigma(d_2) \\

&= \sum_{d_1|a}\sigma(d_1)\sum_{d_2 | b}\sigma(d_2) \\

&= \left(\sum_{d_1|a}\sigma(d_1)\right)\left(\sum_{d_2 | b}\sigma(d_2)\right)

\end{align*}[/tex]

And:

[tex]\begin{align*}

\sum_{d|ab}\frac{ab}{d}\tau(d) &= \sum_{d_1|a,d_2|b}\frac{ab}{d_1 d_2}\tau(d_1 d_2) \\

&= \sum_{d_1|a,d_2|b}\frac{a}{d_1}\tau(d_1)\frac{b}{d_2}\tau(d_2) \\

&= \sum_{d_1|a}\left(\frac{a}{d_1}\tau(d_1)\sum_{d_2 | b}\frac{b}{d_2}\tau(d_2)\right) \\

&= \left(\sum_{d_1|a}\frac{a}{d_1}\tau(d_1)\right)\left(\sum_{d_2 | b}\frac{b}{d_2}\tau(d_2)\right)

\end{align*}[/tex]

Now since we assumed the result was true for a and b we have:

[tex]\sum_{d|ab}\frac{ab}{d}\tau(d) = \left(\sum_{d_1|a}\frac{a}{d_1}\tau(d_1)\right)\left(\sum_{d_2 | b}\frac{b}{d_2}\tau(d_2)\right) = \left(\sum_{d_1|a}\sigma(d_1)\right)\left(\sum_{d_2 | b}\sigma(d_2)\right) = \sum_{d |ab}\sigma(d)[/tex]

Share: