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
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
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