# Prove that $4| \sigma(4k+3)$ for each positive integer $k$

I am struggling with a part of Apostol concerning divisor functions of $$\sigma_\alpha(n)$$, when $$\alpha =1$$, this denotes the sum of divisors of $$n$$

I wish to prove that $$4| \sigma(4k+3)$$ for each positive integer $$k$$

I started: Since $$\alpha$$ is multiplicative we have: $$\alpha(p_1^{a_1}...p_k^{a_k}) = \sigma(p_1^{a_1})... \sigma(p_k^{a_k})$$

The divisors of a prime power $$p^a$$ are: $$1,p, p^2,...p^a$$

This is a geometric series: Hence: $$\sigma(p^a) = \frac{p^{a+1}-1}{p-1}$$

But I guess I started the wrong way.... Any help appreciated

• Hint: every divisor is either 1 or 3 mod 4, and you can pair them up... Commented Dec 1, 2018 at 12:53

Suppose $$4k+3=p^{\alpha}$$, where $$p$$ is a prime. Then $$p \equiv 3 \mod 4$$ (otherwise $$p^{\alpha}\equiv 1\mod 4$$). Thus, $$3\equiv p^{\alpha}\equiv 3^{\alpha} \mod 4 \Longrightarrow \alpha$$ is odd. Thus, $$\sigma(p^{\alpha})= 1+p+p^2+...+p^{\alpha}\equiv 1+3+3^2+...+3^{\alpha}\equiv 1+(-1)+(-1)^2+...+(-1)^{\alpha}\mod 4$$ Since $$\alpha$$ is odd, the above sum is $$0$$.

Now if $$n=4k+3$$ is not a prime power, then it can be written as a product of prime powers. Since $$n\equiv 3\mod 4$$, atleast one of the prime powers must be $$3\mod 4$$, and since $$\sigma$$ is multiplicative the result follows.

This is a repeat of Oscar Lanzi's answer but with more words and an example.

If $$d$$ divides $$4k+3$$ then $$dq=4k+3$$ but then $$d$$ has a remainder of $$0,1,2,3$$ after we divide by $$4$$ and actually we can rule out $$0,2$$ because otherwise $$4k+3$$ would be even. Then if $$d$$ is congruent to $$1 \mod 4$$ then $$q$$ must be congruent to $$3 \mod 4$$. This is because $$1\times 3 =3$$ and $$dq=3 \mod 4$$. Note then that $$d+q \mod 4=0$$. Likewise, if $$d\equiv 1 \mod 4\implies q \equiv 3 \mod 4$$.

This is true for every divisor of $$4k+3$$ so like it says in the comments: We can pair them up!

Let's take $$63$$ as an example.

$$63=1 \times 63$$ and $$1+63$$ is a multiple of $$4$$ because $$1$$ is one more than a multiple of $$4$$ and 63 is $$3$$ more than a multiple of $$4$$.

$$63=3 \times 21$$ and $$3+21$$ is a multiple of $$4$$ because $$21$$ is one more than a multiple of $$4$$ and $$3$$ is $$3$$ more than a multiple of $$4$$.

$$63=7 \times 9$$ and $$7+9$$ is a multiple of $$4$$ because $$9$$ is one more than a multiple of $$4$$ and $$7$$ is $$3$$ more than a multiple of $$4$$.

You are good so far.

Notice that $$4k+3$$ is odd number, so none of $$p_i$$s will be $$2$$.

Also, if all of $$p_i^{a_i}$$ satisfies $$p_i^{a_i} \equiv 1\pmod 4$$, then their product will be also $$1$$ modulo $$4$$. Therefore, there exists $$i$$ satisfying $$p_i^{a_i} \equiv 3\pmod 4$$. Let's say $$p_k^{a_k} \equiv 3\pmod 4$$.

If $$p_k \equiv 1\pmod 4$$, then $$p_k^n \equiv 1\pmod 4$$ for all positive integer $$n$$. Therefore $$p_k \equiv 3\pmod 4$$.

Since $$p_k^{a_k} \equiv 3\pmod 4$$, $$a_k$$ must be odd number. In other words, $$p_k^{a_k+1}$$ is square of odd number. Therefore $$p_k^{a_k+1} \equiv 1\pmod 8$$.

Now, $$p_k-1 \equiv 2\pmod 4$$ and $$p_k^{a_k+1}-1 \equiv 0\pmod 8$$. It follows that $$\sigma(p^k) = \frac{p^{k+1}-1}{p-1}$$ is multiple of $$4$$.

This may be (definitely is) overkill and not what you're looking for, but we can actually prove a more general and much more interesting theorem:

If $$n\in\mathbb N$$ cannot be expressed as a sum of two squares (that is, if the diophantine equation $$a^2+b^2=n$$ has no integer solutions), then $$4|\sigma(n).$$

The proof contains a bit of machinery with which you are not familiar; if so, this answer will serve mainly to amuse other observers of this question.

Proof: Define the function $$f:\mathbb N\mapsto \{0,1\}$$ as evaluating to $$1$$ if its argument is a sum of two squares and evaluating to $$0$$ if its argument cannot be written as a sum of two squares. It is a well-known fact in number theory that this function is multiplicative (though I will not provide proof of this unless it is specifically requested, as it requires a lengthy dive into the Gaussian Integers). Thus, if $$n$$ cannot be written as a sum of squares, then $$f(n)=0$$. If we expand $$n$$ into its prime factorization $$n=p_1^{m_1}...p_k^{m_k}$$ we may see that $$f(n)=f(p_1^{m_1}...p_k^{m_k})=f(p_1^{m_1})...f(p_k^{m_k})=0$$ from which it follows that $$f(p^m)=0$$ for some $$p^m$$ in the prime factorization of $$n$$. Then, we clearly have that $$m$$ is odd, since if this were not the case, $$p^m=(p^{m/2})^2+0^2$$ could be written as a sum of two squares. Using another theorem from number theory, which states that any prime congruent to $$1$$ modulo $$4$$ is a sum of two squares, we have that $$p\equiv 3\pmod 4$$. Thus, \begin{align}\sigma(p^m) &=p^m+p^{m-1}+...+p+1\\ &\equiv 3+1+...+3+1\\ &\equiv 4+...+4\\ &\equiv 0\bmod 4 \end{align} and so $$4|\sigma(p^m)$$. From the multiplicativity of $$\sigma$$, it follows that $$4|\sigma(n)$$. $$\blacksquare$$

Your exercise is a direct corollary of this much more difficult theorem; it is easy to see that any number in the form $$4k+3$$ is not a sum of two squares, so we have that $$4|\sigma(4k+3)$$.

There exists an interesting analogue of this theorem regarding divisibility by $$3$$ rather than by $$4$$, but I will not prove it here:

If $$n\in\mathbb N$$ is such that the diophantine equation $$a^2+ab+b^2=n$$ has no integer solutions, then $$3|\sigma(n)$$.

This tantalizing result requires the use of the Eisenstein Integers $$\mathbb Z[e^{2\pi i/3}]$$ rather than the Gaussian Integers.

Let $$4k+3=pq$$. Then the only way the product is $$\equiv 3\bmod 4$$ is if one factor is $$\equiv 3$$ and then other is $$\equiv 1$$. Add this pair of factors together, repeat to cover all factors.

• Thanks for the hint, but I am not getting there.. Commented Dec 1, 2018 at 13:39
• It might be a little better to avoid using $p,q$ to denote divisors that are not necessarily prime :). Commented Dec 3, 2018 at 19:51