# The sum of $49$ natural numbers is $540$. Find the largest possible value of their greatest common divisor.

The sum of $$49$$ natural numbers is $$540$$. Find the largest possible value of their greatest common divisor.

I don't really understand even how the proof should be structured here. It must be shown that the gcd of numbers does not exceed some natural number $$d'$$, right? Is it going to be enough? I'd be thankful if you could show me a full, formal proof.

• I think the answer is $10$. I got this from doing $540\div49\approx11.02$ and recognizing that $11$ is prime but $10$ is not. Extending, we have $540=48\times10+1\times60$ and $\gcd(10,60)=10$. I'm at a loss as to how to prove this, however. Commented Oct 18, 2019 at 18:07
• @AndrewChin I think it's pretty much that, except noting that the problem with 11 is not that it is prime but that it is not a factor of 540.
– user694818
Commented Oct 18, 2019 at 18:12
• @DavidG.Stork The greatest common divisor of a set of elements is also a divisor of their sum Commented Oct 18, 2019 at 18:14
• @MarkBennet 1,225. Clearly the numbers need not be distinct. (But presumably they cannot be 0).
– user694818
Commented Oct 18, 2019 at 18:15
• @AndrewChin the next divisor of $540$ is $12$, but $49*12$ is already bigger than $540$. I think that proves that $10$ is the maximal possible common divisor. Commented Oct 18, 2019 at 18:23

Denote the numbers by $$x_1, x_2, \ldots, x_{49}$$ and their greatest common divisor by $$g$$. Then $$g \le x_i$$ for each $$i$$, and so $$g \le \min(x_1, \ldots, x_{49})$$. But the minimum is less than or equal to the average of the numbers, so $$g \le 540/49$$. Since $$g$$ is an integer we have $$g \le 11$$.

Next, $$540 = x_1 + x_2 + \cdots + x_{49}$$. Let $$x_i = g y_i$$ for each $$i$$; the $$y_i$$ are positive integers because $$g$$ is a divisor of $$x_i$$. So $$540 = g(y_1 + \cdots + y_{49})$$ and therefore $$g$$ is a factor of $$540$$.

So $$g$$ can't be $$11$$. It can be $$10$$, and we can construct an explicit example, $$x_1 = x_2 = \cdots = x_{48} = 10$$ and $$x_{49} = 60$$. Similarly $$g$$ can be any factor of $$540$$ smaller than 11.

We are trying to satisfy the equation

$$\sum_{i=1}^n a_ix_i=540$$ where $$\sum_{i=1}^n a_i=49$$ and $$x_i\in\Bbb N$$.

I propose that the answer is $$10$$, since we have $$540=48\times 10+1\times 60 \Rightarrow\gcd(10,60)=10$$ (as per my comment above).

Suppose the answer is greater than $$10$$. We know that the maximum $$\gcd$$ of a set is at most equal to one of the elements in the set. In order to produce a $$\gcd$$ greater than $$10$$ (say, $$11$$), then we must have another element in the set that is a multiple of that number (i.e. $$11k, k\in\Bbb N, k>1$$). We would then have $$a_1(11)+a_2(11k)=540.$$ Notice that this does not work as $$540\equiv 1\pmod{11}$$, or more specifically, $$540\not\equiv 0\pmod{11}$$.

So, in addition to a potential $$\gcd$$ value greater than $$10$$, it must also divide $$540$$. The next lowest factor of $$540$$ is $$12$$, so we can try as we had above: \begin{align} a_1(12)+a_2(12k)&=540\\ 12(a_1+ka_2)&=540\\ a_1+ka_2&=45 \end{align} But from our original equation, we need $$a_1+a_2=49$$. So, the $$\gcd$$ you are looking for cannot be $$12$$, nor can it be greater than $$12$$. Therefore, the answer must be $$10$$.

It cannot be $$11$$ (as mentioned above). So...

$$10$$

$$44 \cdot 10 + 5 \cdot 20 = 540$$

(or similar answers by trading $$10$$s for multiples of $$10$$)