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)$.
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ You should say what kind of "formula" you want. The rule of being $< a$ and relatively prime to $n$ without any relation between $a$ and $n$ other than $a \leq n$ is not going to make $\varphi(n,a)$ into a nice function (e.g., usually not multiplicative in $n$). Do you have any basis for believing there should be a nice formula of some kind? $\endgroup$– KConradCommented Dec 2, 2016 at 10:29
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
The formula is given in this question, while the answers thereto discuss the accuracy of the obvious approximation (that this is like $a \phi(n)/n.$)
answered Dec 2, 2016 at 10:33