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.