Torsten Sillke Some mathematical Impossibilities? 2001-11-20 Problem A: Prove that the product of four consecutive positive integers cannot be a perfect square. Problem B: Prove that the product of three or more consecutive positive integers cannot be a perfect square. Problem C: Can both x^2 + y and x + y^2 be squares for x and y natural numbers? Problem D: Why is n(n+2) = m(m+1) impossible for positive integers m, n? Problem E: Can p+q and p-q be squares for p and q primes? Problem F: Show that n! cannot be a prefect square for any integer n>1. Problem Z: Let P a monic polynomial in Z[X]. We suppose that : - the degree of P is even, - for all positive integer n, P(n) is a square in Z. Can we say that P is a square in Z[X] ? Solution A: Let N be the smallest integer (of the four). The product is then N(N+1)(N+2)(N+3) = N(N+3) (N+1)(N+2) = (N^2 + 3N)(N^2 + 3N + 2) = (N^2 + 3N + 1)^2 - 1 This is not a perfect square since two positive squares cannot differ by 1. According to Erd"os this problem has already been solved by L. Euler [Eul??] for products of four consecutive members of an arithmetic progression. For an elementary proof of this fact see Erdelyi [Erd00] who didnot find a reference of a proof of Euler. Erd"os and Selfridge showed in general: The product of consecutive integers is never a power [ErS75] solving a 150-year-old problem [Hof98, p254]. Solution B: See arithmetic/consecutive.product.p below. References: AiZ98: Martin Aigner, G\"unter M. Ziegler; Proofs from THE BOOK, Springer, Berlin, 1998 - Chapter 2: Bertrand's postulate, p7-12 For every n>=1, there is some prime number p with n 1 such that n(n + 1)(n + 2) = m^r. SaA99: Mark Saul, Titu Andreescu; Square or not square? Quantum July/August 1999, p45-46, 53 problem 10: n!+2000 cannot be a square problem 11: n(n+1) cannot be a square problem 12: n(n+2) cannot be a square problem 14: n(n+1)(n+2)(n+3) cannot be a square problem 15: (m+n)^2 + 3m + n + 1 cannot be a square (for n != m) problem 16: 1!+2!+ ... +n! cannot be a square (for n > 3) problem 17: n! cannot be a square (for n > 1) This article contain 17 impossible square problems. Sil65: David L. Silverman; Mathematics Magazine 38 (Jan. 1965) 60 Product of four consecutive odd integers. 3^2 = (-3)(-1) 1 3 Tri85: Charles W. Trigg; Mathematical Quickies, 1967 (reprinted: Dover Publications, 1985). Problem 130: Never a Square if n^4 + 2n^3 + 2n^2 + 2n + 1 is a square then n=0. Problem 262: Wanted - Integer Solutions find all integral solutions of y^2 + y = x^4 + x^3 + x^2 + x. That is (2y+1)^2 = 4(x^4 + x^3 + x^2 + x) + 1. ==> arithmetic/consecutive.product.p <== from the rec.puzzles.archive Prove that the product of three or more consecutive positive integers cannot be a perfect square. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - ==> arithmetic/consecutive.product.p <== Prove that the product of three or more consecutive positive integers cannot be a perfect square. ==> arithmetic/consecutive.product.s <== Lemma: If a and b are relatively prime, and ab is a square, then a and b are squares. (This is left as an exercise.) Three consecutive numbers: Suppose (n - 1)n(n + 1) = k^2, where n > 1. Then n(n^2 - 1) = k^2. But n and (n^2 - 1) are relatively prime. Therefore n^2 - 1 is a perfect square, which is a contradiction. Four consecutive numbers: n(n + 1)(n + 2)(n + 3) = (n^2 + 3n + 1)^2 - 1 Five consecutive numbers: Assume the product is a integer square, call it m. The prime factorization of m must have even numbers of each prime factor. For each prime factor, p, of m, p >= 5, p^2k must divide one of the consecutive naturals in the product. (Otherwise, the difference between two of the naturals in the product would be a positive multiple of a prime >= 5. But in this problem, the greatest difference is 4.) So we need only consider the primes 2 and 3. Each of the consecutive naturals is one of: 1) a perfect square 2) 2 times a perfect square 3) 3 times a perfect square 4) 6 times a perfect square. By the shoe box principle, two of the five consecutive numbers must fall into the same category. If there are two perfect squares, then their difference being less than five limits their values to be 1 and 4. (0 is not a natural number, so 0 and 1 and 0 and 4 cannot be the perfect squares.) But 1*2*3*4*5=120!=x*x where x is an integer. If there are two numbers that are 2 times a perfect square, then their difference being less than five implies that the perfect squares (which are multiplied by 2) are less than 3 apart, and no two natural squares differ by only 1 or 2. A similar argument holds for two numbers which are 3 times a perfect square. We cannot have the case that two of the 5 consecutive numbers are multiples (much less square multiples) of 6, since their difference would be >= 6, and our span of five consecutive numbers is only 4. Therefore the assumption that m is a perfect square does not hold. QED. In general the equation: y^2 = x(x+1)(x+2)...(x+n), n > 3 has only the solution corresponding to y = 0. This is a theorem of Rigge [O. Rigge, ``Uber ein diophantisches Problem'', IX Skan. Math. Kong. Helsingfors (1938)] and Erdos [P. Erdos, ``Note on products of consecutive integers,'' J. London Math. Soc. #14 (1939), pages 194-198]. A proof can be found on page 276 of [L. Mordell, ``Diophantine Equations'', Academic Press 1969]. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Generalization: Given a monic polynom p of even order. Is there an integral solution of p(n) = k^2? Solution: There is a effective method to find the finite number of solutions. Compute the sqrt of p. Forget all term of order 1/N of higher. This is an approximate solution. Examples: p(N) = N(N+1) Sqrt(p(N)) = N + 1/2 + O(1/N) q(N) = N + 1/2 r(N) = p(N) - q(N)^2 = -1/4 As N^2 < p(N) < (N + 1/2)^2 for N>0 it is not a square. p(N) = N(N+1)(N+2)(N+3) Sqrt(p(N)) = N^2 + 3N + 1 + O(1/N) q(N) = N^2 + 3N + 1 r(N) = p(N) - q(N)^2 = -1 = O(1) Note that r(N) is of order 0 and not of the expected order 1. p(N) = N(N+1)(N+2)(N+3)(N+4)(N+5) Sqrt(p(N)) = N^3 + 15/2 N^2 + 115/8 N + 75/16 + O(1/N) q(N) = N^3 + 15/2 N^2 + 115/8 N + 75/16 r(N) = p(N) - q(N)^2 = O(N^2) As order(r) < order(q) there can be at most finitely many solutions. p(N) = N(N+1)(N+2)(N+3)(N+4)(N+5)(N+6)(N+7) Sqrt(p(N)) = N^4 + 14 N^3 + 63 N^2 + 98 N + 28 + O(1/N) q(N) = N^4 + 14 N^3 + 63 N^2 + 98 N + 28 r(N) = p(N) - q(N)^2 = (8 N + 28)^2 = O(N^2) Note that r(N) is of order 2 and not of the expected order 3. As order(r) < order(q) there can be at most finitely many solutions. p(N) = N^4 + N^3 + N^2 + N + 1 [Hon78] Sqrt(p(N)) = N^2 + N/2 + 3/8 + O(1/N) q(N) = N^2 + N/2 + 3/8 r(N) = p(N) - q(N)^2 = 5/8 N + 55/64 = O(N) As order(r) < order(q) there can be at most finitely many solutions. As 2q(N) is between adjacent integers 2N^2 + N < 2q(N) < 2N^2 + N + 1 we will show that (2N^2 + N)^2 < 4p(N) < (2N^2 + N + 1)^2 except for a finite set of integers. First show the left side (2N^2 + N)^2 <= 4p(N) <=> 0 <= 3N^2 + 4N + 4 = 1/3 ((3N+2)^2 + 8) which is valid for all real N. Second show the right side 4p(N) <= (2N^2 + N + 1)^2 <=> 0 <= N^2 - 2N - 3 = (N-3)(N+1) which is valid for all real N > 3 and N < -1. Checking the values N from -1 to 3 gives the integral solutions p(-1) = p(0) = 1^2 and p(3) = 11^2. p(N) = (N-3a)(N-a)(N+a)(N+3a) [Sil65] Sqrt(p(N)) = N^2 - 5a^2 + O(1/N) q(N) = N^2 - 5a^2 r(N) = p(N) - q(N)^2 = -16a^4 = O(1) Note that r(N) is of order 0 and not of the expected order 1. As (s-1)^2 - s^2 = -2s + 1 look for the roots of -2(N^2 - 5a^2) + 1 = -16a^4 N = sqrt( 8a^4 + 5a^2 + 1/2 ) For a=1 we find the bounds 0<=N<4 and for a=2 we find the bounds 0<=N<13 and for a=3 we find the bounds 0<=N<27. Solutions: a=1: p(0) = 3^2, p(1) = p(3) = 0^2. Solutions: a=2: p(0) = 12^2, p(2) = p(6) = 0^2. Solutions: a=3: p(0) = 27^2, p(3) = p(9) = 0^2. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - By partitioning the linear factors we get differences of squares. p(N) = a1 a2 ... ak b1 b2 ... bk = ((a1 a2 ... ak + b1 b2 ... bk)/2)^2 - ((a1 a2 ... ak - b1 b2 ... bk)/2)^2 But this approach is successfull for p4, p8, (and p2). p2(N) = N(N+1) = (N + 1/2)^2 - (1/2)^2 not the difference of two integers, as there are values 2 mod 4. p4(N) = N(N+1)(N+2)(N+3) = N(N+3) (N+1)(N+2) = (N^2 + 3N)(N^2 + 3N + 2) = (N^2 + 3N + 1)^2 - 1^2 Unique partition with one square of order 0. q4(N) = N^2 + 3N + 1 p6(N) = N(N+1)(N+2)(N+3)(N+4)(N+5) = N(N+3)(N+5) (N+1)(N+2)(N+4) = (N^3 + 8 N^2 + 15 N)(N^3 + 7 N^2 + 14 N + 8) = (N^3 + 15/2 N^2 + 29/2 N + 4)^2 - (1/2 N^2 + 1/2 N - 4)^2 = N(N+3)(N+4) (N+1)(N+2)(N+5) = (N^3 + 15/2 N^2 + 29/2 N + 5)^2 - (1/2 N^2 + 5/2 N + 5)^2 = N(N+2)(N+5) (N+1)(N+3)(N+4) = (N^3 + 15/2 N^2 + 29/2 N + 6)^2 - (1/2 N^2 + 9/2 N + 6)^2 All partitions with one square of order 2. Note that the bigger squares are consecutive integers. p8(N) = N(N+1)(N+2)(N+3)(N+4)(N+5)(N+6)(N+7) = N(N+3)(N+5)(N+6) (N+1)(N+2)(N+4)(N+7) = (N^4 + 14 N^3 + 63 N^2 + 90 N ) * (N^4 + 14 N^3 + 63 N^2 + 106 N + 56) = (N^4 + 14 N^3 + 63 N^2 + 98 N + 28)^2 - (8 N + 28)^2 = (q4(N) q4(N+4) - 1)^2 - (8 N + 28)^2 Unique partition with one square of order 1. p12(N) = N(N+1)(N+2)(N+3)(N+4)(N+5)(N+6)(N+7)(N+8)(N+9)(N+10)(N+11) = N(N+2)(N+6)(N+7)(N+8)(N+10) (N+1)(N+3)(N+4)(N+5)(N+9)(N+11) = (N^6 + 33 N^5 + 418 N^4 + 2508 N^3 + 6952 N^2 + 6720 N ) * (N^6 + 33 N^5 + 418 N^4 + 2574 N^3 + 8041 N^2 + 11793 N + 5940) = (N^6 + 33 N^5 + 418 N^4 + 2541 N^3 + 14993/2 N^2 + 18513/2 N + 2970)^2 - ( 33 N^3 + 1089/2 N^2 + 5073/2 N + 2970)^2 Unique partition with one square of order 3. p16(N) = N(N+1)(N+2)(N+3)...(N+14)(N+15) = N(N+3)(N+5)(N+6)(N+9)(N+10)(N+12)(N+15) (N+1)(N+2)(N+4)(N+7)(N+8)(N+11)(N+13)(N+14) = (N^8 + 60 N^7 + 1490 N^6 + 19800 N^5 + 151569 N^4 + 665820 N^3 + 1547100 N^2 + 1458000 N ) * (N^8 + 60 N^7 + 1490 N^6 + 19800 N^5 + 151953 N^4 + 677340 N^3 + 1671260 N^2 + 2024400 N + 896896) = (N^8 + 60 N^7 + 1490 N^6 + 19800 N^5 + 151761 N^4 + 671580 N^3 + 1609180 N^2 + 1741200 N + 448448)^2 - ( 192 N^4 + 5760 N^3 + 62080 N^2 + 283200 N + 448448)^2 Unique partition with one square of order 4. p20(N) = N(N+1)(N+2)(N+3)...(N+18)(N+19) No partition with one square of order 6 possible. --------------------------------------------------------- A classical theorem discovered independently by Sylvester and Schur, states that the product of k consecutive integers, each greater than k, has a prime divisor greater than k. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Problem C Can both x^2 + y and x + y^2 be squares for x and y natural numbers? Solution: No. Since x and y are both positive integers, for x^2 + y to be a square requires y >= 2*x + 1. But similarly, for y^2 + x to be a square, x >= 2*y + 1 is also necessary. These inequalities cannot hold simultaneously if x and y are positive. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Problem E: Can p+q and p-q be squares for p and q primes? Solution: Let p+q = x^2 and p-q = y^2 then there difference is (*) 2q = x^2 - y^2 = (x+y)(x-y). Reducing mod 2 we have (x+y)(x-y) = 0 (mod 2). As x+y = x-y (mod 2) both factors are 0 (mod 2). That means 2q = x^2 - y^2 = (x+y)(x-y) = 0 (mod 4). Therefore q = 0 (mod 2) which gives the solution q = 2. Now we can substitute back into (*) finding 4 = (x+y)(x-y) with two even factors x+y and x-y. Let both factors be positive we find the system: x+y = 2 and x-y = 2. Unique solution (2,2,2,0) = (p,q,x,y). - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Problem ([Trigg P262] and [Mar66]) Find all integers x, y satisfying y^2 + y = x^4 + x^3 + x^2 + x. Solution: Multiply both sides by 4 and add 1 gives (2y + 1)^2 = 4x^4 + 4x^3 + 4x^2 + 4x + 1. Let p(x) = 4x^4 + 4x^3 + 4x^2 + 4x + 1 then Sqrt(p(x)) = 2x^2 + x + 3/4 + O(1/x) We will show that (2x^2 + x)^2 < p(x) < (2x^2 + x + 1)^2 for all x < -1 or x > 2. First show the left side (2x^2 + x)^2 <= p(x) <=> 0 <= 3x^2 + 4x + 1 = (x+1)(3x+1) which is valid for x <= -1 or x >= -1/3. Second show the right side p(x) <= (2x^2 + x + 1)^2 <=> 0 <= x^2 - 2x = x(x-2) which is valid for x <= 0 or x >= 2. Therefore we have only to consider the cases of x in {-1, 0, 1, 2}. Checking these values gives the six solutions y = -1, x = -1 y = 0, x = -1 y = -1, x = 0 y = 0, x = 0 y = -6, x = 2 y = 5, x = 2 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Problem ([Hun81]) Find all integers x, y satisfying y^2 = x^4 + 4x^3 + 8x^2 + 4x + 16. Solution: Let p(x) = x^4 + 4x^3 + 8x^2 + 4x + 16 then Sqrt(p(x)) = x^2 + 2x + 2 + O(1/x) We will show that (x^2 + 2x + 1)^2 < p(x) < (x^2 + 2x + 3)^2 for all x <= -5 or x >= 1. First show the left side (x^2 + 2x + 1)^2 < p(x) <=> 0 < 2x^2 + 15 which is valid for real x. Second show the right side p(x) < (x^2 + 2x + 3)^2 <=> 0 < 2x^2 + 8x - 7 = 2(x+5)(x-1) + 3 which is valid for x <= -5 or x >= 1. Therefore we have only to consider the cases of x in {-4, -3, -2, -1, 0} for exceptions. Checking these values gives the solutions p(0) = 4^2 and p(-3) = 7^2. We are left with the case that p(x) = (x^2 + 2x + 2)^2 the only square in the inverval left. This is the case for x = 3 only. So there is one further square p(3) = 17^2. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Problem: [Tri85 Q 130] if n^4 + 2n^3 + 2n^2 + 2n + 1 is a square then n=0. solution Leo Moser, MM 37 (Jan. 1964) 62: We have (n^2 + n)^2 = n^4 + 2n^3 + n^2 < n^4 + 2n^3 + 2n^2 + 2n + 1 < n^4 + 2n^3 + 3n^2 + 2n + 1 = (n^2 + n + 1)^2 for n != 0. So the given number lies between two consecutive squares. solution Ch. Trigg: n^4 + 2n^3 + 2n^2 + 2n + 1 = (n^2 + 1)(n + 1)^2. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Problem F: [SaA99 problem 17] Show that n! cannot be a prefect square for any integer n>1. Solution [SaA99 solution 17] -------- Let p be the largest prime that divides n!. If we want n! to be a square, it must contain at least one more multiple of p, namely 2p. But according to Bertrand's postulate, between p and 2p there must be another prime. This contradicts our assumption that p is the largest prime that divides n!. Note that the proof doesnot apply for n=1 as no prime divides 1!. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Problem Z: (from sci.math.research 1998-11-05) Let P a monic polynomial in Z[X]. We suppose that : - the degree of P is even, - for all positive integer n, P(n) is a square in Z. Can we say that P is a square in Z[X] ? Solution (Mark Sapir) -------- It can be a nice high school olympiad problem. Here is a sketch of an elementary solution: if f(x) has degree 2n, find a polynomial g(x) such that g(x)^2 has the same first n+1 coefficients as f(x) (it is always possible to do); g(x) will have ratioanal coefficients, which is not a problem, just multiply the variable x by a proper number, and you get a polynomial with integer coefficients. Then use the fact that the distance between two integer squares a^2-b^2 cannot be much smaller than 2*min{a,b}. Mark Sapir msapir@math.vanderbilt.edu Solution (Robert Israel): -------- Yes, it must be a square. If p(z) is monic with degree 2n, consider the Laurent series of q(z) = z^n sqrt(p(z)/z^(2n)) (taking the principal branch of the square root) on |z| > R = max{ |r|: p(r)=0 }. If p(z) is not a square, q(z) is not a polynomial, and we have q(z) = r(z) + a_k z^(-k) + O(|z|^(-k-1)) where r(z) is a polynomial with rational coefficients and a_k \ne 0. If M is the least common multiple of the denominators of the coefficients in r(z), M (q(z)- r(z)) can't be an integer when z is a sufficiently large integer, so neither can sqrt(p(z)). Robert Israel israel@math.ubc.ca Solution (Dave Rusin): -------- Yes. When I ran into this question last year I got this information from Bruce Reznick: >Michael Filaseta [...] contacted Schinzel, who'd know. The >consensus is that the original result (f: Z -> Z^2 => f = g^2) is >apparently well-known and has been discovered several times. I don't have any references, however. Reznick's solution was to compute Q = sqrt(P) = F + G formally where F is polynomial and G(n)->0 as n->oo. By assumption the values of Q are integers so the iterated differences are too; on the other hand high-enough differences of F also vanish. Thus the differences of G are both integral and small, hence zero, making G itself both polynomial and small, hence zero (as n->oo, and hence identically). So Q is a polynomial. Here's an alternative proof Neil Dummigan and I worked out: factor P = P1^2*P2 with P2 square-free; then y^2=P2(x) is a non-singular curve with infinitely many integral points, hence P2 is at most quadratic. (Obviously P2 can't be linear with all P2(n) squares unless P2=constant.) Completing the square makes this equivalent to an equation y^2=ax^2+b (Pell's equation) and the premise becomes that it has O(N) solutions with x Z, does it follow that P = f o g for some polynomial g? I suppose something like Reznick's solution will apply. Note that there is a distinction between integer polynomials and polynomials all of whose values at integers are integers (e.g. x(x+1)/2) so the question has to be phrased carefully. Note that the proofs cannot be purely formal, e.g. P(X) = X^4+4 is not a square in R[X] even though P(x) is a square in R for every x in R, when R = Z/5Z or R is the real number field. dave History (John Mitchell): ------- Several readers have already supplied proofs that this is true. I just wanted to mention that this question appeared on the "Aggregation" exam given to students at the Ecole Normale de Jeune Filles (in Paris) around 1980. One of the "jeunes filles" told an Argentinian mathematician I knew about the problem, and he then asked me about it. I came up with a finite difference solution that's essentially the same as Bruce Resnick's solution mentioned in Dave Rusin's reply. Notice that with this solution (and perhaps with others), you don't need the assumptions that P is monic and has even degree. John Mitchell San Diego, California Repley: On the other hand, some of these solutions (including mine, which used Laurent series) solve the harder question where "for all positive integer n" is replaced by "for infinitely many positive integers n". For that one you do need P to be monic and of even degree, otherwise counterexamples are P(n) = n and P(n) = 2 n^2 + 1. Robert Israel israel@math.ubc.ca - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Subject: Re: why is impossible for m(m+1) = n(n+2) for natural m, n? Date: 05 Jan 1999 01:54:27 -0500 Problem D: Why is n(n+2) = m(m+1) impossible for positive integers m,n? ... Rewritten as (m-n)(m+n+1) = n it is clearly unsolvable since the positive integer n cannot have a larger factor m+n+1 > n. Or, note f(n) = n(n+2) is increasing and f(m-1) < m(m+1) < f(m). Or, equivalently, adding one yields (n+1)^2 = m^2 + m + 1, but this can't be square since its between two consecutive squares: m > 0 => m^2 < m^2 + m + 1 < (m+1)^2 {this is just 1 + [ f(m-1) < m (m+1) < f(m) ] as above, i.e. its same as above after shifting f(n) -> f(n)+1 = (n+1)^2 and noting that (n+1)^2 is increasing}. REMARK Note how the above proofs depend essentially on the property that multiplication is increasing. EXERCISE Formalize the prior remark by investigating the minimal (order?) structure needed in a ring for the result to hold true. -Bill Dubuque - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Problem: [Hon78] Solving x^4+x^3+x^2+x+1=y^2 for integers. Short solution by Pete Moore (Jan. 1999, sci.math) Write the equation as (2y)^2 = 4x^4 + 4x^3 + 4x^2 + 4x + 4 And note that the right side is greater than (2x^2+x)^2, and is also equal to (2x^2+x+1)^2 - (x^2-2x-3) and hence is less than (2x^2+x+1)^2, except possibly for those values of x for which x^2-2x-3 is negative (i.e. -1<=x<=3) - for other values of x, the right side lies between two successive squares, and so cannot be a square. Considering the values -1<=x<=3 individually, we find that the only solutions are (x,y) = (-1,1), (0,1), (3,11) - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - KOMAL Gy2198: For what natural numbers is n^5 - n^4 - 2n^3 + 2n^2 + n - 1 a perfect square? Kozepiskolai Matematikai Lapok 34(1984)220 proposal -- mailto:Torsten.Sillke@uni-bielefeld.de http://www.mathematik.uni-bielefeld.de/~sillke/