“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++]
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. ):
We can write where because .
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.