Maths Olympiad Prep

Library / /42 of 43

Number theory Difficulty 7.1 National Olympiad, round 2 Prove it Italy

Problem:

a. There are seven positive integers a,b,c,d,e,f,ga, b, c, d, e, f, g such that the products ab,bc,cd,de,ef,fg,gaab, bc, cd, de, ef, fg, ga are all perfect cubes. Prove that a,b,c,d,e,f,ga, b, c, d, e, f, g are also perfect cubes.

b. There are six positive integers a,b,c,d,e,fa, b, c, d, e, f such that the products ab,bc,cd,de,ef,faab, bc, cd, de, ef, fa are all perfect cubes. Is it always true that a,b,c,d,e,fa, b, c, d, e, f are all perfect cubes?

Note: an integer mm is called a perfect cube if m=n3m = n^{3} for some integer nn.

Solution

Solution:

First, note that the product and the quotient (when this is an integer) of two perfect cubes is again a perfect cube. The quantity
(ab)(cd)(ef)(ga)(bc)(de)(fg)=a2 \frac{(ab)(cd)(ef)(ga)}{(bc)(de)(fg)} = a^{2}
is then a perfect cube. Now, if a2a^{2} is a perfect cube, then aa is also a perfect cube: indeed, a2a^{2} being a perfect cube means that, letting a=p1t1prtra = p_{1}^{t_{1}} \cdots p_{r}^{t_{r}} be the prime factorization of aa, 2ti2 t_{i} is a multiple of 3 for every ii; but then tit_{i} is also a multiple of 3 for every ii, which means that aa is a perfect cube. We thus know that aa and abab are perfect cubes; it follows that bb is also one. We now know that bb and bcbc are perfect cubes, from which it follows that cc is also one, and so on.

Note that, for a number, being a perfect cube means that for every prime pip_{i} appearing with exponent tit_{i} in its factorization, tit_{i} is a multiple of 3. Let us then fix a prime pp and call ta,tb,,tgt_{a}, t_{b}, \ldots, t_{g} the exponents with which it appears in the factorization of a,b,,ga, b, \ldots, g. The conditions of the problem tell us that
ta+tb, tb+tc, tc+td, td+te, te+tf, tf+tg, tg+ta t_{a} + t_{b},\ t_{b} + t_{c},\ t_{c} + t_{d},\ t_{d} + t_{e},\ t_{e} + t_{f},\ t_{f} + t_{g},\ t_{g} + t_{a}
are multiples of 3.
Suppose for contradiction that one of the tt's is not a multiple of 3. Up to cyclically renaming the integers involved, we may assume it is tat_{a}. Suppose that the remainder of the division of tat_{a} by 3 is 1 (the case in which it is 2 is handled in exactly the same way). Then, from the fact that the first of the expressions above is a multiple of 3, it follows that the remainder of the division by 3 of tbt_{b} is 2; hence, from the second it follows that tct_{c} has remainder 1, and then similarly that tdt_{d} has remainder 2, tet_{e} has remainder 1, tft_{f} has remainder 2, and tgt_{g} has remainder 1. But the last relation says that tg+tat_{g} + t_{a} is a multiple of 3, whereas we have shown that both tat_{a} and tgt_{g} have remainder 1, which is impossible. This completes the proof by contradiction.

The fact that the quantities in (1) are multiples of 3 can be expressed as the following linear system over the field of integers modulo 3.
ta+tb0(mod3)tb+tc0(mod3)tc+td0(mod3)td+te0(mod3)te+tf0(mod3)tf+tg0(mod3)tg+ta0(mod3) \begin{aligned} t_{a} + t_{b} &\equiv 0 \pmod{3} \\ t_{b} + t_{c} &\equiv 0 \pmod{3} \\ t_{c} + t_{d} &\equiv 0 \pmod{3} \\ t_{d} + t_{e} &\equiv 0 \pmod{3} \\ t_{e} + t_{f} &\equiv 0 \pmod{3} \\ t_{f} + t_{g} &\equiv 0 \pmod{3} \\ t_{g} + t_{a} &\equiv 0 \pmod{3} \end{aligned}
This system has as its associated matrix the matrix
(11111111111111). \left(\begin{array}{lllllll} 1 & 1 & & & & & \\ & 1 & 1 & & & & \\ & & 1 & 1 & & & \\ & & & 1 & 1 & & \\ & & & & 1 & 1 & \\ & & & & & 1 & 1 \\ 1 & & & & & & 1 \end{array}\right).
Over the field of integers modulo 3, this matrix is invertible (because it has nonzero determinant), so the system has only the trivial solution ta=tb==tg=0t_{a} = t_{b} = \ldots = t_{g} = 0.

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.