Number of positive integers $\le n$ which are a multiple of $p$

Question

I was trying to understand the proof of the following formula:

$$ \varphi(n)= n\prod_{\substack{p \text{ prime }\ p \vert n}} \left( 1- \frac{1}{p}\right) $$

Using inclusion-exclusion.

What we want is the number of positive elements $\le$ that are coprime to $n$, Suppose $n=\prod_{i=1}^{k}p_{i}^{e_{i}}$ is the unique prime factsization of $n$ and let let $A_i$ be the set of such positive integers that $i$ prime number does not divide them with $1\le i\le k$ and the primes are all a factor of $n$,then we want $$\bigcap_{i=1}^{k} \left|A_{i}\right|$$

But here we need to know the number of positive integers $\le n$ which are a multiple of $p$,this is given by $$\lfloor \frac{n}{p} \rfloor$$ Where $\lfloor \rfloor$ denoted the floor function.

But how one can show that?

Answer 1

It's assumed to be obvious and self explanitory.

The multiples of $p \le n$ are $1p, 2p, 3p, ....., kp\le n$ for some $k$. That means that there $k$ such multiples and $kp \le n < (k+1)p$. So $k \le \frac pn < k+1$.

So $k = \lfloor \frac np \rfloor$.

Answer 2

Consider the sequence

$$p, 2p, 3p, \dots, pk$$

This is an AP with initial term $p$ and common difference $p$.

The $k$^th term is given by $pk$.

We want $pk \le n$.

$\therefore, k \le {n \over p} \implies k = \lfloor {n \over p} \rfloor$

Answer 3

The following approach is somewhat defective because it makes no attempt to address the OP's question(s), which other reactions have done. Further this approach is intuitive only, with the formality of math all but discarded.

To prove (informally - via intuition only):

$$\varphi(n) = n \times \prod_{p ~\text{prime}~ p|n} \left(1 - \frac{1}{p}\right).$$

Each prime # is relatively prime to all the others. Very informally, one can construe divisibility by one prime # to be an independent event with respect to divisibility by another prime #.

For example, in the set $\{1,2,\cdots, 100\}$
the chance that a random # from this set is divisible by 2 is $\frac{1}{2}.$
If you restrict the set, and only consider those #'s that are
multiples of 5 (i.e. $\{5, 10, \cdots, 100\}$), then the chance
that a random # from this subset is (also) divisible by 2 is
(still) $\frac{1}{2}.$

Extending the analogy, the chance that a random # from the set $\{2,4,\cdots, 100\}$ is relatively prime to $5$ is $\frac{4}{5}.$

Note: this intuition critically depends on the fact that $100$ is a common multiple of $2$ and $5$.

Let $U \equiv \{1, 2, \cdots, n\}.$
Let $P \equiv \{p_1, p_2, \cdots, p_k\}$ be the complete list
of all distinct primes that divide $n$.

Let $E_p ~: p \in P$ denote the event that a given random # in $U$ is relatively prime to $p$.
Then chance of event $E_p$ occurring is $\left(1 - \frac{1}{p}\right).$

In order for any # $u \in U$ to be relatively prime to $n$,
it must be relatively prime to each $p \in P$.

Since (intuitively) $E_{p_1}, E_{p_2}, \cdots, E_{p_k}$ are all independent events, the chance that a # chosen at random from $U$ will be relatively prime to $n$ is therefore,

$$\prod_{p ~\text{prime}~ p|n} \left(1 - \frac{1}{p}\right).$$

Since $U$ contains exactly $n$ numbers, the formula is intuitively justified.

---

Addendum
After some time, I became bothered by the informality of my approach, and tried to formalize it into a proof. After a few hours, I decided to research the problem for insights.

I actually found the proof handed to me, as a result of the ideas mentioned at
https://en.wikipedia.org/wiki/Euler%27s_totient_function $~~~$ and
https://en.wikipedia.org/wiki/Chinese_remainder_theorem

These articles really left me nothing to prove, so I can at least summarize the ideas. From what I read, it seems like there are only two ways of proving it.

One way is to use the inclusion exclusion principle (https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle). I prefer to avoid this approach.

The alternative approach is described below.

---

$\underline{\text{General Terminology}}$

If $V$ is any set with a finite # of elements,
let $|V|$ denote the number of elements in $V$.

For any positive integer $k > 1$, let $A_k$ denote the set $\{0, 1, 2, \cdots, (k-1)\}.$

For any positive integer $k > 1$, let $\overline{A_k}$ denote the set $\{i ~: i \in A_k, ~i ~\text{relatively prime to} ~k\}.$

$\underline{\text{The Chinese Remainder Theorem}}$

Let $n_1, n_2, \cdots, n_k$ each be a positive integer $> 1$
where these $k$ integers are all pairwise coprime.

Let $N = \prod_{i=1}^k n_i.$

Let $a_1, a_2, \cdots, a_k$ be any integers such that
$a_1 \in A_{n_1}, a_2 \in A_{n_2}, \cdots, a_k \in A_{n_k}$.

Then the following system of $k$ congruency equations will have exactly one solution in $A_N$:

$\displaystyle ~~~~~~~~x \equiv a_1 \pmod{n_1}$
$\displaystyle ~~~~~~~~x \equiv a_2 \pmod{n_2}$
$\displaystyle ~~~~~~~~~~~ \cdots$
$\displaystyle ~~~~~~~~x \equiv a_k \pmod{n_k}$

In my opinion, the corresponding wikipedia page cited above proves this result.

The remainder of the proof will only need the special case of the Chinese Remainder Theorem where $k=2.$

---

$\underline{\text{To prove:}}$

