James **jamestanton**) asked the following question on Twitter (December 31, 2017):

“If all of the numbers 1, 2, …, n-1 are coprime to n (share only the factor 1 with n), then n must be prime. Is there an n with precisely half of the numbers 1,2,…,n-1 coprime to n? One with precisely a third of them coprime to n?”

There is a well-known name for the number of positive integers less than and coprime to n: this is Euler’s totient function, denoted .

A pretty mindless computation indicates there’s not likely to be any positive integers k such that a fraction of the numbers are coprime with .

The *Mathematica* code below was aborted at n = 1,038,898,229 without finding any such k:

**n = 2;**

**While[IntegerQ[(n – 1)/EulerPhi[n]] == False, n++]**

**n**

So why might this be so?

Euler’s product formula for the totient function is:

so to say, for example, that

is to say that

While it’s commonly the case that

it is not universally so. For example if is the product of the primes 2, 3, 71, 491, 1031, 1489, 1657, 1949, 2269, 2381, 3613, 4079, 5743, 5807, 6131, 6257, 6637, 6709, 7207, 7433 then

So, at least from the perspective of Euler’s totient formula, the question even of whether there is an for which

seems to be a little subtle.

When is a product of distinct primes then

is equivalent to

We can see how this isn’t possible for a product of 2 primes (i.e. ):

if then

We can write where because .

Then,

which means

which is not possible since is not a square.

For a product of 3 distinct primes we can do something similar, writing and end up with a *cubic* polynomial in with coefficients involving . As we get a larger collection of primes we get polynomials, with integer coefficients, in of higher degree (for which the rational roots test doesn’t seem to help).

We can also see how is not possible when is a prime power:

from we get and the rational roots test tells us that the only integer solution is .

Maybe more is clear to a number theorist. At this point however, I am stumped.