I am trying to figure out how to interpret the following formula using probability:


The left hand side is clearly the probability that a random chosed number from $1\leq a\leq n$ is coprime to $n$.

I am told that the right hand side insists that our number is not divisible by any prime divisors of $n$. Why is this so?


2 Answers 2


Coprime means, not sharing any factor other than 1 in common. Therefore, to count the number of coprimes less than N, is exactly equal to, N times the product of 1 minus 1 pth, where p ranges over the prime factors of N. A number in general, is coprime to N, if it is in one of that many remainders mod N.


Because of $1\le \phi(n)\le n$ we have $0<\frac{\phi(n)}{n}\le 1$. Hence the RHS satisfies $$ 0<\prod_{p|n}(1-\frac{1}{p})\le 1. $$ So the claim about divisibility by primes is clear.

  • $\begingroup$ Ok, the RHS is between 0 and 1. Not sure why this implies the claim about divisibility of primes. $\endgroup$ Commented Mar 9, 2019 at 18:14
  • $\begingroup$ Because a number between $0$ and $1$ cannot be divided by any prime. $\endgroup$ Commented Mar 9, 2019 at 19:05
  • $\begingroup$ Yes, but why are the two sides equal? We just have that they both are between 0 and 1. $\endgroup$ Commented Mar 9, 2019 at 19:21
  • 2
    $\begingroup$ The two sides are equal because of the product formula you wrote. For a reference for this formula see here - using exactly the probability argument you were talking about. $\endgroup$ Commented Mar 9, 2019 at 19:35
  • 1
    $\begingroup$ In that proof, why is the probability that m is divisible by $p$ $1/p$? $\endgroup$ Commented Mar 9, 2019 at 20:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .