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

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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$.

Answer 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$.

Answer 5

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.