# Prove that ## \sum_{d\mid n}\sigma_{1}(d)\sigma_{1}(\frac{n}{d}) ##

• Math100
In summary: 1^{k}+p^{k}+p^{2\cdot k}+\dotsb +p^{k\cdot k}=\frac{p^{k+1}-1}{p-1} #### \sigma_{0}(p^{k})\sigma_{0}(p^{k})=\frac{(p^{k+1}-1)^{2}}{(p-1)^{2}}=\frac{p^{2k+2}-2p^{k+1}+1}{p^{2}-2p+1}=\frac{p^{2k+2}-2p^{k+1}+1}{p^{2}-2p+1} #### \sigma_{
Math100
Homework Statement
By considering ## u\cdot u\cdot N\cdot N ##, prove that ## \sum_{d\mid n}\sigma_{1}(d)\sigma_{1}(\frac{n}{d})=\sum_{d\mid n}d\sigma_{0}(d)\sigma_{0}(\frac{n}{d}) ##.
Relevant Equations
None.
Proof:

Let ## n\in\mathbb{N} ##.
Then ## \sigma_{\alpha}(n)=(u\cdot N^{\alpha})(n) ## for ## \alpha\neq 0 ## and ## \sigma_{0}(n)=(u\cdot u)(n) ##
such that ## u(n)=1, N(n)=n ## for all ## n ##.
By considering ## u\cdot u\cdot N\cdot N ##, we have that
\begin{align*}
&\sigma_{1}\cdot \sigma_{1}=(u\cdot N)\cdot (u\cdot N)\\
&=(N\cdot u)\cdot (u\cdot N)\\
&=N\cdot (u\cdot u)\cdot N\\
&=N\cdot \sigma_{0}\cdot N\\
&=\sigma_{0}\cdot (N\cdot N).\\
\end{align*}
Observe that
\begin{align*}
&(\sigma_{1}\cdot \sigma_{1})(n)=[\sigma_{0}\cdot (N\cdot N)](n)\\
&=\sum_{d\mid n}\sigma_{0}(\frac{n}{d})(N\cdot N)(d)\\
&=\sum_{d\mid n}\sigma_{0}(\frac{n}{d})\sum_{d_{1}\mid d}N(d_{1})N(\frac{d}{d_{1}})\\
&=\sum_{d\mid n}\sigma_{0}(\frac{n}{d})\sum_{d_{1}\mid d}d_{1}(\frac{d}{d_{1}})\\
&=\sum_{d\mid n}\sigma_{0}(\frac{n}{d})\sum_{d_{1}\mid d}d\\
&=\sum_{d\mid n}\sigma_{0}(\frac{n}{d})d\sum_{d_{1}\mid d}1\\
&=\sum_{d\mid n}\sigma_{0}(\frac{n}{d})d\sum_{d_{1}\mid d}u(d_{1})u(\frac{d}{d_{1}})\\
&=\sum_{d\mid n}\sigma_{0}(\frac{n}{d})d[(u\cdot u)(d)]\\
&=\sum_{d\mid n}d\sigma_{0}(d)\sigma_{0}(\frac{n}{d}).\\
\end{align*}
Since ## (\sigma_{1}\cdot \sigma_{1})(n)=\sum_{d\mid n}\sigma_{1}(d)\sigma_{1}(\frac{n}{d}) ##,
it follows that ## \sum_{d\mid n}\sigma_{1}(d)\sigma_{1}(\frac{n}{d})=\sum_{d\mid n}d\sigma_{0}(d)\sigma_{0}(\frac{n}{d}) ##.
Therefore, ## \sum_{d\mid n}\sigma_{1}(d)\sigma_{1}(\frac{n}{d})=\sum_{d\mid n}d\sigma_{0}(d)\sigma_{0}(\frac{n}{d}) ##.