Given, that $m,n$ are relatively prime positive integers, each $> 1.$ Then $\varphi(m \times n) = [\varphi (m)] \times [\varphi (n)].$

---

$\underline{\text{Proof:}}$

Let $F ~: ~\left(A_m \times A_n\right) \to A_{(mn)}$ be specified as follows:

Given $~a \in A_m, ~b \in A_n,~$ by the Chinese Remainer Theorem,
there exists a unique $x \in A_{(mn)}$
such that $~x \equiv a \pmod{m} ~\text{and} ~x \equiv b \pmod{n}.$
Then $F(a,b) = x.$

Suppose that $F(a_1, b_1) = x = F(a_2, b_2).$
Then, $~\{a_1 \equiv x \equiv a_2 \pmod{m} ~\text{and} ~b_1 \equiv x \equiv b_2 \pmod{n}\} ~\Rightarrow$ $\{a_1 = a_2 ~\text{and} ~b_1 = b_2\}.~$ Thus $F$ is an injection.

Therefore, since $|A_{(mn)}| = |A_m| \times |A_n|,~$ $F$ is also a surjection. Therefore, $F$ is a bijection.

Since $~\varphi(mn) = |\overline{A_{(mn)}}|, ~\varphi(m) = |\overline{A_m}|, ~\text{and} ~\varphi(n) = |\overline{A_n}|,$
it remains to show that $|\overline{A_{(mn)}}| = |\overline{A_m}| \times |\overline{A_n}|.$

If $~a \in \overline{A_m}, ~b \in \overline{A_n} ~\text{and} ~F(a,b) = x,$
then $~\{x \equiv a \pmod{m} ~\text{and} ~x \equiv b \pmod{n}\} ~\Rightarrow$
$\{x ~\text{is relatively prime to both} ~m ~\text{and} ~n\} ~\Rightarrow$
$x ~\text{is relatively prime to} ~(mn) ~\Rightarrow ~x \in \overline{A_{(mn)}}.$

Conversely, if $~F(a,b) = x~$ and $~x \in \overline{A_{(mn)}}$
then $~\{x ~\text{is relatively prime to} ~(mn)\} ~\Rightarrow$
$\{x ~\text{is relatively prime to both} ~m ~\text{and} ~n\}.$
Further $~x \equiv a \pmod{m}~$ and $~x \equiv b \pmod{n}.~$
Therefore, $~a \in \overline{A_m}~$ and $~b \in \overline{A_n}.$

Thus, if $G$ is the same map as $F$ but with its domain restricted to $\left(\overline{A_m} \times \overline{A_n}\right)$
then $\{$the range of $~G\} \subseteq \overline{A_{(mn)}}~$ and $\overline{A_{(mn)}} \subseteq~$ $\{$the range of $~G\}.$
Therefore, $\{$the range of $~G\} = \overline{A_{(mn)}}.$
Therefore, if $~G$ is regarded as a map from $~\left(\overline{A_m} \times \overline{A_n}\right) \to \overline{A_{(mn)}}$
then $G$ is a surjection onto $\overline{A_{(mn)}}$.

Further, the property of $G$ being an injection is inherited from $F$.
Therefore, $~G$ is a bijection from $~\left(\overline{A_m} \times \overline{A_n}\right) \to \overline{A_{(mn)}}.$
Therefore, $|\overline{A_{(mn)}}| = |\overline{A_m}| \times |\overline{A_n}|.$

---

$\underline{\text{To prove:}}$

$$\varphi(n) = n \times \prod_{p ~\text{prime}~ p|n} \left(1 - \frac{1}{p}\right).$$

---

$\underline{\text{Proof:}}$

Let the prime factorization of $n$ be given by

$$ \prod_{i=1}^k p_i^{(\alpha_i)}.$$

The proof will be by induction on $k$.

For $j \in \{1,2,\cdots, k\},$

let $\displaystyle r_j = \prod_{i=1}^j p_i^{(\alpha_i)}~$ and

let $\displaystyle s_j = \prod_{i=1}^j \left(1 - \frac{1}{p_i}\right).$

Thus, $~r_1 = p_1^{\alpha_1}, ~r_k = n,~$ and the problem reduces to showing
that for all $~j \in \{1,2,\cdots, k\}, \varphi(r_j) = r_j \times s_j.$

In the "Value for a prime power argument" section of https://en.wikipedia.org/wiki/Euler%27s_totient_function it is proven that for any prime $p$ and positive integer $\alpha$,

$$\varphi\left(p^{\alpha}\right) = p^{\alpha} \times \left(1 - \frac{1}{p}\right).$$

Therefore, it is immediate that $\varphi(r_1) = r_1 \times s_1.$

Inductively assume that for one specific $J \in \{1,2,\cdots (k-1)\},$

$\varphi\left(r_j\right) = r_j \times s_j.$

Then:

• from the definition, $r_{(J)}$ is relatively prime to $[p_{(J+1)}]^{\alpha_{(J+1)}}$

• $\displaystyle \varphi\left\{[p_{(J+1)}]^{\alpha_{(J+1)}}\right\} = \left\{[p_{(J+1)}]^{\alpha_{(J+1)}}\right\} \times \left(1 - \frac{1}{p_{(J+1)}}\right).$

• From the previous analysis, [re $\varphi(mn) = \varphi(m) \times \varphi(n)$]
  
  $\displaystyle \varphi\left[r_{(J+1)}\right] = [r_j \times s_j] \times \left\{[p_{(J+1)}]^{\alpha_{(J+1)}}\right\} \times \left(1 - \frac{1}{p_{(J+1)}}\right)$

• $= r_{(J+1)} \times s_{(J+1)}.$