The probability that a random integer is prime to a given integer $m$ is $\frac{\phi(m)}m$?

Question

Let $N_m(x)$ denote the number of positive integers not exceeding $x$ that are relatively prime to $m$ , then how to prove that $\lim_{x \to \infty} \dfrac{N_m(x)}x=\dfrac{\phi (m)}m$ , where $\phi(.)$ is the Euler's phi function ?

Answer 1

Some hints

1. There are exactly $\varphi(m)$ integers less than $m$ and coprime to $m$
2. For every $k$ there are exactly $\varphi(m)$ integers in the interval $[km,(k+1)m-1]$ coprime to $m$, Indeed every integer $i\in [km,(k+1)m-1]$ can be written in the form $i=km+t$ with $0\leq t<m$ and $\gcd(t,m)=\gcd(i,m)$ so every coprime $i$ gives us a com prime $t$ less than $m$ and the converse still correct, so the number of comprime integers with $m$ in the two intervals is the same.
3. Given a large integer $x=Km+r$ with $r\leq m$ we partition the interval $[0,x]$ in $k+1$ intervales: $$[0,m-1],[m,2m-1],[2m,3m-1],\cdots\cdots\cdots,[(K-1)m,Km-1],[Km,Km+r] $$ the first $k$ intervals contain each $\varphi(m)$ coprime to $m$ and the last inteval contain no more than $\varphi(m)$ so: $$K\varphi(m)\leq N_m(x)\leq (K+1)\varphi(m) $$

and don't forget that :$K=\left \lfloor\frac{x}{m}\right\rfloor$ and $\lim_{x\to \infty} \frac{K}{x}=\frac{1}{m}$

Answer 2

Hint: $n$ is relatively prime to $m$ iff $n \mod m$ is.

Answer 3

This question can be answered rigorously using the Wiener-Ikehara Theorem. Suppose the prime factorization of $m$ is $$m = \prod_p p^v.$$ Suppose we set $$\Lambda(s) = \sum_{\gcd(n,m)=1} \frac{1}{n^s}.$$

By inspection we get the following Euler product for $\Lambda(s)$: $$\Lambda(s) = \zeta(s) \prod_p \left(1-\frac{1}{p^s}\right).$$

Then by the Wiener-Ikehara theorem we have that $$\sum_{n\le x, \; \gcd(m,n)=1} 1 \sim \prod_p \left(1-\frac{1}{p}\right) \times x.$$

It follows that $$\frac{1}{x} \sum_{n\le x, \; \gcd(m,n)=1} 1 \sim \prod_p \left(1-\frac{1}{p}\right) = \frac{\varphi(m)}{m}.$$

Remark. The variable $p$ in the above ranges over the prime factors of $m$ (as opposed to all primes).