Math100 said:
Homework Statement:: By considering ## u\cdot u\cdot N\cdot N ##, prove that ## \sum_{d\mid n}\sigma_{1}(d)\sigma_{1}(\frac{n}{d})=\sum_{d\mid n}d\sigma_{0}(d)\sigma_{0}(\frac{n}{d}) ##.
Relevant Equations:: None.

Proof:

Let ## n\in\mathbb{N} ##.
Then ## \sigma_{\alpha}(n)=(u\cdot N^{\alpha})(n) ## for ## \alpha\neq 0 ## and ## \sigma_{0}(n)=(u\cdot u)(n) ##
such that ## u(n)=1, N(n)=n ## for all ## n ##.
How is ##\sigma_0## defined? E.g. you have a variable (or constant) ##u## on the right but not on the left. Then you have ##u## and ##u(n)##, same with ##N##. This is confusing.

I know ##\sigma_k(n)=\displaystyle{\sum_{d|n}d^k}## for ##k\in \mathbb{N}_0.## Would that be correct?
It means that ## \sigma_0(n)## counts all divisors of ##n## and ##\sigma_1(n)## adds them. Right?

I think the hint means that ##\sigma_k(a\cdot b)=\sigma_k(a)\cdot\sigma_k(b)## for any coprime numbers ##a,b.## I would work with the prime decomposition of ##n.##

fresh_42 said:
I think the hint means that ##\sigma_k(a\cdot b)=\sigma_k(a)\cdot\sigma_k(b)## for any coprime numbers ##a,b.## I would work with the prime decomposition of ##n.##
How can the prime decomposition of ## n ## work in here?

Do you mean ## \sigma_{\alpha}(p_{1}^{a_{1}}\dotsb p_{k}^{a_{k}})=\sigma_{\alpha}(p_{1}^{a_{1}})\dotsb \sigma_{\alpha}(p_{k}^{a_{k}}) ##?

If ##n=p_1^{k_1}\cdot\ldots\cdot p_r^{k_r}## then all ##p_i^{k_i},p_j^{k_j}## are coprime if ##i\neq j.## Therefore
$$\sigma_0(n)=\prod_{i=1}^r \sigma_0(p_i^{k_i}) \text{ and } \sigma_1(n)=\prod_{i=1}^r \sigma_1(p_i^{k_i})$$

Now first prove the formula for ##n=p^k.## Then we see how it works for a product of two, say ##p^k\cdot q^m,## which probably shows us the way for any value of ##r.##

fresh_42 said:
How is ##\sigma_0## defined? E.g. you have a variable (or constant) ##u## on the right but not on the left. Then you have ##u## and ##u(n)##, same with ##N##. This is confusing.

I know ##\sigma_k(n)=\displaystyle{\sum_{d|n}d^k}## for ##k\in \mathbb{N}_0.## Would that be correct?
It means that ## \sigma_0(n)## counts all divisors of ##n## and ##\sigma_1(n)## adds them. Right?
Yes, ## \sigma_{0}(n) ## is the number of the divisors of ## n ##, and ## \sigma_{1}(n) ## is the sum of the divisors of ## n ##.

fresh_42 said:
If ##n=p_1^{k_1}\cdot\ldots\cdot p_r^{k_r}## then all ##p_i^{k_i},p_j^{k_j}## are coprime if ##i\neq j.## Therefore
$$\sigma_0(n)=\prod_{i=1}^r \sigma_0(p_i^{k_i}) \text{ and } \sigma_1(n)=\prod_{i=1}^r \sigma_1(p_i^{k_i})$$

Now first prove the formula for ##n=p^k.## Then we see how it works for a product of two, say ##p^k\cdot q^m,## which probably shows us the way for any value of ##r.##
## \sigma_{0}(p^{k})=k+1 ##

## \sigma_{0}(p^{k})=1^{0}+p^{0}+p^{2\cdot 0}+\dotsb +p^{k\cdot 0}=k+1 ##
## \sigma_{1}(p^{k})=1^{1}+p^{1}+p^{2\cdot 1}+\dotsb +p^{k\cdot 1}=\frac{p^{k+1}-1}{p-1} ##

