Olympiad Maths Prep

Track / Stage 6 / 239 of 400 #1239 of 2000

Problem 1239

National olympiad, first round
Number theory Difficulty 6.4 Find the answer

Find all positive integers nn that have distinct positive divisors d1,d2,,dkd_1, d_2, \dots, d_k, where k>1k>1, that are in arithmetic progression and n=d1+d2++dk.n=d_1+d_2+\cdots+d_k. Note that d1,d2,,dkd_1, d_2, \dots, d_k do not have to be all the divisors of nn.

Official solution

1. Let d1=m d_1 = m and d2d1=a d_2 - d_1 = a . Then the divisors in arithmetic progression are d1,d2,,dk d_1, d_2, \ldots, d_k where di=m+(i1)a d_i = m + (i-1)a for i=1,2,,k i = 1, 2, \ldots, k .

2. The sum of these divisors is:
n=d1+d2++dk=m+(m+a)+(m+2a)++(m+(k1)a) n = d_1 + d_2 + \cdots + d_k = m + (m + a) + (m + 2a) + \cdots + (m + (k-1)a)
This can be simplified using the formula for the sum of an arithmetic series:
n=km+ak(k1)2 n = k \cdot m + a \cdot \frac{k(k-1)}{2}

3. Since dkn d_k \mid n , we have:
m+(k1)akm+ak(k1)2 m + (k-1)a \mid k \cdot m + a \cdot \frac{k(k-1)}{2}

4. Let gcd(m,a)=d \gcd(m, a) = d . Then m=dm1 m = dm_1 and a=da1 a = da_1 with gcd(m1,a1)=1 \gcd(m_1, a_1) = 1 . Substituting these into the divisibility condition, we get:
m1+(k1)a1m1k+a1k(k1)2 m_1 + (k-1)a_1 \mid m_1k + a_1 \cdot \frac{k(k-1)}{2}

5. Similarly, since dk1n d_{k-1} \mid n , we have:
m1+(k2)a1m1k+a1k(k1)2 m_1 + (k-2)a_1 \mid m_1k + a_1 \cdot \frac{k(k-1)}{2}

6. Using the Euclidean algorithm, we find:
gcd(m1+(k1)a1,m1+(k2)a1)=gcd(a1,m1+(k2)a1)=gcd(m1,a1)=1 \gcd(m_1 + (k-1)a_1, m_1 + (k-2)a_1) = \gcd(a_1, m_1 + (k-2)a_1) = \gcd(m_1, a_1) = 1

7. Therefore, from the above, we obtain:
(m1+(k1)a1)(m1+(k2)a1)m1k+a1k(k1)2 (m_1 + (k-1)a_1) \cdot (m_1 + (k-2)a_1) \mid m_1k + a_1 \cdot \frac{k(k-1)}{2}

8. Expanding and simplifying, we get:
m12+m1a1(2k3)+a12(k1)(k2)m1k+a1k(k1)2 m_1^2 + m_1a_1(2k-3) + a_1^2(k-1)(k-2) \mid m_1k + a_1 \cdot \frac{k(k-1)}{2}

9. From this, we deduce that 2k3 2 \le k \le 3 .

Case 1: If k=2 k = 2 :
m12+m1a12m1+a1 m_1^2 + m_1a_1 \mid 2m_1 + a_1
Since gcd(m1,a1)=1 \gcd(m_1, a_1) = 1 and m12m1+a1 m_1 \mid 2m_1 + a_1 , we get m1=1 m_1 = 1 . This implies:
a1+12+a1 a_1 + 1 \mid 2 + a_1
which is a contradiction.

Case 2: If k=3 k = 3 :
m12+3m1a1+2a123m1+3a1 m_1^2 + 3m_1a_1 + 2a_1^2 \mid 3m_1 + 3a_1
From here, we get a1=1 a_1 = 1 . Therefore:
m12+2m1+23m1+3 m_1^2 + 2m_1 + 2 \mid 3m_1 + 3
This implies m1=1 m_1 = 1 . Hence, m=a m = a and k=3 k = 3 .

10. Therefore, the divisors are d1=m,d2=2m,d3=3m d_1 = m, d_2 = 2m, d_3 = 3m and:
n=d1+d2+d3=6m n = d_1 + d_2 + d_3 = 6m

Thus, the solution is n=6m n = 6m for all mZ+ m \in \mathbb{Z}^+ .

The final answer is n=6m \boxed{ n = 6m } for all mZ+ m \in \mathbb{Z}^+ .

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