Numbers That Divide the Others' Sum

Here is problem #1841 from Mathematics Magazine,v. 83, n. 2, APRIL 2010. The problem was proposed by H. A. ShahAli, Tehran, Iran.

Let n ≥ 3 be a natural number. Prove that there exist n pairwise distinct natural numbers such that each of them divides the sum of the remaining n - 1 numbers.

Solution

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

Let n ≥ 3 be a natural number. Prove that there exist n pairwise distinct natural numbers such that each of them divides the sum of the remaining n - 1 numbers.

We need to check the claim for some small number n. Naturally, n = 3 comes to mind along with the three numbers 1, 2, 3. Let's see: 1 divides (2 + 3), 2 divides (1 + 3), and 3 divides (1 + 2).

It would have been nice if, when moving from n integers to n + 1, we were able to expand an existing n-set instead of inventing a new (n + 1)-set from a scratch. There is one way to approach that problem. The new number to be added to the n-set must divide the sum of the existsing numbers. As we know little of what that sum might be, let's try the sum itself. So, let's look at the set of for numbers, 1, 2, 3, 6 (= 1 + 2 + 3).

This indeed works: 1 divides (2 + 3 + 6), 2 divides (1 + 3 + 6), 3 divides (1 + 2 + 6) and 6 divides (1 + 2 + 3).

For a set of 5 integers we want to choose 1, 2, 3, 6, 12. Let's do the arithmetic once more:

1 divides 2 + 3 + 6 + 12,
2 divides 1 + 3 + 6 + 12,
3 divides 1 + 2 + 6 + 12,
6 divides 1 + 2 + 3 + 12,
12 divides 1 + 2 + 3 + 6.

Is there any general reason why adding the sum of the existing numbers as a new one works? Yes, there is! Let a be one of the existing numbers and A the sum of the remaining ones. So that a divides A. The new member we add equals s = a + A and is clearly divisible by a (because A is.) Now, for a set of n elements we have to establish n divisibility facts. For the expanded set, we need to check n + 1 of them. As we just saw the first n hold: a|(A + a + A), for any a from the existing set of n integers. But the remaing (n + 1)st divisibility works automatically, due to the choice of the new element: s|s.

The answer is 1, 2, 3, 6, 12, 24, 48, ...

|Contact| |Front page| |Contents| |Arithmetic|

Copyright © 1996-2018 Alexander Bogomolny

71471261