Maths Olympiad Prep

Library / /26 of 92

Number theory Difficulty 6.1 National olympiad Prove it Iran

Prove that for each natural number k>1k > 1, only a finite number of kk-tuples of consecutive natural numbers exist such that their product is a perfect square.

Solution

If kk is even, using the lemma proved in the solution of the 7th problem of the Third Round, we can say that there exist an integer aa and some polynomial Q(x)Z[x]Q(x) \in \mathbb{Z}[x] such that
(Q(x))2a2(x+1)(x+2)(x+k)<(Q(x)+1)2,for large values of x. (Q(x))^2 \le a^2(x+1)(x+2)\cdots(x+k) < (Q(x)+1)^2, \quad \text{for large values of } x.
Since Q(x)Q(x) is a perfect square for infinitely many values of xx, we get
(Q(x))2=a2(x+1)(x+2)(x+k). (Q(x))^2 = a^2(x+1)(x+2)\cdots(x+k).
This is a contradiction since a2(x+1)(x+2)(x+k)a^2(x+1)(x+2)\cdots(x+k) does not have any multiple roots.

For odd values of kk, we claim that if i=1k(a+i)\prod_{i=1}^k (a+i) is a perfect square, there is some nonempty proper subset AA of {1,2,,k}\{1, 2, \dots, k\} such that iA(a+i)\prod_{i \in A} (a+i) is a perfect square. To prove the claim, consider all of the subsets of S={a+1,a+2,,a+k}S = \{a+1, a+2, \dots, a+k\}.

For any subset AA of SS, let F(A)F(A) be the product of elements of AA (F()=1F(\emptyset) = 1) and let g(A)g(A) be the square free part of F(A)F(A).

Note that all of the prime divisors of g({a+1}),g({a+2}),,g({a+k})g(\{a+1\}), g(\{a+2\}), \dots, g(\{a+k\}) are less than kk, because if some prime number pkp \ge k divides two of the numbers g({a+1}),g({a+2}),,g({a+k})g(\{a+1\}), g(\{a+2\}), \dots, g(\{a+k\}), for example pa+ip|a+i and pa+jp|a+j, we obtain pjip|j-i and hence p<kp < k. If for some i,1ik,pi, 1 \le i \le k, p divides only g({a+i})g(\{a+i\}), this leads to a contradiction because g(S)=1g(S) = 1 is a perfect square, and the power of pp in the factorization of i=1ka+i\prod_{i=1}^k a + i should be even.

For any ASA \subseteq S, g(A)g({a+1})g({a+2})g({a+k})g(A)|g(\{a+1\})g(\{a+2\})\cdots g(\{a+k\}) and so the prime divisors of all g(A)g(A)'s are less than kk. This implies that for each ASA \subseteq S, g(A)g(A) is a divisor of 2×3××pπ(k1)2 \times 3 \times \cdots \times p_{\pi(k-1)}. So we have 2π(k1)2^{\pi(k-1)} cases for g(A)g(A).

Since k1>π(k1)k-1 > \pi(k-1), 2k>2×2π(k1)2^k > 2 \times 2^{\pi(k-1)}. This implies that there are two subsets A,BSA, B \subseteq S such that AB,SBA \ne B, S-B and g(A)=g(B)g(A) = g(B) (note that g(A)=g(SA)g(A) = g(S-A) because g(S)=1g(S) = 1). Now, g(A)=g(B)g(A) = g(B), therefore F(A)F(B)F(A)F(B) is a perfect square. We have
F(A)F(B)=F(AB)2F(AΔB). F(A)F(B) = F(A \cap B)^2 F(A\Delta B).
Hence F(AΔB)F(A\Delta B) is a perfect square. But AΔB,SA\Delta B \ne \emptyset, S since AB,SBA \ne B, S-B, and this is the desired subset.

By replacing AΔBA\Delta B with SAΔBS - A\Delta B if necessary, we will get a nonempty proper subset XX of {1,2,,k}\{1, 2, \dots, k\} with an even number of elements such that iX(x+i)\prod_{i \in X} (x + i) is a perfect square. Using the lemma in the solution of the 7th problem of the Third Round again, this product can be a perfect square for at most a finite number of values of xx. Thus if kk is odd, then (x+1)(x+2)(x+k)(x+1)(x+2)\cdots(x+k) is a perfect square for at most a finite number of values of xx.

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.