How Can You Prove This Number Theory Function?

And thus our result holds for ab, which completes the proof. In summary, we have proven that the equality holds for prime powers, and by using the fact that \tau and \sigma are multiplicative, we can extend this to any positive integer.
  • #1
icystrike
445
1
This is not a homework , i got this question from the internet.

Prove:
attachment.php?attachmentid=22536&stc=1&d=1260952985.jpg
 

Attachments

  • 3.jpg
    3.jpg
    2.6 KB · Views: 411
Physics news on Phys.org
  • #2
We have:
[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
Hi rasmhop !
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
Ok. I'm not sure at exactly what level you want the explanation, but let me try a somewhat more elementary approach using your hint. I use some manipulations of sums, but I don't know how familiar you are with this stuff. If there is something you're not clear on just ask. Anyway the general idea is to first prove the case for prime powers, then prove the both the left-hand side and right-hand side are multiplicative.

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]
 

Related to How Can You Prove This Number Theory Function?

1. What is number theory function?

Number theory function is a branch of mathematics that studies the properties and relationships of integers. It involves understanding the patterns and structures of numbers and their properties such as divisibility, prime numbers, and factors.

2. What are some examples of number theory functions?

Some examples of number theory functions include the greatest common divisor (GCD), least common multiple (LCM), Euler's totient function, and the prime counting function.

3. How is number theory function used in real-life applications?

Number theory function has various applications in real-life such as in cryptography, coding theory, and computer science. It is also used in practical applications such as creating secure passwords and generating random numbers.

4. What are the main branches of number theory function?

The main branches of number theory function are analytic number theory, algebraic number theory, and arithmetic geometry. Analytic number theory deals with the properties of numbers using techniques from analysis, while algebraic number theory studies number fields and their algebraic properties. Arithmetic geometry combines the techniques of algebraic geometry and number theory to study the relationships between algebraic equations and integer solutions.

5. What are some famous theorems in number theory function?

Some famous theorems in number theory function include Fermat's Last Theorem, which states that there are no positive integer solutions to the equation x^n + y^n = z^n for n > 2, and the Prime Number Theorem, which gives an estimate of the number of prime numbers below a given number. Other important theorems include the Fundamental Theorem of Arithmetic, Wilson's Theorem, and the Chinese Remainder Theorem.

Similar threads

Replies
9
Views
1K
Replies
5
Views
934
  • Linear and Abstract Algebra
Replies
3
Views
894
  • Linear and Abstract Algebra
2
Replies
42
Views
3K
  • Linear and Abstract Algebra
Replies
7
Views
1K
  • Linear and Abstract Algebra
Replies
5
Views
1K
  • Atomic and Condensed Matter
Replies
0
Views
1K
  • Linear and Abstract Algebra
2
Replies
55
Views
4K
Replies
2
Views
823
  • Linear and Abstract Algebra
Replies
2
Views
920
Back
Top