Math100 said:
## \sigma_{0}(p^{k})=k+1 ##
Yes, and that means we have the divisors ##\{1,p,p^2,\ldots,p^k\}.## Thus
\begin{align*}
\sum_{d|n}d\sigma_{0}(d)\sigma_{0}(\frac{n}{d})&=\sum_{m=0}^kp^m\cdot \sigma_{0}(p^m)\sigma_{0}(p^{k-m})=\sum_{m=0}^kp^m\cdot (m+1)\cdot (k-m+1)\\
\sum_{d|n}\sigma_{1}(d)\sigma_{1}(\frac{n}{d})&=\sum_{m=0}^k \dfrac{p^{m+1}-1}{p-1}\cdot\dfrac{p^{k-m+1}-1}{p-1}
\end{align*}
O.k., that looks like a lot of work to do. Maybe the idea wasn't the best way. My problem was that ##d## and ##\dfrac{n}{d}## aren't necessarily coprime so the multiplicativity of ##\sigma_k## isn't useful.

Let us simply check an example.
##n=3^3##.
\begin{align*}
\sum_{d|n}d\sigma_{0}(d)\sigma_{0}(\frac{n}{d})&=\sigma_{0}(1)\sigma_{0}(27)+3\sigma_{0}(3)\sigma_{0}(9)+9\sigma_{0}(9)\sigma_{0}(3)+27\sigma_{0}(27)\sigma_{0}(1)\\
&=4+3\cdot 2\cdot 3+9\cdot 3\cdot 2 +27 \cdot 4= 184\\
\sum_{d|n}\sigma_{1}(d)\sigma_{1}(\frac{n}{d})&=\sigma_{1}(1)\sigma_{1}(27)+\sigma_{1}(3)\sigma_{1}(9)+\sigma_{1}(9)\sigma_{1}(3)+\sigma_{1}(27)\sigma_{1}(1)\\
&=40+4\cdot 13+13\cdot 4 +40=184
\end{align*}
I do not see how this could be done without the work since the summands are so differently.

Could it be that ##n## is assumed to be square-free?

fresh_42 said:
Yes, and that means we have the divisors ##\{1,p,p^2,\ldots,p^k\}.## Thus
\begin{align*}
\sum_{d|n}d\sigma_{0}(d)\sigma_{0}(\frac{n}{d})&=\sum_{m=0}^kp^m\cdot \sigma_{0}(p^m)\sigma_{0}(p^{k-m})=\sum_{m=0}^kp^m\cdot (m+1)\cdot (k-m+1)\\
\sum_{d|n}\sigma_{1}(d)\sigma_{1}(\frac{n}{d})&=\sum_{m=0}^k \dfrac{p^{m+1}-1}{p-1}\cdot\dfrac{p^{k-m+1}-1}{p-1}
\end{align*}
O.k., that looks like a lot of work to do. Maybe the idea wasn't the best way. My problem was that ##d## and ##\dfrac{n}{d}## aren't necessarily coprime so the multiplicativity of ##\sigma_k## isn't useful.

Let us simply check an example.
##n=3^3##.
\begin{align*}
\sum_{d|n}d\sigma_{0}(d)\sigma_{0}(\frac{n}{d})&=\sigma_{0}(1)\sigma_{0}(27)+3\sigma_{0}(3)\sigma_{0}(9)+9\sigma_{0}(9)\sigma_{0}(3)+27\sigma_{0}(27)\sigma_{0}(1)\\
&=4+3\cdot 2\cdot 3+9\cdot 3\cdot 2 +27 \cdot 4= 184\\
\sum_{d|n}\sigma_{1}(d)\sigma_{1}(\frac{n}{d})&=\sigma_{1}(1)\sigma_{1}(27)+\sigma_{1}(3)\sigma_{1}(9)+\sigma_{1}(9)\sigma_{1}(3)+\sigma_{1}(27)\sigma_{1}(1)\\
&=40+4\cdot 13+13\cdot 4 +40=184
\end{align*}
I do not see how this could be done without the work since the summands are so differently.

