Maths Olympiad Prep

Library / /12 of 14

Number theory Difficulty 8.8 Shortlist Prove it Estonia

Call a tuple (bm,bm+1,,bn)(b_m, b_{m+1}, \dots, b_n) of integers *perfect* if both following conditions are fulfilled:
1. There exists an integer a>1a > 1 such that bk=ak+1b_k = a^k + 1 for all k=m,m+1,,nk = m, m+1, \dots, n;
2. For all k=m,m+1,,nk = m, m+1, \dots, n, there exists a prime number qq and a non-negative integer tt such that bk=qtb_k = q^t.
Prove that if nmn - m is large enough then there is no perfect tuples, and find all perfect tuples with the maximal number of components.

Solution

*Answer:* (20+1,21+1,22+1,23+1,24+1)(2^0 + 1, 2^1 + 1, 2^2 + 1, 2^3 + 1, 2^4 + 1).

Clearly (20+1,21+1,22+1,23+1,24+1)(2^0 + 1, 2^1 + 1, 2^2 + 1, 2^3 + 1, 2^4 + 1) is a perfect tuple with length 5. Show in the rest that there are no other perfect tuples with length 5 or larger.

For that, let (am+1,am+1+1,,an+1)(a^m + 1, a^{m+1} + 1, \dots, a^n + 1) be an arbitrary perfect tuple with length at least 5. There must exist at least two odd exponents among m,m+1,,nm, m+1, \dots, n; let kk and k+2k+2 be the two largest odd exponents. As ak+1a^k + 1 and ak+2+1a^{k+2} + 1 are prime powers while having a common divisor a+1a+1, these two integers must be powers of the same prime qq. Thus the larger of them, ak+2+1a^{k+2} + 1, is divisible by the smaller one, ak+1a^k + 1, which shows that ak+1a^k + 1 divides also the difference a2(ak+1)(ak+2+1)=a21a^2 \cdot (a^k + 1) - (a^{k+2} + 1) = a^2 - 1. Hence ak+1a21a^k + 1 \le a^2 - 1, implying k<2k < 2. So k=1k = 1 as kk is odd. By choice of kk, the only odd exponents in our perfect tuple are 1 and 3 and the tuple is of the form (a0+1,a1+1,a2+1,a3+1,a4+1)(a^0 + 1, a^1 + 1, a^2 + 1, a^3 + 1, a^4 + 1).

As a+1a+1 and a3+1a^3+1 are powers of the same prime number qq, also the ratio a3+1a+1=a2a+1\frac{a^3+1}{a+1} = a^2-a+1 is a power of qq. Note that a2a+12aa+1=a+1a^2-a+1 \ge 2a-a+1 = a+1 by a2a \ge 2, hence a2a+1a^2-a+1 is divisible by a+1a+1. Thus the difference (a2a+1)(a+1)(a2)=3(a^2-a+1)-(a+1)(a-2) = 3 is divisible by a+1a+1. This filters out the only possibility a=2a=2.

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.