Is there some way to use Euler's Totient function to represent the amount of odd composites that share a factor with integer $n$ less than $n$? For instance,

$n-\phi(n)$ represents the total amount of composites less than $n$ that share a factor with $n$. How might I reduce this to only the odd composites?

  • $\begingroup$ For odd numbers it's still $n-\phi(n)$. For $n=2^rp$ with $p$ prime and $r\ge 1$, it's $2^{r-1}$. $\endgroup$
    – Mastrem
    Mar 23, 2017 at 21:14
  • $\begingroup$ Can you use the prime counting function $\pi(n)$? If so, you might have to adjust by $+1$ or $-1$. $\endgroup$
    – Bob Happ
    Mar 23, 2017 at 21:23

1 Answer 1


If $n$ is even, then no even number is relatively prime to $n,$ so the $n-\phi(n)$ numbers not-relatively-prime-to-n include the $n/2$ even numbers, so in that case, your number is: $$n/2 - \phi(n).$$

If $n$ is odd, then the number of even numbers not-relatively-prime to $n$ is the same as the number of number $\leq \lfloor \frac{n}{2}\rfloor$ not-relatively-prime to $n.$ Now the number of integers relatively prime to $n$ and less than or equal to $n/2$ is $\Phi(n, \lfloor \frac{n}{2}\rfloor),$ where $\Phi(n, x)$ is defined (see this question) as $$\Phi(n,x)=x-\sum_i\lfloor{x/{p_i}}\rfloor+\sum_{i \lt j}\lfloor x/{p_ip_j}\rfloor-\cdots+(-1)^{k}\lfloor x/{n}\rfloor,$$ and thus the number of even numbers not-relatively-prime-to-n equals $$E(n) = \lfloor \frac{n}{2}\rfloor - \Phi(n, \lfloor \frac{n}{2}\rfloor).$$ So, the number of odd non-relativel-prime integers is $$n-\phi(n) - E(n).$$ I am not sure if you can simplify this further.

  • $\begingroup$ Can't you simplify $E(n)$ to $\sum_i\lfloor{x/{p_i}}\rfloor+\sum_{i \lt j}\lfloor x/{p_ip_j}\rfloor-\cdots+(-1)^{k}\lfloor x/{n}\rfloor$? $\endgroup$ Mar 23, 2017 at 21:41
  • $\begingroup$ @LinusRastegar Indeed! I was wondering whether one can avoid alternating sums altogether ... $\endgroup$
    – Igor Rivin
    Mar 23, 2017 at 21:46
  • $\begingroup$ If $x = \lfloor \frac{n}{2}\rfloor$ I think there is a way to simplify $E(n)$ further because this means that $\Phi(n,x)$ can somehow be related the product of $1-\frac{1}{p_i}$, as the question you linked claimed with a simpler version of $\Phi$. $\endgroup$ Mar 23, 2017 at 21:57
  • $\begingroup$ @LinusRastegar Yes, but it is not clear that there is a closed form. In fact, each $\lfloor \frac{x}{p_1 \dots p_k}\rfloor$ equals $$\lfloor \frac{n}{2 p_1 \dots p_k}\rfloor,$$ but the trick is getting rid of the floors... $\endgroup$
    – Igor Rivin
    Mar 23, 2017 at 21:59
  • $\begingroup$ You could split the floors into two separate cases. $\lfloor \frac{n}{2}\rfloor$ could be rewritten as $\frac{n}{2}$ when $n$ is even and $\frac{n}{2} - 1$ when $n$ is odd. $\endgroup$ Mar 23, 2017 at 23:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.