Could it be that ##n## is assumed to be square-free?
Sorry, may I know how to find ## \sigma_{0}(1), \sigma_{0}(27), ##, etc?

Math100 said:
Sorry, may I know how to find ## \sigma_{0}(1), \sigma_{0}(27), ##, etc?
Your formulas were correct, but I was lazy. I looked them up here:
https://de.wikipedia.org/wiki/Teilerfunktion
The sum over all divisors makes it complicated. That's why I asked if ##n## could be assumed square-free.

fresh_42 said:
Your formulas were correct, but I was lazy. I looked them up here:
https://de.wikipedia.org/wiki/Teilerfunktion
The sum over all divisors makes it complicated. That's why I asked if ##n## could be assumed square-free.
Never mind, I found out how to find those ## \sigma_{0}(1), \sigma_{0}(27) ##. But if my formulas were correct, then is there anything I need to fix in my previous, first proof for this problem? What would you add/fix anything to it?

Math100 said:
Never mind, I found out how to find those ## \sigma_{0}(1), \sigma_{0}(27) ##. But if my formulas were correct, then is there anything I need to fix in my previous, first proof for this problem? What would you add/fix anything to it?
I haven't understood a word of your proof. What are ##u## and ##N## in case of ##n=27##?

fresh_42 said:
I haven't understood a word of your proof. What are ##u## and ##N## in case of ##n=27##?
I think I should have included/added a definition of the Dirichlet product.

fresh_42 said:
I haven't understood a word of your proof. What are ##u## and ##N## in case of ##n=27##?
I am not sure. What should ## u, N ## be? Because I think ## u, N ## are arithmetical functions and we write ## (u\cdot N)(n) ## for ## \sum_{d\mid n}\sigma_{1}(d)\sigma_{1}(\frac{n}{d}) ##.

## \sigma_{\alpha}=u\cdot N^{\alpha} ## and ## N=\phi\cdot u ##
From above, how should I find ## u, N ##?

Let us see whether the case that ##n## is square-free is easier. Square-free means that all primes occur only once in the factorization of ##n.##

Let ##n=p_1\cdot\ldots\cdot p_r.## Then
\begin{align*}
\sum_{d|n}\sigma_1(d)\sigma_1(n/d)&=2 \sigma_1(n) +\sum_{i=1}^r (p_i+1)\cdot \prod_{j\neq i} (p_j+1)=(2+r)\prod_{j=1}^r(p_j+1)\\
\sum_{d|n}d\sigma_0(d)\sigma_0(n/d)&= (1+n)\cdot 2^r +\sum_{i=1}^r p_i \cdot 2\cdot \prod_{j\neq i} 2= 2^r\left(1+n+\sum_{i=1}^r p_i\right)
\end{align*}
Applied to ##n=3\cdot 5=15## we get
\begin{align*}
\sum_{d|n}\sigma_1(d)\sigma_1(n/d)&=\sigma_1(1)\sigma_1(15)+\sigma_1(3)\sigma_1(5)+\sigma_1(5)\sigma_1(3)+\sigma_1(15)\sigma_1(1)\\
&=2\cdot 24 +2\cdot 4\cdot 6=96\\
\sum_{d|n}d\sigma_0(d)\sigma_0(n/d)&=\sigma_0(1)\sigma_0(15)+3\cdot \sigma_0(3)\sigma_0(5)+5\cdot \sigma_0(5)\sigma_0(3)+15\sigma_0(15)\sigma_0(1)\\
&=16\cdot 4+ 8\cdot 2 \cdot 2 =96
\end{align*}

If I look at the fact that the summands are so different, then it is hard to see a smart proof without additional formulas. I assume they are behind those ##u## and ##N## functions that I do not know.

