[proofplan]
The proof has two independent parts, corresponding to the two equalities in the statement. The first equality is a direct combinatorial description of the integers in $[1, X]$ coprime to $P$: such an integer has no prime factor $\leq \sqrt{X}$, hence is either $1$ or a prime in $(\sqrt{X}, X]$. The second equality is a Möbius inversion: we express the indicator $\mathbb{1}_{\gcd(n, P) = 1}$ via the Möbius identity $\sum_{d \mid n} \mu(d) = \mathbb{1}_{n = 1}$, swap the order of summation, and count the multiples of $d$ in $[1, X]$ as $\lfloor X / d \rfloor$.
[/proofplan]
[step:Identify the integers in $[1, X]$ coprime to $P$ as $1$ together with the primes in $(\sqrt{X}, X]$]
Let $S := \{1 \leq n \leq X : \gcd(n, P) = 1\}$. We show
\begin{align*}
S = \{1\} \cup \{p \text{ prime} : \sqrt{X} < p \leq X\}.
\end{align*}
Since $P = \prod_{p \leq \sqrt{X}} p$ is the product of all primes $\leq \sqrt{X}$, for any $n \geq 1$ we have
\begin{align*}
\gcd(n, P) = 1 \iff n \text{ has no prime factor } \leq \sqrt{X}.
\end{align*}
Consider $n \in S$. If $n = 1$, it has no prime factors and so lies in $S$. If $n \geq 2$, let $q$ be the smallest prime factor of $n$; then $q > \sqrt{X}$ by the previous equivalence. Since $q \mid n$ and $n \leq X$, we have $q \leq n \leq X$. If $n \neq q$, then $n / q \geq 2$, so $n \geq 2q > 2\sqrt{X}$, and moreover $n$ has another prime factor $q' \geq q > \sqrt{X}$; then $n \geq q q' > (\sqrt{X})^2 = X$, contradicting $n \leq X$. Hence $n = q$ is itself a prime in the range $(\sqrt{X}, X]$.
Conversely, $1$ lies in $S$ (since $\gcd(1, P) = 1$), and any prime $p$ with $\sqrt{X} < p \leq X$ has no prime factor $\leq \sqrt{X}$ (its only prime factor is $p > \sqrt{X}$), hence lies in $S$.
Counting the two parts gives
\begin{align*}
\#S = 1 + (\pi(X) - \pi(\sqrt{X})) = \pi(X) - \pi(\sqrt{X}) + 1,
\end{align*}
which is the first equality in the statement.
[/step]
[step:Rewrite the coprimality indicator using the Möbius identity]
We apply the Möbius identity
\begin{align*}
\sum_{d \mid m} \mu(d) = \mathbb{1}_{m = 1}
\end{align*}
valid for every integer $m \geq 1$ (see [Möbius Inversion Formula](/theorems/1749) and the underlying identity). Taking $m = \gcd(n, P)$, we have $\gcd(n, P) = 1$ if and only if the indicator equals $1$. Hence
\begin{align*}
\mathbb{1}_{\gcd(n, P) = 1} = \sum_{d \mid \gcd(n, P)} \mu(d).
\end{align*}
The condition $d \mid \gcd(n, P)$ is equivalent to $d \mid n$ and $d \mid P$, so summing over $n \in \{1, \ldots, \lfloor X \rfloor\} \cap \mathbb{Z}_{\geq 1}$ — equivalently over integers $n$ with $1 \leq n \leq X$ — we obtain
\begin{align*}
\#S = \sum_{1 \leq n \leq X} \mathbb{1}_{\gcd(n, P) = 1} = \sum_{1 \leq n \leq X} \sum_{\substack{d \mid n \\ d \mid P}} \mu(d).
\end{align*}
[guided]
The Möbius identity $\sum_{d \mid m} \mu(d) = \mathbb{1}_{m = 1}$ is the standard device for detecting coprimality. We use it with $m = \gcd(n, P)$: $\gcd(n, P) = 1$ precisely when the indicator $\mathbb{1}_{m = 1}$ equals $1$, so
\begin{align*}
\mathbb{1}_{\gcd(n, P) = 1} = \sum_{d \mid \gcd(n, P)} \mu(d).
\end{align*}
Why rewrite the indicator this way? Because the right-hand side is a sum we can rearrange: a divisor $d$ of $\gcd(n, P)$ is exactly an integer $d$ that divides both $n$ and $P$, and decoupling these two divisibility conditions will let us swap the order of summation in the next step. The Möbius function $\mu$ is the ingredient that makes the identity work: it encodes the inclusion-exclusion over prime factors of $m$.
Summing over $1 \leq n \leq X$ (where $n$ ranges over positive integers),
\begin{align*}
\#S = \sum_{1 \leq n \leq X} \mathbb{1}_{\gcd(n, P) = 1} = \sum_{1 \leq n \leq X} \sum_{\substack{d \mid n \\ d \mid P}} \mu(d).
\end{align*}
This is the expression we will manipulate by Fubini-style reordering in the next step.
[/guided]
[/step]
[step:Swap the order of summation and count multiples of $d$ in $[1, X]$]
We interchange the order of the double sum. The region of summation $\{(n, d) : 1 \leq n \leq X, \ d \mid n, \ d \mid P\}$ is finite, so the swap is valid and produces
\begin{align*}
\#S = \sum_{1 \leq n \leq X} \sum_{\substack{d \mid n \\ d \mid P}} \mu(d) = \sum_{d \mid P} \mu(d) \cdot \#\{1 \leq n \leq X : d \mid n\}.
\end{align*}
For each positive integer $d$, the multiples of $d$ in $[1, X]$ are $d, 2d, 3d, \ldots, \lfloor X/d \rfloor d$, so
\begin{align*}
\#\{1 \leq n \leq X : d \mid n\} = \left\lfloor \frac{X}{d} \right\rfloor.
\end{align*}
Substituting,
\begin{align*}
\#S = \sum_{d \mid P} \mu(d) \left\lfloor \frac{X}{d} \right\rfloor.
\end{align*}
[/step]
[step:Combine the two identities to obtain Legendre's formula]
From the first step, $\#S = \pi(X) - \pi(\sqrt{X}) + 1$. From the third step, $\#S = \sum_{d \mid P} \mu(d) \lfloor X/d \rfloor$. Equating,
\begin{align*}
\pi(X) - \pi(\sqrt{X}) + 1 = \sum_{d \mid P} \mu(d) \left\lfloor \frac{X}{d} \right\rfloor,
\end{align*}
which is Legendre's formula.
[/step]
