Alexander Bogomolny (@CutTheKnotMath)
The proofs rely, among other things, on the fact that prime numbers are of the form
, which is clear since a prime greater than 3 cannot leave a remainder of 0, 2, 3 or 4 upon division by 6.
I want to consider a slight extension of this fact – basically replacing
by an arbitrary non-zero complex number – by considering something relevant to the first solution offered at Cut the Knot.
In that solution the facts are utilized.
Suppose we choose arbitrarily as a complex number.
Can we find complex numbers such that
?
Yes, we can, notably & uniquely:
or
So, we now have the following:
Let be a complex number and let either
or
.
If then
.
For this follows directly from the fact that
.
A similar argument holds when .
Since primes are of the form
we have the following:
Let be a complex number and let either
or
.
If is prime then
.
Another collection of positive integers that are necessarily of the form are those
for which
, where
is Euler’s phi function: the number of
that are coprime with
. See the Online Encyclopedia of Integer Sequences, for example.