Some comments on fractions of integers less than and coprime to n

James Tanton (@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 $\phi(n)$ .

A pretty mindless computation indicates there’s not likely to be any positive integers k such that a fraction $1/k$ of the numbers $1,2,\ldots, n-1$ are coprime with $n$ .

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:

$\displaystyle\phi(n)=n\prod_{p|n, p \textrm{ prime}}(1-\frac{1}{p})$

so to say, for example, that

$\frac{\phi(n)}{n-1}=\frac{1}{3}$

is to say that

$\displaystyle3\prod_{p|n}(1-\frac{1}{p})=1-\frac{1}{n}$

While it’s commonly the case that

$\displaystyle3\prod_{p|n}(1-\frac{1}{p})>1-\frac{1}{n}$

it is not universally so. For example if $n$ 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

$\displaystyle3\prod_{p|n}(1-\frac{1}{p}) < 1-\frac{1}{n}$

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

$\frac{\phi(n)}{n-1}=\frac{1}{3}$

seems to be a little subtle.

When $n=p_1p_2\ldots p_k$ is a product of distinct primes $p_1,p_2,\ldots,p_k$ then

$\frac{\phi(n)}{n-1}=\frac{1}{3}$

is equivalent to

$3(p_1-1)(p_2-1)\ldots (p_k-1)= p_1p_2\ldots p_k - 1$

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

if $3(p_1-1)(p_2-1)= p_1p_2 - 1$ then

$2p_1p_2 -3(p_1+p_2) + 4 = 0$

We can write $p_2=p_1+d$ where $d\neq 0$ because $p_1\neq p_2$ .

Then,

$2 p_1^2 +(2d-6)p_1 +4-3d=0$

which means

$p_1 =(3 - d + \sqrt{1 + d^2})/2$

which is not possible since $1+d^2$ is not a square.

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