Maths Olympiad Prep

Library / /11 of 12

Number theory Difficulty 7.5 National olympiad, round 2 Prove it Czech Republic

Find all triples of positive integers aa, bb, cc for which the product
(a+b)(b+c)(c+a)(a+b+c+2036)(a+b)(b+c)(c+a)(a+b+c+2036)
is equal to the power of a prime number with an integer exponent.

Solutions — 2

Solution 1

First, let us note that at least one of the numbers a+ba+b, a+ca+c and b+cb+c must be even. Indeed, two of the three numbers aa, bb, cc have the same parity, so their sum is even.
If the product we investigate is a power of a prime pp, then each of the four factors must be a power of pp. As we already know, one of the first three factors is even, so p=2p = 2. Each of the four factors is therefore a power of two, which is greater than 1=201 = 2^0, since the numbers a,b,ca, b, c are positive integers. Hence, each factor is an even number.

Further observe that the numbers a+ba+b, a+ca+c, b+cb+c are all even numbers, if and only if the numbers a,b,ca, b, c all have the same parity. Since a+b+c+2036a+b+c+2036 is even, a,ba, b and cc must be even numbers. Therefore, we can write a=2a1a = 2a_1, b=2b1b = 2b_1, and c=2c1c = 2c_1, where a1,b1,c1a_1, b_1, c_1 are positive integers. Then of course
(a+b)(a+c)(b+c)(a+b+c+2036)=24(a1+b1)(a1+c1)(b1+c1)(a1+b1+c1+1018). (a+b)(a+c)(b+c)(a+b+c+2036) = 2^4(a_1+b_1)(a_1+c_1)(b_1+c_1)(a_1+b_1+c_1+1018).
The product of the last four parentheses must be a power of two. The numbers a1,b1,c1a_1, b_1, c_1 are therefore solutions to the original problem with the constant 2036 replaced by 1018. For the same reason as above a1,b1a_1, b_1, and c1c_1 must be even. We denote by a2,b2a_2, b_2 and c2c_2 respectively their halves (they are again positive integers) and we get
(a+b)(a+c)(b+c)(a+b+c+2036)=28(a2+b2)(a2+c2)(b2+c2)(a2+b2+c2+509). (a+b)(a+c)(b+c)(a+b+c+2036) = 2^8(a_2+b_2)(a_2+c_2)(b_2+c_2)(a_2+b_2+c_2+509).
And again, we have the same problem with the constant 509, so the numbers a2,b2a_2, b_2, and c2c_2 necessarily have the same parity. However, since the number 509 is odd, a2,b2a_2, b_2 and c2c_2 must be odd numbers. We see that the triple a2=b2=c2=1a_2 = b_2 = c_2 = 1 satisfies the problem (since 3+509=5123 + 509 = 512 is a power of two), so the corresponding triple a=b=c=4a = b = c = 4 is a solution to the original problem. We show that it is the only solution.

Suppose that at least one of the numbers a2,b2,c2a_2, b_2, c_2 is greater than one, let it be c2c_2 without loss of generality. Then, of course, the power of two equal to a2+c2a_2+c_2 is greater than 2, so it is divisible by four. This means that dividing by four one of the numbers a2,c2a_2, c_2 gives a remainder of 1 and the other a remainder of 3. So the third odd number b2b_2 has the same remainder when divided by four as one of the numbers a2,c2a_2, c_2. The sum of b2b_2 with this number then has a remainder of 2, and since this sum is also a power of two, it must be the power of 212^1. It follows that b2=1b_2 = 1 and a2=1a_2 = 1 (the equality of c2=1c_2 = 1 is ruled out by our assumption c2>1c_2 > 1). Thus the remainder 3 when divided by four necessarily gives c2c_2. But then the number a2+b2+c2+509a_2+b_2+c_2+509 gives remainder 2, so it is not a power of two, and that is a contradiction.

Conclusion. A single triple (a,b,c)=(4,4,4)(a, b, c) = (4, 4, 4) satisfies the problem statement.

Solution 2

Let abca \ge b \ge c hold without loss of generality, so then a+bc+ab+c2a+b \ge c+a \ge b+c \ge 2. The product (a+b)(b+c)(c+a)(a+b+c+2036)(a+b)(b+c)(c+a)(a+b+c+2036) is a power of some prime number if and only if powers of that prime are all four factors of a+b,b+c,c+aa+b, b+c, c+a, and a+b+c+2036a+b+c+2036. So let a+b=pk,c+a=pla+b = p^k, c+a = p^l, and b+c=pmb+c = p^m for some prime pp and non-negative integers k,lk, l and mm. For these, by the theorem of the introduction klm1k \ge l \ge m \ge 1.

If k>lk > l, and hence k1lk-1 \ge l and k1mk-1 \ge m, with respect to p2p \ge 2, we would have
a+b=pkpk1+pk1pl+pm=(c+a)+(b+c)>a+b, a+b = p^k \ge p^{k-1} + p^{k-1} \ge p^l + p^m = (c+a) + (b+c) > a+b,
which is impossible. Necessarily, then, k=lk=l, so a+b=pk=pl=c+aa+b = p^k = p^l = c+a, where b=cb=c. Then of course pm=b+c=2bp^m = b+c = 2b, and so b=c=pm/2b=c = p^m/2, so 2p2|p, e.g. p=2p=2, and therefore b=c=2m1b=c = 2^{m-1} and a+b=2ka+b = 2^k. Since p=2p=2, it is also a+b+c+2036=2na+b+c+2036 = 2^n for some integer nn, which obviously satisfies the condition 2n>20362^n > 2036.

By the conclusion of the previous paragraph, the numbers k,m,nk, m, n satisfy the equality
2n=(a+b)+c+2036=2k+2m1+2036. 2^n = (a+b) + c + 2036 = 2^k + 2^{m-1} + 2036.
Note that dividing by 16 number 2036 gives the remainder of 4, while 2n2^n certainly gives a remainder of 0 if 2n>20362^n > 2036. This implies 2k+2m112(mod16)2^k + 2^{m-1} \equiv 12 \pmod{16}. The summands 2k2^k and 2m12^{m-1}—as powers of two—are congruent to 1, 2, 4, 8 or 0 (mod 16). It is easy to see that the derived congruence holds only if one of the powers of 2k,2m12^k, 2^{m-1} yields a residue of 4 and the other 8. Then k,m1=2,3k, m-1 = 2, 3. However, since 2m1=b<a+b=2k2^{m-1} = b < a+b = 2^k, it is necessarily m1<km-1 < k, and therefore m1=2m-1=2 and k=3k=3. Hence b=c=2m1=4b=c=2^{m-1}=4 and a+b=2k=8a+b=2^k=8, whence also a=4a=4. This gives us the only possible triple (a,b,c)=(4,4,4)(a, b, c) = (4, 4, 4). This is indeed the solution to the problem—the product of the problem is then 88820488 \cdot 8 \cdot 8 \cdot 2048, while 8=238=2^3 and 2048=2112048 = 2^{11}.

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 and solution reproduced as published; topic and difficulty added by this site.