1
$\begingroup$

This question already has an answer here:

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)$.

$\endgroup$

marked as duplicate by Alexey Ustinov, Community Dec 2 '16 at 13:15

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 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$ – KConrad Dec 2 '16 at 10:29
1
$\begingroup$

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.$)

$\endgroup$

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