# Totient function works well!

Suppose we take a number $n$. We choose primes $p_1, p_2, p_3, \cdots, p_k$ such that $\forall$ $1\leq i\leq k$, $GCD(p_i,n)$ is not necessarily equal to $p_i$; it can be $1$ as well. In other words, they must not necessarily divide $n$ or be coprime to it.

Let $n$ be any big number (say $>10000)$ and the primes be within $15$ suppose. In this case, if we want to find the count of numbers from $1$ to $n$ which are coprime to each and every $p_i$, we can apply the Euler's Phi function in something as this way : ${n \prod{(1-\frac{1}{p_i})}}$ and then we get the count. It's just the best approximation and is quite near to the count. In fact, it's just $±1$ distance apart I think. Not exact if the primes don't divide $n$

Can anyone explain me the reason behind it? Note that the primes may necessarily not divide $n$. Do provide a good proof

• Your formula cannot possibly work because you have put no restrictions on the primes you choose. Those are just any set of primes. There is no relationship between those primes and n, so clearly you cannot expect that formula to hold (or to be an approximation). – Ant Mar 7 '17 at 8:09
• @Ant I have edited the question well – Mathejunior Mar 7 '17 at 8:14

Every $p_i$ -th number is divisible by $p_i$. So an estimate of the numbers $\lt n$ not divisible by $p_i$ is : $n(1-\frac{1}{p_i})$. What remains you can roughly multiply by $1-\frac{1}{p_{i+1}}$ to get an estimate of numbers coprime to both $p_i$ and $p_{i+1}$. This way you arrive at your formula.