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

  • $\begingroup$ 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). $\endgroup$ – Ant Mar 7 '17 at 8:09
  • $\begingroup$ @Ant I have edited the question well $\endgroup$ – Mathejunior Mar 7 '17 at 8:14

Your formula is based on the fact that generally every say third number is divisible by 3.
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.

There can be no other hidden effects because this is exactly what your formula does.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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