Maths Olympiad Prep

Library / /3 of 20

Number theory Difficulty 6.3 National olympiad Find the answer

Prove: If the sum of all positive divisors of n Z\text{n Z} is a power of two, then the number/amount of the divisors is a power of two.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

To prove that if the sum of all positive divisors of nZ+ n \in \mathbb{Z}^{+} is a power of two, then the number of divisors of n n is also a power of two, we first introduce some notation and known results:

### Notation and Definitions

1. Let n n be a positive integer.
2. Denote the set of positive divisors of n n as {d1,d2,,dk} \{d_1, d_2, \ldots, d_k\} , where d1=1 d_1 = 1 and dk=n d_k = n .
3. The sum of all positive divisors of n n is given by:
σ(n)=i=1kdi. \sigma(n) = \sum_{i=1}^{k} d_i.

### Known Facts

- Prime Power Divisors: If n=p1a1p2a2pmam n = p_1^{a_1} p_2^{a_2} \ldots p_m^{a_m} is the prime factorization of n n , then the number of positive divisors of n n is:
k=(a1+1)(a2+1)(am+1). k = (a_1 + 1)(a_2 + 1) \ldots (a_m + 1).
- Sum of Divisors: The sum of the divisors for n n with the same prime factorization is:
σ(n)=(1+p1+p12++p1a1)(1+p2+p22++p2a2)(1+pm+pm2++pmam). \sigma(n) = (1 + p_1 + p_1^2 + \ldots + p_1^{a_1})(1 + p_2 + p_2^2 + \ldots + p_2^{a_2}) \ldots (1 + p_m + p_m^2 + \ldots + p_m^{a_m}).

### Proof

Given that σ(n)\sigma(n) is a power of two, let's denote it by 2b2^b, where bb is a non-negative integer.

For σ(n)\sigma(n) to be a power of two, each factor (1+pi+pi2++piai)(1 + p_i + p_i^2 + \ldots + p_i^{a_i}) must also be a power of two because if one factor is not a power of two, σ(n)\sigma(n) cannot be a power of two.

Let’s consider each factor of σ(n)\sigma(n):

- For a prime pip_i, 1+pi+pi2++piai1 + p_i + p_i^2 + \ldots + p_i^{a_i} being a power of two implies that the sequence (1,pi,pi2,,piai) (1, p_i, p_i^2, \ldots, p_i^{a_i}) must sum to a power of two.

- This can happen when ai=1a_i = 1; and therefore, nn is composed of distinct prime powers such as n=21,31n = 2^1, 3^1, etc.

Thus, the structure n n should support k k being a power of two to ensure σ(n)\sigma(n) is a power of two:

1. If each (ai+1)(a_i + 1) for the corresponding prime pip_i is a power of two, then their product, k k , the number of divisors, is also a power of two.

Therefore, if the sum of all positive divisors is a power of two, the number of divisors must also be a power of two. Thus, we conclude:

The number of divisors is a power of two. \boxed{\text{The number of divisors is a power of two.}}

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.