Show that 3 divides $\sigma(3n+2)$

I would like to show that for any integer $n \geq 0$, $3|\sigma(3n+2)$, where $\sigma(n)$ denotes the sum-of-divisors function.

I have been able to show some results, for example that if $(3n+2)$ has a prime factor of the form $6k-1$ which occurs with an odd exponent, then $3|\sigma(3n+2)$. However, this leaves some other cases too, and it seems like my approach is not the best.

Any suggestions?

• If $k \equiv 2 \pmod{3}$, then $k$ has at least one prime factor $p \equiv 2 \pmod{3}$ that divides $k$ with an odd power. – Daniel Fischer Aug 18 '13 at 21:33
• @DanielFischer: Thanks for your comment! It should say "a prime factor of the form 6k-1". – Alexandre Vandermonde Aug 18 '13 at 21:45
• That isn't necessarily the case, $2$ is also a possibility. – Daniel Fischer Aug 18 '13 at 21:46
• To unravel Daniel's first comment: the fact that $m\equiv 2$ mod $3$ necessarily implies there is a prime $p$ with $p\equiv2$ mod $3$ whose exponent in $m$ is odd. You can prove this by contradiction $-$ show that on the contrary assumption (all prime divisors $p\equiv-1$ have even exponent) $m$ must be $0$ or $1$ mod $3$. – anon Aug 18 '13 at 21:56
• Thank you for clearing this up! I realize now that it suffices to consider the primes on the form $3k \pm 1$ and use the same technique as I used for the special case. – Alexandre Vandermonde Aug 18 '13 at 22:00

Briefly: $$2\sigma(3n+2) = \sum_{d\mid 3n+2} d + \sum_{d\mid 3n+2}\frac{3n+2}{d}= \sum_{d\mid 3n+2} \left(d+\frac{3n+2}{d}\right)$$

And just show that all the terms of this sum are divisible by $3$.

• I should stop trying to write LaTeX from my iPad. – Thomas Andrews Aug 18 '13 at 21:57
• Looks great now! Thanks for the hint, it is very neat. – Alexandre Vandermonde Aug 18 '13 at 22:11
• Why all the terms of this sum are divisible by 3 ? – Pranasas Dec 18 '14 at 18:36
• Because if $d\equiv 1\pmod 3$ then $\frac{3n+2}{d}\equiv 2\pmod 3$ and visa versa. @Pranasas – Thomas Andrews Dec 18 '14 at 18:38
• Because $d\frac{3n+2}{d}=3n+2\equiv 2\pmod 3$, so if $d\equiv 1\pmod 3$... @Dominik – Thomas Andrews Jun 22 '15 at 18:44

Hint: Consider all pairs of numbers such that $a\times b = n$. Show that $3 \mid a+b$.

Hint: There is a 'special case' that you have to check for completeness. Use the fact that 2 is not a quadratic residue modulo 3.

• What is this special case? With Thomas' motivation for your first hint, it seems to me that the method works for all $n \geq 0$. – Alexandre Vandermonde Aug 18 '13 at 22:09
• @AlexandreVandermonde The special case is to check when $a=b$. But we can't have $a^2 = 3k+2$. – Calvin Lin Aug 18 '13 at 22:14
• I'm sorry, but I still fail to see why Thomas' formula below would not be correct in the case $a=b$ (that is, $d=\sqrt{3n+2}$, right?). We still want to add one term for each of the sums in the middle equation. – Alexandre Vandermonde Aug 18 '13 at 22:22
• @AlexandreVandermonde Thomas' solution is correct. He does work around the case of $a^2 = 3n+2$, by doing the counting twice. So he did account for it (though not explicitly). – Calvin Lin Aug 18 '13 at 22:27
• Alright, thanks for clearing that up! – Alexandre Vandermonde Aug 18 '13 at 22:30