Let . What is the ratio of the sum of the odd divisors of to the sum of the even divisors of ?
- A)
- B)
- C)
- D)
- E)
Answer
C
Key insight
Every even divisor is an odd divisor times 2, 4, or 8. So the even divisors add up to 2 + 4 + 8 = 14 times the odd ones.
Solution
Step 1: try a small example.
- Take . Its odd divisors are , with sum .
- Its even divisors are (the odd ones times ), (times ) and (times ). Their sum is .
- So for the ratio is . The pattern: every even divisor is an odd divisor times , or .
Step 2: count the 2s in .
4. Break each factor into primes: , , .
5. So has in it, and the rest is odd:
Step 3: add up the divisors.
6. The odd divisors of are exactly the divisors of . Call their sum .
7. Each even divisor of is one of these odd divisors times , or , and each such product is a different divisor. So the even divisors add up to
8. The ratio of odd to even is .
The answer is .
Why this works
Only the number of 2s in matters. Every divisor is "an odd part times a power of 2," so the divisors split into groups that are , , or times the odd ones. The big odd part never needs to be worked out. Next time a problem compares odd and even divisors, pull out the powers of 2 first.
The trap
Comparing the odd divisors with all the divisors (1 : 15) instead of with the even ones, or miscounting how many 2s are in N.
Concise solution
Factor: , , . So
Let be the odd part of , and let be the sum of all divisors of . The odd divisors of are exactly the divisors of , so their sum is .
Every even divisor of is with and a divisor of , and each such pair gives a different even divisor. Grouping by , the sum of the even divisors is
The ratio of odd sum to even sum is .
The answer is .
Review in the AoPS books
- Introduction to Number Theory, Chapter 1: Integers: The Basics (§1.4, §1.5)
- Introduction to Number Theory, Chapter 2: Primes and Composites
- Intermediate Counting & Probability, Chapter 4: Constructive Counting and 1-1 Correspondences (§4.4, §4.5, §4.6)
- Introduction to Number Theory, Chapter 5: Divisor Problems (§5.2, §5.3)
Techniques
Map the objects to something easier to count · Set up the equation/formula and compute; no special trick needed