# Olympiad problem: Erdos-Selfridge

The following problem is a special case of Erdos-Selfridge theorem: http://projecteuclid.org/euclid.ijm/1256050816

Problem: Prove that for any positive integer $n$, the product $(n+1)(n+2)...(n+10)$ is not a perfect square.

It appeared as an olympiad problem, so there is a solution using just olympiad techniques (i.e. "elementary" maths), and it shouldn't be too long either because in an olympiad you only have limited time. However, after trying this for almost a day I still couldn't get anything interesting. I've tried simpler versions but it was no use. I would appreciate any help!

EDIT: I couldn't find a solution anywhere, I tried the AoPS contest section. It's from the 2002 Bosnia Herzegovina Team Selection Test, in case anyone wants to try looking.

• Hint: It's got something to do with primes. – Lucian Sep 30 '14 at 17:24
• Obvious Hint #$2$: Given the fact that all products of k consecutive numbers are divisible by $k!$, how many sevens are there in your product ? – Lucian Sep 30 '14 at 17:48
• @Lucian: There are two sevens in $43 \cdot \dots \cdot 52$, which seems fine to me. – J. J. Sep 30 '14 at 17:54
• @J.J.: Well, then... It's all well if it ends well, right ? ;-) – Lucian Sep 30 '14 at 18:01
• @SheheryarZaidi There could be two sevens as in $49$ - that's what makes it hard. One technique though is to analyse the small primes - anything not divisible by a small prime must be a square. The only square numbers which differ by less than $10$ are small, and easily eliminated, so you can only have one. – Mark Bennet Sep 30 '14 at 18:16

## 2 Answers

Here is an extended start. The multiples of two are either found in the odd positions or the even positions and include at least one multiple of $8$ - if two multiples of $8$ then one is a multiple of $16$.

There are three multiples of three (at least one of which is even) or four, if $n+1$ is a multiple of three - and two of these are even. There are at most two odd multiples of three.

There are two multiples of $5$, one of which must be even.

There are one or two multiples of $7$, at most one of which can be odd.

So of our ten numbers, five are even. Of the odd numbers at most two are divisible by $3$, one by $5$ and one by $7$. This leaves one odd number in the product which has no prime factor less than ten. This must be an odd square whose prime factors are all $\ge 11$.

Note we need to separate out the odd multiples of $3,5,7$ to avoid having two odd squares with large prime factors (which is impossible, because large squares cannot be that close together).

Now analyse the possible patterns, allocating the primes $2$ and $3$ to positions in the sequence. Note that an odd square which is not a multiple of $9$ is $\equiv 1 \mod 24$, and this is taken into account below, in that the square has to follow a multiple of $6$. Also even multiples of $5$ or $7$ may be present (here are the ones where $n+1$ is even)

$[2,3], [5/7/s],[2],[3],[2], [5/7],[2,3],[5/7/s],[2],[3]$

$[2],[3],[2],[7 - 2 \text{ is not a square mod } 5],[2,3,5^*],[s \text { only place for square }],[2],[3],[2],[5 -\text{ only place for } 5]$

*Even multiple of $5$ identified through other criteria

$[2],[5,7],[2,3],[5/7/s],[2],[3],[2],[5/7], [2,3], [5/7/s]$

and similarly for the cases where the first term is odd

These can now be analysed in terms of higher powers of the small primes (taking into account what is known about $s$ and quadratic residues modulo $5$ and $7$ - one example of this is given above). Note that the total powers of the small primes must all be even. Note also that any prime factor $p\gt 7$ of any term must involve $p$ to an even power.

I believe careful analysis will eliminate most cases easily.

Working forward from the square we have:

$[s], [2], [3], [4], [5a], [2,3], [7], [8b], [3], [2,5]$

$a$ we know that $s\equiv -4$ modulo the prime here. $3$ is not a prime factor

$b$ could be any power of $2$ which is at least $8$. Other powers of two are exact. Powers of $3,5,7$ could be higher

Working backwards from the square

$[?f],[2,3],[5e],[4],[3],[2],[7d],[8c,3,5e'],[s],$

$c$ any power of two $\ge 8$

$d$ note that $2$ is not a square mod $5$. The two positions for odd multiples of $7$ before and after the square are incompatible, so the sequence must avoid having both.

$e$ only place for $5$, $e'$ note now that either way the square is congruent to $1$ mod $5$.

$f$ is now impossible to fill.

Whence the sequence must be a ten element subsequence of

$[2,3],[5],[4],[3],[2^*],[7^*],[8,3,5],[s], [2], [3], [4], [5], [2,3], [7], [8], [3], [2,5]$

$^*$ can't start here, because of incompatible sevens

the product is equal 2^5 x (odd number) . 5 is not even, thus the product cannot be a square.

Best regards

• This is not correct. Some of the even numbers in the product have a factor of 4. – user940 Apr 12 '16 at 14:37
• Nonsense: if $n=9$, then the product contains a $2^9$ factor. – Alex M. Apr 12 '16 at 15:14