Prove that for any positive integer n, 3 | σ(3n+2).?

Question

σ(n) is the summation of all divisors of n.

Answer 1

obviously 3n+2 is not divisible by 3. Also 3n+2 has at least one prime factor of form 3k+2, because otherwise multiplication of all of the prime factors will result in a number of form 3m+1 rather than 3n+2.

Furthermore, it is easy to show that the exponent of at least of prime q=3k+2 in the prime factorization of 3n+2 must be odd.

Let t be the exponent of such q. Using the expansion of  ÃƒÂÃ‚ƒ(3n+2) in terms of the prime factors of 3n+2 we can see that:

1+q+q^2+...+q^t |  ÃƒÂÃ‚ƒ(3n+2). Since t is odd, 3 | 1+q+q^2+...+q^t and problem is solved.

Answer 2

σ(3n + 2) = 1 + (3n + 2) + f_1 + f_2 + ... + f_(i - 1) + f_i

f_j represents a factor of 3n + 2

3n + 2 cannot be a perfect square, hence there is an even number of factors. i is thus even.

(f_1)(f_i) = 3n + 2

(f_2)(f_(i - 1)) = 3n + 2

...

...

...

None of these factors are multiples of 3.

This must mean, we have to show there are an equal number of factors of the form 3k + 1 and 3k + 2.

Assume f_1 is of the form 3k + 1.

(3k_1 + 1)(f_i) = 3n + 2

3(f_i)(k_1) + f_i = 3n + 2

At this point, we can see that f_i will HAVE to be 3n + 2. If otherwise, look at this:

3(f_i)(k_1) + 3k_i + 1 = 3n + 2

3((f_i)(k_1) + k_i) + 1 = 3n + 2

Clearly one leaves a remainder of 1 when divided by 3 and the other leaves a remainder of 2.

If f_1 is of the form 3k + 2, f_i will have to be of the form 3k + 1.

This fact is extended onto the other factors.

Hence, if two factors multiply to equal 3n + 2, one must be of the form 3k + 1 and its "partner" is of the form 3k + 2.

There are an equal number of 3k + 1 and 3k + 2 factors, hence σ(3n + 2) is divisible by 3.