Maths Olympiad Prep

Library / /9 of 18

Number theory Difficulty 5.8 AIME, harder Find the answer Italy

Problem:

Lucia wants to write three positive integers a,b,ca, b, c in such a way that each of them is a divisor of 3030 and that the greatest common divisors between two consecutive terms (that is, MCD(a,b)\operatorname{MCD}(a, b) and MCD(b,c)\operatorname{MCD}(b, c)) are prime numbers. In how many ways can she do this?

Pick one

Solution

Solution:

The answer is (C). We distinguish several cases, depending on the number of prime factors of bb:

a. If bb has 0 prime factors, then b=1b=1, and whatever the value of aa is, we have (a,b)=1(a, b)=1, which is not a prime number.

b. If bb has exactly one prime factor, that is, it is itself prime, then the condition that (a,b)(a, b) and (b,c)(b, c) be prime means that both must coincide with bb. The integers a,ca, c can therefore be chosen in any way among the divisors of 30=23530=2 \cdot 3 \cdot 5 that are multiples of bb. It is easy to check that (whatever the value of bb) there are 4 choices for aa and 4 choices for cc (for example, if b=2b=2, then aa and cc can be chosen in the set {2,6,10,30}\{2,6,10,30\}). Taking into account that 30=23530=2 \cdot 3 \cdot 5 has exactly 3 distinct prime factors (and therefore there are 3 choices for bb in this case), we have 344=483 \cdot 4 \cdot 4=48 possible choices for the triple (a,b,c)(a, b, c).

c. If bb has exactly 2 prime factors, say b=pqb=pq, then setting r=30/br=30 / b one easily sees that the condition that (a,b)(a, b) and (b,c)(b, c) be prime numbers is equivalent to the integers a,ca, c belonging to the set {p,q,pr,qr}\{p, q, pr, qr\}. We observe that choosing bb is equivalent to choosing the prime r{2,3,5}r \in \{2,3,5\}, so in this case we have 3 choices for bb and 4 choices for each of aa and cc, for a total of 344=483 \cdot 4 \cdot 4=48 possible choices.

d. Finally, if bb has exactly 3 prime factors, then b=30b=30. Since by hypothesis aa and cc divide 3030, we have (a,b)=a(a, b)=a and (b,c)=c(b, c)=c, so we must choose both aa and cc in the set {2,3,5}\{2,3,5\}. We then have 33=93 \cdot 3=9 choices for the triple (a,b,c)=(a,30,c)(a, b, c)=(a, 30, c).

In total, the number of triples (a,b,c)(a, b, c) satisfying the desired properties is 48+48+9=10548+48+9=105.

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: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.