divisibilitygcd-and-lcm
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.
You wrote it yourself: the gcd is the smallest positive linear combination. Smallest positive linear combination is shorthand for smallest positive number which is a linear combination. It is true that $0$ is a linear combination of $12$ and $6$ with integer coefficients, but $0$ is not positive.
The proof is not difficult, but it is somewhat lengthy. We give full detail below.
Let $e$ be the smallest positive linear combination $as+bt$ of $a$ and $b$, where $s$ and $t$ are integers. Suppose in particular that $e=ax+by$.
Let $d=\gcd(a,b)$. Then $d$ divides $a$ and $b$, so it divides $ax+by$. Thus $d$ divides $e$, and therefore in particular $d\le e$.
We show that in fact $e$ is a common divisor of $a$ and $b$, which will imply that $e\le d$. That, together with our earlier $d\le e$, will imply that $d=e$.
So it remains to show that $e$ divides $a$ and $e$ divides $b$. We show that $e$ divides $a$. The proof that $e$ divides $b$ is essentially the same.
Suppose to the contrary that $e$ does not divide $a$. Then when we try to divide $a$ by $e$, we get a positive remainder. More precisely, $$a=qe+r,$$ where $0\lt r\lt e$. Then $$r=a-qe=a-q(ax+by)=a(1-qx)+b(-qy).$$ This means that $r$ is a linear combination of $a$ and $b$, and is positive and less than $e$. This contradicts the fact that $e$ is the smallest positive linear combination of $a$ and $b$.
I made a similar question here, where I propose a partial solution.
How to find the approximate basic frequency or GCD of a list of numbers?
In summary, I came with this
And the goal is to find the $x$ which maximizes the $\operatorname{gcd}_{appeal}$. Using the formulas and code described there, using CoCalc/Sage you can experiment with them and, in the case of your example, find that the optimum GCD is ~100.18867794375123:
testSeq = [399, 710, 105, 891, 402, 102, 397]
gcd = calculateGCDAppeal(x, testSeq)
find_local_maximum(gcd,90,110)
plot(gcd,(x, 10, 200), scale = "semilogx")
Best Answer
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.