Maximum possible gcd of integer elements, whose sum is 540.

Question

What would be a maximum possible GCD of $a_1, a_2, ... a_{49} \in \mathbb{N}$ . Given that

$$ a_1 + a_2 + ... + a_{49} =540 $$

The answer from the book is 10. I was trying to solve it using linear combinations of GCD. However, I stuck.

Answer 1

Let $(a_1,a_2,\ldots,a_{49})=(db_1,db_2,\ldots,db_{49})$, where $d=\gcd(a_1,a_2,\ldots, a_{49})$.

$$b_1+b_2+\cdots+b_{49}=\frac{540}{d}\ge 1+1+\cdots+1=49$$ Therefore $d\le 11$. We can't have $d=11$, because $11\nmid 540$. However,

$$(a_1,a_2,\ldots,a_{49})=(\underbrace{10,10,\ldots,10}_{48 \text{ numbers}},60)$$

works as a solution, so $d=10$ is the maximum possible value of $d$.

Answer 2

If $gcd(a_1,a_2,...,a_{49})$ would be at least $12$, the sum would be at least $588$, which would be too big. If the gcd would be $11$, we would get the equation $11k=540$, which has no solution.

It is easy to find a solution with $gcd(a_1,a_2,...a_{49})=10$.