Here’s a classic exercise in elementary number theory.
Consider a (mathematical and thus constrained to a point) rabbit who starts at zero on the real number line and starts to jump towards her right.
Her first jump is of length 1, her second jump is of length , her third jump is of length
, and so on, so that after
jumps, her position
on the line is
There are hurdles which are placed at the integers from 2 onwards. Of course, we don’t have a hurdle at the integer 1, for this is where the rabbit lands on her first jump. The question is:
Will the rabbit ever land on a hurdle?
Or, put mathematically:
Is an integer for any
?
The answer to both questions is no; the rabbit will never hit a hurdle, for it turns out that the sum
is never an integer for . The proof we will give here involves the following theorem.
Bertrand’s postulate: For every real number there is a prime in the interval
.
Now, let’s prove that the rabbit never lands on a hurdle. We will prove this by contradiction. Assume that we have the equation
where and
is an integer. If we set
in Bertrand’s postulate, it follows that there must be a prime
in the interval
. This means that the term
appears on the left hand side of the above equation, and we may subtract it from both sides to get
Now, the left hand side of the above equation can be written as a fraction , where
is not divisble by the prime
. This is because we have moved the term involving
to the other side, and there are no other integers from 1 to
which are divisible by
, as we chose
so that its first multiple
is greater than
. Thus we have
which we can rearrange to get
This gives us a contradiction as the left hand side is divisible by the prime , but the right hand side is not, as both
and
are not divisible by
.