Last edited:
fresh_42 said:
Let us see whether the case that ##n## is square-free is easier. Square-free means that all primes occur only once in the factorization of ##n.##

Let ##n=p_1\cdot\ldots\cdot p_r.## Then
\begin{align*}
\sum_{d|n}\sigma_1(d)\sigma_1(n/d)&=2 \sigma_1(n) +\sum_{i=1}^r (p_i+1)\cdot \prod_{j\neq i} (p_j+1)=(2+r)\prod_{j=1}^r(p_j+1)\\
\sum_{d|n}d\sigma_0(d)\sigma_0(n/d)&= (1+n)\cdot 2^r +\sum_{i=1}^r p_i \cdot 2\cdot \prod_{j\neq i} 2= 2^r\left(1+n+\sum_{i=1}^r p_i\right)
\end{align*}
Applied to ##n=3\cdot 5=15## we get
\begin{align*}
\sum_{d|n}\sigma_1(d)\sigma_1(n/d)&=\sigma_1(1)\sigma_1(15)+\sigma_1(3)\sigma_1(5)+\sigma_1(5)\sigma_1(3)+\sigma_1(15)\sigma_1(1)\\
&=2\cdot 24 +2\cdot 4\cdot 6=96\\
\sum_{d|n}d\sigma_0(d)\sigma_0(n/d)&=\sigma_0(1)\sigma_0(15)+3\cdot \sigma_0(3)\sigma_0(5)+5\cdot \sigma_0(5)\sigma_0(3)+15\sigma_0(15)\sigma_0(1)\\
&=16\cdot 4+ 8\cdot 2 \cdot 2 =96
\end{align*}

If I look at the fact that the summands are so different, then it is hard to see a smart proof without additional formulas. I assume they are behind those ##u## and ##N## functions that I do not know.
How about ## \sigma_{1}\cdot \sigma_{1}=N\sigma_{0}\cdot \sigma_{0} ## where
## \sigma_{1}=N\cdot u ## and ## \sigma_{0}=u\cdot u ##?
Thus
\begin{align*}
&\sigma_{1}\cdot \sigma_{1}=(N\cdot u)\cdot (N\cdot u)\\
&\sigma_{1}\cdot \sigma_{1}=(u\cdot N)\cdot (N\cdot u)\\
&\sigma_{1}\cdot \sigma_{1}=u\cdot (N\cdot N)\cdot u\\
&\sigma_{1}\cdot \sigma_{1}=u\cdot N\sigma_{0}\cdot u\\
&\sigma_{1}\cdot \sigma_{1}=N\sigma_{0}\cdot (u\cdot u)=N\sigma_{0}\cdot \sigma_{0}\\
\end{align*}
where ## N\cdot N=\sum_{d\mid n}d\cdot \frac{n}{d}=n\sum_{d\mid n}1=N\sigma_{0} ##.

If this works, then how should I proceed from here and prove that they're equal?

Math100 said:
How about ## \sigma_{1}\cdot \sigma_{1}=N\sigma_{0}\cdot \sigma_{0} ## where
## \sigma_{1}=N\cdot u ## and ## \sigma_{0}=u\cdot u ##?
Thus
\begin{align*}
&\sigma_{1}\cdot \sigma_{1}=(N\cdot u)\cdot (N\cdot u)\\
&\sigma_{1}\cdot \sigma_{1}=(u\cdot N)\cdot (N\cdot u)\\
&\sigma_{1}\cdot \sigma_{1}=u\cdot (N\cdot N)\cdot u\\
&\sigma_{1}\cdot \sigma_{1}=u\cdot N\sigma_{0}\cdot u\\
&\sigma_{1}\cdot \sigma_{1}=N\sigma_{0}\cdot (u\cdot u)=N\sigma_{0}\cdot \sigma_{0}\\
\end{align*}
where ## N\cdot N=\sum_{d\mid n}d\cdot \frac{n}{d}=n\sum_{d\mid n}1=N\sigma_{0} ##.

