So... I was toying around with the Goldbach Conjecture, and I came to a very interesting puzzle, related to the Euler totient Function, $φ(n)$. For those of you who don't know it, Wikipedia has a pretty good description.

My question is a little bit open-ended, because there's a lot of ways this could go:

Suppose we have a number $n$ and prime $p < \sqrt n$ such that n is not divisible by p. Then we could calculate the totient Function of $pn$ to be some constant $k$. In other words, $φ(pn) = k.$ Then my question is this: Of these $k$ relatively prime numbers, what is the minimum that can be in the first $n$ numbers of $pn?$ Or another way of phrasing the question: For a given number $n$ divisible by a prime $q$, what is the fewest possible number of integers less than $n/q$ that are relatively prime to $n$?

TO BE CLEAR: I'm not looking for a comparison $φ(n),$ I'm looking for the numbers 'in' $φ(pn)$ that also happens to be less than $n$. Essentially, I'm looking for the value of $φ(n)$ when we also eliminate everything divisible by an additional factor $p.$

For example: If $n$ is $10, p$ could be $3.$ Then $φ(3*10) = 8,$ so $k$ is $8$ and $k/p = 8/3.$ In reality, there are only $2$ numbers less than $10$ that are relatively prime to $30-1$ and $7.$ This is different from $φ(10),$ as it does not include $3$ or $9.$

My hope is to show that the real value can be no less than half expected value (φ(n)/q), though I don't know if this is true.

Thanks in advance for any help you can provide.

  • $\begingroup$ Just to see if I got it right. You have a prime $p$, and a natural number $n$, with $p < \sqrt{n}$. You want to show that $\{ x : 0 \le x < n, \gcd(x, p n) = 1 \}$ has no more than $\phi(pn)/p$ elements? $\endgroup$ Commented Feb 20, 2017 at 8:26
  • $\begingroup$ Almost- I'm trying to show that it has more than φ(pn)/2p elements (or no less than φ(pn)/(2p-ε), if you prefer). Everything else here is correct. $\endgroup$
    – SDhn2a
    Commented Feb 20, 2017 at 16:24
  • 1
    $\begingroup$ Which is the relationship of this question with Goldbach conjecture? $\endgroup$ Commented Feb 15, 2020 at 16:54

2 Answers 2


$\phi(p) = p-1$ (for $p$ prime) and $\phi$ is multiplicative between coprime numbers, so $\phi(pn)=(p-1)\phi(n)$. Additionally of the totatives of $n$ we will only lose multiples of $p$, and only those that are also coprime to $n$ of course. So the value you are seeking should be no less than $\phi(n) -\frac {n(p-1)}p $ as I understand your question. Of course for $n$ odd and $p=2$ this could be large drop... say $n=15, p=2$ we go from $(1,2,4,7,8,11,13,14)$ to $(1,7,11,13)$ but the overlap of numbers already covered by the prime factors of $n$ does appear to keep the total loss limited to no more than half of $\phi(n)$

  • $\begingroup$ This is useful, but I think you misunderstood my question slightly: Here you compare the totient function of n to that of pn. What I am trying to do is compare the totient function of pn to the number of integers coprime to pn (not coprime to n) less than n, which is not necessarily equal to φ(n). $\endgroup$
    – SDhn2a
    Commented Feb 20, 2017 at 6:13
  • $\begingroup$ Hmm, I see, made some updates see if that is any better. $\endgroup$
    – Joffan
    Commented Feb 20, 2017 at 6:24
  • $\begingroup$ Thanks, this is much better. Though can you think of any way one might build on the "does appear..." in the last line? I'm kind of assuming the statement to be true, but the crux of the issue is that I can't think how I might go about proving it. $\endgroup$
    – SDhn2a
    Commented Feb 20, 2017 at 6:35

Let it be some positive integer $n$, and some prime number $q<n$ such that $\gcd\left(q,n\right)=1$

Let it be $S=\left\{ x\,:\,0\leq x\leq n,\,\gcd\left(x,qn\right)=1\right\}$

In order to prove that $\mid S\mid>\frac{\varphi\left(qn\right)}{2q}$, we can divide the problem in two cases: $n$ being prime and $n$ being composite.

- Solution for $n$ being some prime number

If $n=p$, where $p$ is some prime number, and $q<p$, then to get the elements of $S$ we need to substract from $\varphi\left(p\right)$ those numbers that are multiples of $q$; as there are only $\lfloor\frac{p}{q}\rfloor$ numbers less than $p$ are relatively prime to $p$ and not relatively prime to $qp$, we have that

$$\mid S\mid=\varphi\left(p\right)-\lfloor\frac{p}{q}\rfloor$$

