Problem Solving Positive Integers

Question

This is a very interesting word problem that I came across in an old textbook of mine. So I know the maximum value of the HCF has to be a factor of $540$ and mayhaps the Euclidean Algorithm, but other than that, the textbook gave no hints really and I'm really not sure about how to approach it. Any guidance hints or help would be truly greatly appreciated. Thanks in advance :) So anyway, here the problem goes:

Let $a_1, a_2, ... , a_{49}$ be positive integers such that $$a_1 + a_2 \ + \ ... \ + a_{49} = 540.$$ What can be the maximum value of the highest common factor of the numbers $a_1, a_2, ... , a_{49}$?

Answer 1

Denote by $h$ the highest common factor. If $h\ge 12$, then $a_i\ge h\ge 12$ implies $a_1+\cdots +a_{49}\ge 49\cdot 12=588>540$, a contradiction. Hence $h\le 11$. Now $h=11$ is impossible, because $11\nmid 540$. The rest follows by explicit calculation ($h=10$ is possible).

Answer 2

The answer is $10$, we take the decomposition:

$540=5 \cdot 20+44 \cdot 10$ or $540=\underbrace{20+\cdots+20}_\text{$5$ times} + \underbrace{10+\cdots+10}_\text{44} $.

So the maximum value $M$ of the highest common factor is at least $10$. To show that $M \le 10$ we note that $M<12$ since $540/49<12$ and $M \not=11$ since $11 \not \mid 540$.

Answer 3

How I would approach it:

First do a prime factorization of $540$:
$540 = 2 \cdot 2 \cdot 3 \cdot 3 \cdot 3 \cdot 5$

Now pick some factors and divide $540$ with it so the resulting number is larger than $49$ and try to get the smallest number possible this way. This method is a bit of trial and error but this example would be small enough to do it that way I guess.

You'll find out that $2 \cdot 5 = 10$ are the factors you're looking for.