Product of consecutive numbers as a power

By Yatir Halevi on Friday, April 12, 2002 - 12:18 pm:

There is an old conjecture that says that the product of consecutive numbers can't be a number to the power of another number (Is there a simple way of saying it???) - except to the power of one (of course).
It was proved by Erdos and Selfrididge in 1975, and it took them 9 years.
To prove that two consecutive numbers can't have that property is easy since gcd(n,n+1)=1 and they can't be to the same power. (except 1 and 2)
Does anybody have the proof?
(I guess it wasn't done using induction...)

Thanks,

Yatir

By David Loeffler on Saturday, April 13, 2002 - 09:49 pm:

According to a Google search, it's Erdos and Selfridge: "The product of consecutive integers is never a power",
Illinois Journal of Mathematics 19 (1975), pages 292--301. (Mathematical Reviews 51 #12692). (Aren't search engines wonderful?)
However, I'm not in Cambridge at the moment so I don't have access to a library which which would have the paper. Is anyone on the NRICH team better placed?

David

By Ian Short on Monday, April 15, 2002 - 10:15 am:

Thanks for the tip-off David. The proof for general powers is a mountain, but there was a reference for just square powers (Erdos 1939) which I'll indicate the main steps for, to suggest the flavour of such questions. The general ideas involved are within reach of anyone who has taken a first course in number theory, only a few parts need further material. Extra work required in the proof will be indicated by up to 3 (#)s.

Aiming for a contradiction, assume there are integers

k

m

and

n > 1

with

n (n + 1) \dots (n + k - 1) = m^{2}

Write

n + i = a_{i} x_{i}^{2}

where

a_{i}

are square-free integers (no square divisors, Erdos writes 'quadratfrei') and if prime

p | a_{i}

then

p < k

(#).

Show

a_{i}

s distinct. (###)

Thus

a_{0} a_{1} \dots a_{k - 1}

is greater than the product of the first

k

square-free integers. i.e. for

k > 24

it is greater than

(4 / 3)^{k} k!

. (##)

The number of

a_{i}

s divisible by prime

p < k

is equal to or less than

[k / p] + 1

(

[.]

denoting integer part) (#).

Hence $a_{0} a_{1} \dots a_{k - 1} < \underset{p < k}{Π} p^{[k / p] + 1}$ .

In fact, $a_{0} a_{1} \dots a_{k - 1} < 2^{k - 2} \underset{p < k}{Π} p^{[k / p]}$ . (###)

But

k! > (2^{k} 3^{k / 2} / 6 k^{2}) \underset{3 < p < k + 1}{Π} p^{[k / p]}

using a theorem of Legendre. (##)

Combine inequalities in (4), (5) and (6) to get a contradiction for

k > 100

. Some other guy (Seimatsu Narumi) had previously established the result for

k < 202

The proof was a few pages long, but this is the gist of it. Tell me if you have any problems or if you discover a better proof!.

Ian

By Yatir Halevi on Monday, April 15, 2002 - 04:25 pm:

Ian, Could you please explain stages (4) and (6)...

Thanks,
Yatir

By Ian Short on Tuesday, April 16, 2002 - 11:35 am:

Sure, my 24 in (4) seems to have come out of nowhere.

(4) Let $S_{n} =$ the $n$ th square-free number. It can be verified algebraically that $S_{1} S_{2} \dots S_{24} > (4 / 3)^{24} 24!$ . Thus if we can show $S_{n} > 4 n / 3$ , the result holds by induction. This is true as for $m > 9$ , the number of square-free integers equal to or less than $m$ is at most $m - [m / 4] - 1 < 3 m / 4$ . (Suffices to omit all the integers divisible by 4.)

(6) Let $r_{p} =$ the power to which $p$ divides $k!$ for $p < k + 1$ (so that $k! = \underset{p < k + 1}{Π} p^{r}$ ). Then for $p > 3$ use $r_{p} \geq [k / p]$ and for $p = 2$ and 3 Erdos obtains $p^{r} \geq p^{k / (p - 1)} / kp$ via Legendre's formula.

This formula states that if $k = a_{0} + a_{1} p + \dots + a_{s} p^{s}$ ( $0 \leq a_{i} < p$ ) then $r_{p} = (k - \sum a_{i}) / (p - 1)$

Thus $r_{p} \geq k / (p - 1) - (s + 1)$ so put this to the power of $p$ .

Combining the results for $p = 2$ , 3 and $p > 3$ should give the inequality that I wrote down.

The remaining (###) bits are no more complicated than this, just longer. Hope that's okay.

Ian

By Yatir Halevi on Tuesday, April 16, 2002 - 03:40 pm:

Ian, in (4), how did you show that the product of the a_i s is greater the the product of the square free integers...sorry, I still didn't get it...

Thanks, Yatir

By Ian Short on Tuesday, April 16, 2002 - 06:24 pm:

I'm not sure whether you now understand the first part of (4). All I had meant to indicate was that the a_i s are distinct and square-free so that a_0 ...a_{k-1} is equal to or greater than the product of the k smallest square-free numbers- i.e. the first k such.

Note that I checked none of the arithmetic, rather trusting Erdos. It is necessary by around the 7th step to up k to about 100 anyway.

Tell me if you get anywhere with your factorial idea, I'll dwell on it...

Ian

By Yatir Halevi on Wednesday, April 17, 2002 - 06:01 am:

Yes, I do get (4) now, I thoughtt of a proof and I didn't see that the reasoning was lying right there in front of me...