3
$\begingroup$

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.

$\endgroup$
9
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Oct 18, 2019 at 18:07
  • 1
    $\begingroup$ @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. $\endgroup$
    – user694818
    Commented Oct 18, 2019 at 18:12
  • 1
    $\begingroup$ @DavidG.Stork The greatest common divisor of a set of elements is also a divisor of their sum $\endgroup$ Commented Oct 18, 2019 at 18:14
  • 1
    $\begingroup$ @MarkBennet 1,225. Clearly the numbers need not be distinct. (But presumably they cannot be 0). $\endgroup$
    – user694818
    Commented Oct 18, 2019 at 18:15
  • 1
    $\begingroup$ @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. $\endgroup$
    – Berci
    Commented Oct 18, 2019 at 18:23

3 Answers 3

3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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$)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .