Maths Olympiad Prep

Library / /173 of 520

Number theory Difficulty 5.3 AIME, harder Find the answer

3. Let dd - the greatest common divisor of eight natural numbers, the sum of which is equal to 595. What is the largest value that dd can take?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Answer: 35.

Solution. If each of the numbers is divisible by dd, then their sum is also a multiple of dd. Therefore, dd is a divisor of the number 595. Let's factorize the latter into prime factors: 595=5717595=5 \cdot 7 \cdot 17 and list all its divisors:

1,5,7,17,35,85,119,595 1,5,7,17,35,85,119,595

Each of the eight numbers (from the problem statement) is not less than dd. Therefore, their sum, which is 595, is not less than 8d8 d. From the inequality 5958d595 \geqslant 8 d we get d74d \leqslant 74. From the list ()(*) the largest possible value is 35.

It is not difficult to come up with a corresponding example (which is far from unique): let seven numbers be 70, and one more be 105.

Evaluation. 13 points for a complete solution. 7 points for an estimate without an example. 6 points for an example without an estimate.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.