Let $\phi(\cdot)$ be the Euler totient function, and let $n=p_1^{k_1}\cdots p_s^{k_s}$ be the prime factorization of $n\in \mathbb{N}$. The well-known Euler's product formula states that $\phi(n)=n(1-\frac{1}{p_1})\cdots(1-\frac{1}{p_s})$. For some fixed positive integer $a\leq n$, let $\phi(n,a)$ denote the number of positive integers which are less than $a$ but coprime to $n$. My question is that whether there is some formula for computing $\phi(n,a)$.
Euler's Totient Function
Xueyi Huang
- 377
- 2
- 8