0

This is similar to the totient function, but obviously somewhat different. I would be interested to know if formulae exist for counting the positive odd integers and the positive even integers up to a given integer N that are relatively prime to N.

Maurice
  • 11
  • Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. – CrSb0001 Nov 17 '23 at 12:23
  • Euler's totient function counts all the positive integers, odd and even, up to a given integer N that are relatively prime to N. I am asking if there is a formula dealing with restricting the positive integers to either odd or even integers instead of all positive integers. – Maurice Nov 17 '23 at 12:35

2 Answers2

1

Let f(n) = count of all co-prime integers and g(n) = count of odd co-prime integers. If n is even then all co-prime numbers are odd, so f(n) = g(n).

For odd n: If k is co-prime to 2n then so is 2n-k, and both are odd. So exactly half the numbers co-prime to 2n are less than n, and they are all odd. So g(n) = f(2n) / 2 if n is odd.

(The proof may be a bit dodgy but the principle and the result are right).

gnasher729
  • 10,113
0

A little more generally. For an arithmetic function $f(n)$ and odd $n$ $$\sum_{{k=1}\\{k=odd}}^n f(gcd(n,k)) = \frac{1}{2}\cdot \left((f*\phi)(n)+f(n) \right)$$ and for even $n$ $$\sum_{{k=1}\\{k=odd}}^n f(gcd(n,k)) = (\phi*(L \cdot f)(n)$$ where $\phi$ is the totient function, $*$ is the Dirichlet convolution and $L(n)$ is $1$ for odd $n$ and $0$ for even $n$. Specially for $f(n)=e(n)$ where $e(n)$ is unit function, i.e. $e(n)1$ for $n=1$ and $e(n)=0$ for $n>1$. For odd $n$ $$\sum_{{k=1}\\{k=odd}\\{gcd(n,k)=1}}^n 1 = \frac{1}{2}\cdot(\phi(n)+e(n)))$$ and for even $n$ $$\sum_{{k=1}\\{k=odd}\\{gcd(n,k)=1}}^n 1 = \phi(n)$$

zhrd
  • 97