### Interesting formulas and exercises in number theory

In this post I would like to introduce some interesting exercises in number theory, along with some curious formulas and identities for some number-theoretic functions.

The following list includes the notations used in this post: `φ(n)` is the Euler's totient function`J_k(n)` is the Jordan's totient function`σ_k(n)` is the Divisor (sigma) function`μ(n)` is the Möbius function`c_q(n)` is the Ramanujan's sum function

# Conditional Euler's totient function Given a boolean function `f(x)`, let `a(n)` be the number of integers `k` in the range `[1, n]` for which `f(gcd(n, k))` is true.

For example, if `f(x)` returns a true value only when `x=1`, then the problem reduces to the Euler's totient function: `a(n) = φ(n)`.

This is interesting, because if the prime factorization of `n` can be computed, then we can efficiently compute `φ(n)` using the following formula:

`φ(n) = n * \prod_{p|n} (1 - 1/p)`

where the product is taken over the distinct prime factors of `n`.

Now con…

The following list includes the notations used in this post: `φ(n)` is the Euler's totient function`J_k(n)` is the Jordan's totient function`σ_k(n)` is the Divisor (sigma) function`μ(n)` is the Möbius function`c_q(n)` is the Ramanujan's sum function

# Conditional Euler's totient function Given a boolean function `f(x)`, let `a(n)` be the number of integers `k` in the range `[1, n]` for which `f(gcd(n, k))` is true.

For example, if `f(x)` returns a true value only when `x=1`, then the problem reduces to the Euler's totient function: `a(n) = φ(n)`.

This is interesting, because if the prime factorization of `n` can be computed, then we can efficiently compute `φ(n)` using the following formula:

`φ(n) = n * \prod_{p|n} (1 - 1/p)`

where the product is taken over the distinct prime factors of `n`.

Now con…