Main Question or Discussion Point
I've been trying to improve my problem solving skills by doing some puzzles at this site, mathchallenge.net, and I don't understand the problem or solution to this one:
The divisors of a natural number, excluding the number itself, are called the proper divisors . If the sum of proper divisors is equal to the number we call the number perfect. For example, the divisors of 28 are 1, 2, 4, 7, 14, and 28, so the sum of proper divisors is 1 + 2 + 4 + 7 + 14 = 28.
Similarly, if the sum of the proper divisors exceeds the number we call the number abundant. For example, 12 is abundant because the divisors of 12 are 1, 2, 3, 4, 6 12, and the sum of proper divisors 1 + 2 + 3 + 4 + 6 = 14 greater than 12.
By first showing that 315p is abundant for all primes, p less than or equal 103, prove that all integers greater than 28123 can be written as the sum of two abundant numbers.
I don't understand the cases for 315p, p less than or equal to 103, that the solution lays out.Solution
Let S(n) represent the sum of proper divisors of n.
S(315) = S(32times5times7) = 1 + 3 + 5 + 7 + 9 + 15 + 21 + 35 + 45 + 63 + 105 = 309.
When considering S(315p) we must deal with two cases.
Case 1: p is coprime with 315 (p not equal 3, 5, 7)
therefore S(315p) = p(1 + 3 + ... + 105) + (1 + 3 + ... + 105) + 315 = 309p + 624
For 315p to be abundant, 315p less than 309p + 624 implies p less than 104.
Case 2: p = 3, 5, 7
S(315p) = p(1 + 3 + ... + 105) + 1 + 315 + q, where q is 5 + 7, 3 + 7, or 3 + 5 as p = 3, 5, or 7 respectively.
However for 315p to be abundant it is sufficient to show 315p less than 309p + 316 implies 6p less than 316, which is clearly true for p = 3, 5, 7.
Hence 315p is abundant for all primes, p less than or equal 103.
It can be shown that multiples of abundant numbers are also abundant (see Even Sum Of Two Abundant Numbers). Thus all values of m from 2 to 103 will either be prime or contain a prime in that domain. So although 315 is deficient, 315m is guaranteed to be abundant for 2 less than or equal m less than or equal 103.
We now search for the smallest abundant number that is coprime with 315. Considering numbers of the form 2ktimes11 we find that 88 is the smallest such example. Therefore the expression 315a + 88b will be the sum of two abundant numbers for 2 less than or equal a less than or equal 103 and b greater than or equal 1.
Clearly the expression produces integers congruent with 315a mod 88, and although 0 less than or equal a less than or equal 87 will produce all possible congruences we require a greater than or equal 2 to ensure 315a is abundant; that is, 2 less than or equal a less than or equal 89 will produce all possible congruences.
It is necessary to have at least one multiple of 88, so 315times89 + 88 represents that last integer before the congruences repeat. Hence every integer n greater than 315times89 + 88 = 28123 can be written in the form 315a + 88b, which will be the sum of two abundant numbers. Q.E.D.