If this works, then how should I proceed from here and prove that they're equal?
I still have no idea what that should mean.

Math100 said:
How about ## \sigma_{1}\cdot \sigma_{1}=N\sigma_{0}\cdot \sigma_{0} ## where
## \sigma_{1}=N\cdot u ## and ## \sigma_{0}=u\cdot u ##?
Thus
\begin{align*}
&\sigma_{1}\cdot \sigma_{1}=(N\cdot u)\cdot (N\cdot u)\\
&\sigma_{1}\cdot \sigma_{1}=(u\cdot N)\cdot (N\cdot u)\\
&\sigma_{1}\cdot \sigma_{1}=u\cdot (N\cdot N)\cdot u\\
&\sigma_{1}\cdot \sigma_{1}=u\cdot N\sigma_{0}\cdot u\\
&\sigma_{1}\cdot \sigma_{1}=N\sigma_{0}\cdot (u\cdot u)=N\sigma_{0}\cdot \sigma_{0}\\
\end{align*}
where ## N\cdot N=\sum_{d\mid n}d\cdot \frac{n}{d}=n\sum_{d\mid n}1=N\sigma_{0} ##.
The above should be ##(N \cdot N)(n) = \ldots = (N\sigma_0)(n)##. (why?)
Math100 said:
If this works, then how should I proceed from here and prove that they're equal?
I think this is a right idea but there is a lot being used without explicit mention, which i think maybe makes it hard to follow. Somewhere we might mention "We will write the Dirichlet product of two arithmetic functions ##f, g## as ##f \cdot g##" (i would use ##\ast## instead of ##\cdot## but just my opinion). Otherwise, how will the reader know? Some other things that might also add clarity:

-Give the definition of Dirichlet product
-State its properties: is it associative? commutative?
-Explicitly define ##u,N,\sigma_k##, e.g., "We define the functions ##u(n) = 1## for all ##n## and ##N(n) = n## for all ##n## and etc..."
-Give an explanation why we have ##\sigma_1=N\cdot u## and ##\sigma_0 = u\cdot u##, even if the explanation is just "From the textbook we know...". At least for me, it was hard to see why those two equations are true...

Some of this could be put in the "Relevant equations" part of the homework template (for future reference). To your last question, you've shown ##\sigma_1\cdot\sigma_1 = (N\sigma_0)\cdot\sigma_0##. Are we done?To build off of fresh's suggestion, if ##f, g## are multiplicative, then their Dirichlet product is multiplicative. So i think another solution would be to prove the equation holds for prime powers (as fresh suggested).

Last edited:

## What is the purpose of the sum in the formula?

The sum in the formula is used to calculate the sum of the divisors of a given number n, multiplied by the sum of the divisors of its factors. This formula is also known as the sum of divisors function.

## What is the significance of the sigma notation in the formula?

The sigma notation represents the sum over all divisors of a given number n. It allows for a concise and efficient way to represent the sum of divisors function.

## How is this formula related to number theory?

This formula is closely related to number theory, specifically the study of divisors and their properties. It is often used in the study of perfect numbers, which are numbers that are equal to the sum of their proper divisors.

## Can this formula be used to prove the existence of perfect numbers?

No, this formula alone cannot prove the existence of perfect numbers. It is only one tool among many that can be used to study perfect numbers, but it is not sufficient on its own to prove their existence.

## Are there any practical applications of this formula?

While this formula may not have direct practical applications, it is a useful tool in the study of number theory and can be used to prove various theorems and properties related to divisors and perfect numbers. It also has applications in cryptography and coding theory.

Replies
8
Views
902
Replies
5
Views
898
Replies
7
Views
1K
Replies
14
Views
1K
Replies
5
Views
988
Replies
4
Views
1K
Replies
19
Views
920
Replies
9
Views
607
Replies
2
Views
1K
Replies
3
Views
1K