A Number Theory short (?) story: Christian Aebi's "13" problem

In August 2002, Christian Aebi posted the following question on the sci.math newsgroup:

"Trying to solve the problem: if n > 9 then n*(n+1)*(n+2)*(n+3) is divisible by a prime > or = 13. Thanks for your help."

The ensuing discussion on sci.math was inconclusive, so I felt that an 'exhaustive' approach to Aebi's problem might be in order, and I was able to confirm that in June 2003 ... by breaking the problem into no less than 108 cases, each one shown to be impossible! Surely many of these cases are trivial, and none of them is profound or non-elementary, therefore my solution is ideal for didactic purposes, fully accessible even to high school students. At the same time, Aebi's problem and its obvious generalizations raise interesting questions for the research mathematician: for example, how 'lucky', necessary, effective, or even programmable is my approach, and how far could my or other methods go?

Limiting the discussion to Aebi's original question, I outline my approach as follows:

Observe first that precisely one of the four consecutive integers must be divisible by 2 (but not 4) and precisely another one must be divisible by a power of 2, say 2^k with k greater than 1; indeed no two integers differing by 2 may both be divisible by powers of 2. Likewise, one or two of the four consecutive integers must be divisible by 3 or a power of 3; again no two of the four integers may both be divisible by powers of 3, but it is possible for both (first and last) to be divisible just by 3: to cover all possibilities we consider divisibility by 3^l, where l is now greater than or equal to 1.

The next observation concerns the placement of the other three prime factors allowed by the assumption that none of them can be equal to or greater than 13. Clearly no two out of any four consecutive integers may both be divisible by 5 or 7 or 11, so each one of the three factors must be 'used' at most once; less obviously (see below), each one of the three factors must be 'used' at least once as well, and no two of them may both be factors of anyone of the four consecutive integers.

Putting everything together and taking into account an easily proven special case of the Catalan Conjecture (now a theorem anyway), namely that no power of 2 and a power of an odd integer may differ by 1 (save for 8 and 9, that is), we conclude that there exist precisely 18 possibilities generating, depending on the precise location and permutation of 5, 7, and 11, 18x6 = 108 cases. The process is illustrated in a 4x4 tableau with links to each possibility and case's destruction.

POSTSCRIPT: A more 'mathematical', yet still elementary, proof is available in E. F. Ecklund, Jr. & R. B. Eggleton's "A note on consecutive composite integers" (Mathematics Magazine 48 (1975), pp. 277-81).

Copyright 2003 George Baloglou