Olympiad problem: Erdos-Selfridge

Question

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.

Answer 1

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

Answer 2

Call the product $N$. The factors are incongruent modulo 11, so no more than one of them can be a multiple of 11. If $N$ is a square, $11\nmid N$, so $11\mid n$. Then, modulo 11, $N=1(2\cdot6)(3\cdot4)(-2\cdot-6)(-3\cdot-4)(-1)=-1$ which is not a square modulo 11. Therefore $N$ is not a square.

The modulus here, 11, was small enough that the non-zero residues could be conveniently listed, showing the pairs of inverses. If the problem is posed again with a greater number of terms, you might instead appeal to Wilson's theorem. Alternatively, if the modulus $m$ is prime, as it is here, Lagrange's theorem proves that, modulo $m$, $x^2=1$ only if $x=1$ or $x=-1$, so the $m-3$ residues $2,\dots,m-2$ group into pairs, the residues in each pair being each other's inverses. Therefore $2\cdot\ldots\cdot (m-2)=1$, so $1\cdot\ldots (m-2)(-1)=-1$. If there are $4k$ terms, $m=4k+1$ and $-1$ is a square modulo $m$; if there are $4k-2$ terms, $m=4k-1$ and $-1$ is not a square modulo $m$.

Answer 3

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

Best regards