As $q\nmid p$, we can affirm that


And subsequently we get that

$$\mid S\mid\geq\varphi\left(p\right)-\frac{\varphi\left(p\right)}{q}$$

Operating, we get that

$$\mid S\mid\geq\varphi\left(p\right)\left(1-\frac{1}{q}\right)$$

$$\mid S\mid\geq\varphi\left(p\right)\left(\frac{q-1}{q}\right)$$

As $\gcd\left(q,p\right)=1$, and applying the multiplicative properties of $\varphi\left(n\right)$, we get that


Therefore, for $n$ being some prime number,

$$\mid S\mid\geq\frac{\varphi\left(qn\right)}{q}>\frac{\varphi\left(qn\right)}{2q}$$

- Solution for $n$ being some composite number

If $n$ is some composite number, then less than $\lfloor\frac{n}{q}\rfloor$ numbers less than $n$ are relatively prime to $n$ and not relatively prime to $qn$; concretely, the multiples of $q$ and each prime factor of $n$ could be double-excluded by $\varphi\left(n\right)$ and $\frac{n}{q}$, and therefore need to be added once if necessary. Therefore,

$$\mid S\mid=\varphi\left(n\right)-\lfloor\frac{n}{q}\rfloor+\sum_{p\mid n}\left(\lfloor\frac{n}{qp}\rfloor\right)$$

Where $\sum_{p\mid n}\left(\lfloor\frac{n}{qp}\rfloor\right)$ counts the common multiples of $q$ and each prime factor of $n$, which already are double excluded by $\varphi\left(n\right)$ and $\frac{n}{q}$.

We have that


$$\sum_{p\mid n}\left(\lfloor\frac{n}{qp}\rfloor\right)\geq\sum_{p\mid n}\left(\frac{n-\left(q-1\right)p}{qp}\right)$$


$$\sum_{p\mid n}\left(\frac{n-\left(q-1\right)p}{qp}\right)=\sum_{p\mid n}\left(\frac{n}{qp}-1+\frac{1}{q}\right)$$

Thus, we can affirm that

$$\mid S\mid>\varphi\left(n\right)-\frac{n-1}{q}+\sum_{p\mid n}\left(\frac{n}{qp}\right)-\omega\left(n\right)+\frac{\omega\left(n\right)}{q}$$

Where $\omega\left(n\right)$ counts the number of distinct prime divisors of n.

Operating, we get that

$$\mid S\mid>\varphi\left(n\right)-\frac{n}{q}\left(1-\sum_{p\mid n}\left(\frac{1}{p}\right)\right)+\frac{1}{q}-\omega\left(n\right)+\frac{\omega\left(n\right)}{q}$$

For $\omega\left(n\right)>1$, it is easy to show that

$$\prod_{p\mid n}\left(\frac{p-1}{p}\right)-\frac{1}{n}\geq1-\sum_{p\mid n}\left(\frac{1}{p}\right)$$


$$\mid S\mid>\varphi\left(n\right)-\frac{n}{q}\left(\prod_{p\mid n}\left(\frac{p-1}{p}\right)-\frac{1}{n}\right)+\frac{1}{q}-\omega\left(n\right)+\frac{\omega\left(n\right)}{q}$$

As $\varphi\left(n\right)=n\prod_{p\mid n}\left(\frac{p-1}{p}\right)$, we have that

$$\mid S\mid>\varphi\left(n\right)-\frac{\varphi\left(n\right)}{q}+\frac{2}{q}-\omega\left(n\right)\left(1-\frac{1}{q}\right)$$


$$\mid S\mid>\varphi\left(n\right)\left(\frac{q-1}{q}\right)+\frac{2}{q}-\omega\left(n\right)\left(\frac{q-1}{q}\right)$$

$$\mid S\mid>\varphi\left(n\right)\left(\frac{\varphi\left(q\right)}{q}\right)+\frac{2}{q}-\omega\left(n\right)\left(\frac{\varphi\left(q\right)}{q}\right)$$

As $\gcd\left(q,n\right)=1$, and applying the multiplicative properties of $\varphi\left(n\right)$, we have that



$$\mid S\mid>\frac{\varphi\left(qn\right)+2}{q}-\omega\left(n\right)\left(\frac{\varphi\left(q\right)}{q}\right)$$

As the rate of growth of $\omega\left(n\right)$ is much lesser than the rate of growth of $\frac{\varphi\left(n\right)}{2}$, then we can affirm that, excepting the case $n=6$, which can be verified manually to fulfill the theorem,


Then we have that


And subsequently


Therefore, for n being some composite number,

$$\mid S\mid>\frac{\varphi\left(qn\right)}{2q}$$

And the theorem is proved.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .