# Prove that ## 4\mid \sigma_{1}(4k+3) ##

• Math100
In summary: And while we are at it: I think you mean ##\forall## when you write ##\forall##. I am not sure if you are supposed to explain why ##p_1=3## is the right choice. I guess it is clear to you that the product of the ##p_i^{k_i}## is not divisible by ##4## so that at least one of the factors is not divisible by ##4##. This is what I used to set ##p_1## to a factor that is not divisible by ##4. If it were divisible by ##4## then the product would be divisible by ##4##. But maybe this is too much reading between the lines. I hope you are fine with

#### Math100

Homework Statement
Prove that ## 4\mid \sigma_{1}(4k+3) ## for each positive integer ## k ##.
Relevant Equations
None.
Proof:

Suppose ## a=4k+3 ## for some ## k\in\mathbb{Z^{+}} ##.
Then ## a=p_{1}^{k_{1}}p_{2}^{k_{2}}\dotsb p_{r}^{k_{r}}\implies 4k+3=p_{1}^{k_{1}}p_{2}^{k_{2}}\dotsb p_{r}^{k_{r}} ##.
Observe that ## \sigma_{1}(4k+3)=\sigma (p_{1}^{k_{1}})\sigma (p_{2}^{k_{2}})\dotsb \sigma (p_{r}^{k_{r}} ##.
Thus
\begin{align*}
&\sigma_{1} (p_{i}^{k_{i}})=1+p_{i}+p_{i}^2+\dotsb +p_{i}^{k_{i}}\\
&\equiv (1+3+3^{2}+\dotsb +3^{k_{i}})\pmod {4}\\
&\equiv (1-1+1-1+\dotsb +1-1)\pmod {4}\\
&\equiv 0\pmod {4}.\\
\end{align*}
Therefore, ## 4\mid \sigma_{1}(4k+3) ## for each positive integer ## k ##.

I don't think this is correct.

We have
$$\sigma_1(a)=\sigma_1(4k+3)=\sigma_1\left(\prod_{i=1}^r p_i^{k_i}\right)=\prod_{i=1}^r\dfrac{p_i^{k_i+1}-1}{p_i-1} =\prod_{i=1}^r \left(p_i^{k_i}+\ldots+p_i+1\right)$$

If ##[a]_4## notes the equivalence class of an integer ##a \pmod{4}## then how do we know that ##\sigma_1([a]_4)=[\sigma_1(a)]_4.## It seems as if you would use this. It is wrong. E.g. ##0=\sigma_1([8]_4)\neq [\sigma_1(8)]_4=1+2+4+8=3.## I am not sure if you use it since the intermediate steps are missing.

Another point is: How do you know that the number of ##-1##s and the number of ##+1##s are equal? What if ##k_i## is even?

I think I know what you tried to do.

From ##a=4k+3=p_1^{k_1}\cdot\ldots\cdot p_r^{k_r}## we get
\begin{align*}
[3]_4= [p_1]_4^{k_1}\cdot\ldots\cdot [p_r]_4^{k_r}
\end{align*}
where ##m:=[n]_4## is the abbreviation of ##n \equiv m \in \{0,1,2,3\}\pmod{4}.##

Now we have to examine the right-hand side.
All ##[p_i]_4 \neq 0.## Powers of ##[p_i]_4=2## result in ##0## or ##2## so that they cannot occur since we have only ##[3]_4 ## on the left. All ##[p_i]_4=1## are of no interest since they do not change the product. From the left-hand side we know, that at least one ##[p_i]_4=3## has to occur, say it is ##p_1.## But ##[3]_4\cdot [3]_4=[1]_4## and we need a ##[3]_4.## This means that ##k_1## has to be odd, for otherwise, we would end up with ##[1]_4.## In case ##k_1## is indeed even, then there has to be another index ##j## with ##[p_j]_4=[3]_4## and ##k_j## odd. In such a case we would choose ##j## as our first prime. Say ##k_1=2l_1+1.##

Therefore, we can assume that ##[p_1^{k_1}]_4=[3]_4^{2l_1+1}##. Now
\begin{align*}
\sigma_1([a]_4)&\equiv \prod_{i=1}^r \sigma_1([p_i]_4)^{k_i} \equiv \sigma_1([3^{2l_1+1}]_4) \prod_{i=2}^r \sigma_1([p_i]_4)^{k_i}\\
&\equiv \dfrac{3^{2l_1+2}-1}{3-1}\prod_{i=^2}^r \sigma_1([p_i]_4)^{k_i} \\
&\equiv \dfrac{9^m-1}{2}\prod_{i=^2}^r \sigma_1([p_i]_4)^{k_i} \\
&\equiv 0\pmod{4}
\end{align*}

with ##m=l_1+1\geq 1## and ##9^m-1 \equiv 0\pmod{8},## hence ##\dfrac{9^m-1}{2}\equiv 0\pmod{4}.##

You have to explain why you may assume ##p_1=3,## which by the way is wrong. We can only assume that ##[p_1]_4\equiv [3]_4.##

And make sure that you first pass the entire formula modulo four, and then apply ##\sigma_1.##

Last edited:
The most important question when I read a proof, and therefore the most important question when you write a proof, is WHY. I ask this from line to line. If anybody is asking you this, you should be able to answer. In the best case, it is already written in the proof.

Okay, so I revised this proof:

Let ## 4k+3=p_{1}^{k_1}p_{2}^{k_2}\dotsb p_{s}^{k_s} ##.
Then ## 4\equiv 0\pmod {4} ## and ## 4k+3\equiv 3\pmod {4} ##.
Thus ## p_{i}^{k_{i}}\not\equiv 0\pmod {4} ## for ## i=1, 2,..., s ##.
Suppose all ## p_{i}^{k_{i}}\equiv 1\pmod {4} ##.
Then ## p_{1}^{k_{1}}p_{2}^{k_{2}}\dotsb p_{s}^{k_{s}}\equiv 1\pmod {4} ##.
Since ## p_{1}^{k_{1}}p_{2}^{k_{2}}\dotsb p_{s}^{k_{s}}\equiv 3\pmod {4} ##,
it follows that ## \exists ## one ## p_{i} ## satisfying ## p_{i}^{k_{i}}\equiv 3\pmod {4} ##.
This means ## p_{i}\equiv 3\pmod {4} ##.
Observe that ## p_{i}^{2}\equiv 9\equiv 1\pmod {4} ## and ## p_{i}^{3}\equiv 3\pmod {4} ##.
If ## p_{i}^{r}\equiv 3\pmod {4} ##, then ## r ## must be odd.
This implies ## p_{i}^{k_{i}}\equiv 3\pmod {4} ## where ## k_{i} ## is odd.
Now we have
\begin{align*}
&\sigma_{1}(p_{i}^{k_{i}})=p_{i}^{k_{i}}+p_{i}^{k_{i}-1}+\dotsb +p_{i}+1\\
&\equiv (3+1+\dotsb +3+1)\pmod {4}\\
&\equiv 0\pmod {4},\\
\end{align*}
because ## p_{i}^{r}\equiv 3\pmod {4} ## if ## r ## is odd and ## p_{i}^{r}\equiv 1\pmod {4} ## if ## r ## is even.
Thus
\begin{align*}
4\mid \sigma_{1}(p_{i}^{k_{i}} ) & \implies 4\mid \sigma (p_{1}^{k_{1}} )\dotsb \sigma_{1} (p_{i}^{k_{i}})\dotsb \sigma_{1} ( p_{s}^{k_{s}} ) \\
&\implies4\mid \sigma_{1} (p_{1}^{k_{1}}p_{2}^{k_{2}}\dotsb p_{s}^{k_{s}}).\\
\end{align*}
Therefore, ## 4\mid \sigma_{1} (4k+3) ## for each positive integer ## k ##.

Last edited by a moderator:
fresh_42
Correct.

I edited the typos. If you add one # too many or set one bracket wrong, then it doesn't render properly. It's sometimes hard to find if formulas got lengthy.

Math100