To find the maximum possible value of their greatest common divisor $\gcd (a_1,a_2,\cdots, a_7)$.

497 Views Asked by At

The sum of seven distinct positive integers $a_1,a_2,\cdots, a_7$ is $315$. To find the maximum possible value of their greatest common divisor $\gcd (a_1,a_2,\cdots, a_7)$.


If they were all equal then $a_i = 45$ and the maximum possible value of their greatest common divisor would have been $45$.

Since they are distinct $\gcd(a_1,a_2,\cdots, a_7) < 45$.

Let $ \gcd(a_1,a_2,\cdots, a_7) = d$. Hence $a_i = db_i$ for some $b_i$ for all $i$.

Since $a_1 + \cdots + a_7 = 315$, we have $d(b_1 +\cdots+ b_7) = 315$ and hence $d$ divides $315$.

Thus $d$ can be any factor of $315$ smaller than $45$.


How to proceed after that?

1

There are 1 best solutions below

2
On BEST ANSWER

If $d$ divides both $a$ and $b$, then $d$ divides their sum. By similar reasoning, the max gcd must be a divisor of $315 = 5 \times 7 \times 3^2.$

Further, set $d$ as the gcd. Then, you must have that

$a_1, a_2, \cdots, a_7$ can be represented by

$(d \times x_1), (d \times x_2), \cdots, (d \times x_7).$

This implies that $x_1, \cdots, x_7$ must be distinct positive integers, such that

$\displaystyle x_1 + x_2 + \cdots + x_7 = \frac{315}{d}$.

Further, just as you are very limited in your choices for $d$, a factor of $315$, you are similarly limited in your choices for $~\displaystyle \frac{315}{d}.$

Trying to maximize $d$ is equivalent to trying to minimize $~\displaystyle \frac{315}{d}.$

This implies that you are trying to minimize $x_1 + x_2 + \cdots + x_7.$

However, since $x_1, \cdots, x_7$ must all be positive integers, their sum must be $\geq 1 + 2 + \cdots + 7 = 28.$

Then, you want $~\displaystyle \frac{315}{d}$ to be as small as possible, and still be $\geq 28.$

With $315$ being factored by $5 \times 7 \times 3^2,$ it is immediate that $\displaystyle \frac{315}{d}$ can not be an element in $\{28,29,\cdots, 34\}.$

Therefore, $~\displaystyle \frac{315}{d}$ is minimized by setting it to $(35)$. This implies that $d = 9$, so $(9)$ is the largest possible gcd.

It remains to verify that the equation $x_1 + x_2 + \cdots + x_7 = 35$
does have a solution in distinct positive integers.

Since there is the obvious solution of $(x_1, x_2, \cdots, x_6, x_7) = (1,2,\cdots, 6, 14)$, the problem is solved.