Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Question:

Show that if $n$ is a positive integer such that $24$ divides into $n + 1$, then $24$ divides the sum of all divisors of $n$ (denoted in number theory by $\sigma_0(n)$).

For example if $n = 95$, then $n + 1 = 96 = 4 \times 24$ and the sum of the divisors of $n$ is $$1 + 5 + 19 + 95 = 120 = 5 \times 24.$$ (Note that the number $n$ is included among its divisors.)

share|improve this question
    
"Q1:" suggests that this is probably the first question from a homework. If yes, please add the [homework] tag. –  Srivatsan Jan 31 '12 at 3:02
    
Also see: What is so special about the divisors of 24? –  anon Jan 31 '12 at 4:39

2 Answers 2

We use a pairing argument, working first modulo $3$ and then modulo $8$.

We are told that $n\equiv -1\pmod{24}$. It follows that $n\equiv -1\pmod{3}$. Split the set of divisors of $n$ into unordered pairs $\{a,b\}$ such that $ab=n$. (Since $n\equiv -1\pmod n$, the number $n$ is not a perfect square, so every divisor of $n$ is taken care of.)

For any pair $\{a,b\}$ with $ab=n$, one of $a$ and $b$ is congruent to $1$ modulo $3$, and the other is congruent to $-1$. So all pair sums are congruent to $0$. Therefore the sum of all pair sums, that is, the sum of the divisors, is congruent to $0$ modulo $3$.

The same idea works modulo $8$. We are told that $n\equiv -1\pmod{8}$. If $\{a,b\}$ is an unordered pair with $ab=n$, then either (i) One of $a$ and $b$ is congruent to $1$ modulo $8$, and the other is congruent to $-1$, or (ii) One of $a$ and $b$ is congruent to $3$ modulo $8$, and the other is congruent to $-3$. In either case the sum is congruent to $0$ modulo $8$.

Thus the sum of the divisors of $n$ is divisible by $3$ and by $8$, and therefore by $24$.

share|improve this answer
1  
You have to show that $n$ can't be a square, so that $a,b$ are distinct if $ab=n$. Also, you write $n\equiv 1$ when you mean $n\equiv -1$ at the beginning of your answer. –  Thomas Andrews Jan 28 '12 at 21:58
    
@Thomas Andrews: Thanks for finding the potentially very confusing typo. I had remarked that nothing can be paired with itself because of the $\equiv -1\pmod{3}$ condition. That was insufficiently precise, so the parenthetical remark has been changed to "because $n\equiv -1 \pmod{3}$, $n$ cannot be a perfect square." Thanks for suggesting the improvement. –  André Nicolas Jan 28 '12 at 22:11

We're looking for divisors $a, b$ such that $a \times b = n \equiv - 1 \pmod{24}$. In order for this to be possible, $a$ and $b$ must both be coprime to 24. Now note the following:

$a \times b \equiv -1 \pmod{24}$

$a^2 + a \times b \equiv a^2 -1 \pmod{24}$

$a(a + b) \equiv (a-1)(a+1) \pmod{24}$

Since $a$ is coprime to 24, and thus $a$ is odd, $(a-1), (a+1)$ must be even numbers. Furthermore, they are consecutive even numbers and thus at least one of them is also divisible by 4. In addition, as $a$ is coprime to 24, one of $(a-1), (a+1)$ must be divisible by 3 because if $a \equiv 1 \pmod{3}$ then $3|(a-1)$ and if $a \equiv 2 \mod{3}$ then $3|(a+1)$. This means that $4 \times 2 \times 3 = 24 | (a+1)(a-1)$. As $a$ is coprime to 24, this implies that $(a + b) \equiv 0 \pmod{24}$ for all $a, b$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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