Maths Olympiad Prep

Library / /79 of 520

Number theory Difficulty 6.4 National olympiad Prove it

A perfect number, greater than 66, is divisible by 33. Prove that it is also divisible by 99.

Solution

1. **Lemma: If n n is a perfect number, then mn mn , where m>1 m > 1 , is not a perfect number.

Proof of Lemma:**
Let d1,d2,,dk d_1, d_2, \ldots, d_k be the proper divisors of n n such that d1+d2++dk=n d_1 + d_2 + \ldots + d_k = n . Then, for mn mn , the proper divisors are md1,md2,,mdk md_1, md_2, \ldots, md_k and possibly other divisors. Note that mdi md_i for 1ik 1 \le i \le k are distinct divisors of mn mn and 1<mdi<mn 1 < md_i < mn . If mn mn were a perfect number, we would have:
mn=1+md1+md2++mdk mn = 1 + md_1 + md_2 + \ldots + md_k
However, this implies:
mn1+mn mn \ge 1 + mn
which is a contradiction. Hence, mn mn is not a perfect number. \blacksquare

2. Observation:
The number 6 6 is a perfect number because 6=1+2+3 6 = 1 + 2 + 3 .

3. Assumption:
Assume there is a perfect number n n greater than 6 6 that is divisible by 3 3 but not by 9 9 . Let n=3k n = 3k .

4. Sum of Divisors Function:
Let f(m) f(m) be the sum of the divisors of a number m m . Note that f f is multiplicative, so:
f(n)=f(3k)=f(3)f(k) f(n) = f(3k) = f(3)f(k)
Since the sum of the divisors of 3 3 is 1+3=4 1 + 3 = 4 , we have:
f(n)=4f(k) f(n) = 4f(k)

5. Perfect Number Condition:
For n n to be a perfect number, the sum of its proper divisors must equal n n . Therefore:
n=f(n)n n = f(n) - n
Substituting f(n)=4f(k) f(n) = 4f(k) into the equation, we get:
n=4f(k)n n = 4f(k) - n
Solving for n n , we have:
2n=4f(k)    n=2f(k) 2n = 4f(k) \implies n = 2f(k)
This implies that 2 2 divides n n , and since n=3k n = 3k , 6 6 must divide n n .

6. Contradiction:
By the lemma, n n cannot be a perfect number if it is of the form 3k 3k and not divisible by 9 9 . This leads to a contradiction.

Therefore, n n must be divisible by 9 9 .

\blacksquare

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.