The sum of $10$ natural numbers is $2014$. Determine the greatest possible value of the GCD of these numbers.
Is this a trial and error type of problem?
$a_1 + a_2 + ... + a_{10} = 2014$.
Obviously, we want all big-similar numbers.
What I did is:
$2014 = 2(19)(53) = 19*106$, and so:
$9(106) + 1(1060) = 106 + 106 + ... + 106 + 1060$ and $\gcd(106, 106, ... , 106, 1060) = 106$?
Is $106$ the right answer?
In general, suppose that $a_1+\cdots+a_m=N$ with $a_i$ (positive) natural numbers with the gcd of the $a_i$'s as large as possible. If $\gcd(a_i)=g$, then we know that $g$ divides $N$. Moreover, since $g$ divides each $a_i$ (and each $a_i$ is positive), $\frac{N}{g}\geq m$.
If you take the largest $g$ so that $g$ divides $N$ and $\frac{N}{g}\geq m$, we can make $g$ the gcd of the $a_i$'s by $N=g+\cdots+g+(\frac{N}{g}-(m-1))g$.