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

This question has an open bounty worth +50 reputation from Joe Goldiamond ending in 16 hours.

Looking for an answer drawing from credible and/or official sources.

  • 4
    Hint: every divisor is either 1 or 3 mod 4, and you can pair them up... – user10354138 Dec 1 at 12:53
up vote 2 down vote accepted

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

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.. – Joe Goldiamond Dec 1 at 13:39
  • It might be a little better to avoid using $p,q$ to denote divisors that are not necessarily prime :). – Erick Wong Dec 3 at 19:51

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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.