Let $x\geq 1$ and $\phi(x)$ be the Euler totient function. I want to show that $$\phi(x) = x\prod_{p| x}\bigg(1 - {1\over p}\bigg)$$
First, I looked at the case $x$ is prime. If $x$ is prime, then the only such $p$ that divides $x$ is $1$, so $x-1$ numbers are relatively prime to $x$. So $\phi(x) = x-1$ in this case.
I then tried to apply induction on $x$. The first case $\phi(1) = 1$ holds. So, suppose that $\phi(x) = x\prod_{p| x}\big(1 - {1\over p}\big)$ holds. Then show that $\phi(x+1) = (x+1)\prod_{p| {x+1}}\big(1 - {1\over p}\big)$
If $x+1$ is prime, then $\phi(x+1) = x$. Suppose that $x+1$ is not prime. Then the number of integers coprime to $x$ is given by the product formula, and since $\gcd(x, x+1) = 1$ for all $x\geq 1$, then $x$ is counted as well. So $$\phi(x+1) = x\prod_{p| x}\bigg(1 - {1\over p}\bigg) + 1$$ Which implies $\phi(x+1) = \phi(x) + 1 = \phi(x) + \phi(1)$. So it seems I want to show that in the case $x+1$ is not prime, $$\phi(x+1) = x\prod_{p| x}\bigg(1 - {1\over p}\bigg) + 1= (x+1)\prod_{p| {x+1}}\bigg(1 - {1\over p}\bigg)$$ And this is where I'm stuck. Am I even on the right track with applying induction?
By definition the Euler's totient function counts the positive integers up to a given integer $n\in \mathbb{N}$ that are relatively prime to $n$. Consequently, if $A = \{1,\cdots, n \}$, then $\phi (n) = | \{ a\in A:(a<n)\land (a\not| n) \} |$. What elements of the set $A$ divide $n$? If $ n = \prod_{i=1}^r p_i^{\alpha_i}$ is the prime factorization of $n$ (that is, $p_1$,...,$p_r$ are distinct prime numbers), then $p_i | n $. Therefore, $\phi(n)$ does not count these elements and all elements less than n that are divisible by them. Thus, we need to find the number of all elements up to n and which are not divisible by any of the numbers $p_1$,...,$p_r$ (i.e. $\phi(n)$). Thus, if $P_i = \{ p_i, 2p_i, 3p_i, \cdots, \frac{n}{p_i}p_i \}$ (obviously, $|P_i| = \frac{n}{p_i}$), then $$\phi(n) = | A \setminus \left( \bigcup_{i=1}^r P_i \right) |.$$
Let's find the cardinality by induction on i.
Let us denote by $A_1 = A\setminus P_1$ the set of elements of A that are not divisible by $p_1$. Then $$|A_1| = |A|-|P_1|=n-\frac{n}{p_1} = n \left( 1- \frac{1}{p_1}\right).$$
Now let $A_2= A\setminus (P_1\cup P_2) = A_1 \setminus (P_2 \setminus P_1)$ be the set of elements from A that are not divisible by either $p_1$ or $p_2$. Since $p_1$ and $p_2$ are coprime, the number of elements in $P_2$ that are not divisible by $p_1$ is $|P_2\setminus P_1 | = \frac{n}{p_2} - \frac{\frac{n}{p_2}}{p_1} = \frac{n}{p_2}\left( 1 - \frac{1}{p_1}\right)$ (in the previous step, replacing $n$ with $\frac{n}{p_2}$ we find the number of elements $P_2$ that are not divisible by $p_1$). Thus $$|A_2| = |A_1| - |P_2\setminus P_1| = n \left( 1- \frac{n}{p_1}\right) - \frac{n}{p_2}\left( 1 - \frac{1}{p_1}\right) = n\left( 1 - \frac{1}{p_1}\right) \left( 1 - \frac{1}{p_2}\right).$$
Let $A_3 = A\setminus(P_1\cup P_2 \cup P_3) = A_2 \setminus (P_3\setminus (P_1\cup P_2))$ be the set of elements from $A$ that are not divisible by any of $p_1$, $p_2$, $p_3$. For reasons similar to the previous step, we get that $|P_3\setminus (P_1\cup P_2)| = \frac{n}{p_3}\left( 1 - \frac{1}{p_1}\right) \left( 1 - \frac{1}{p_2}\right)$ (in the previous step, replacing $n$ with $\frac{n}{p_3}$ we find the number of elements $P_3$ that are not divisible by either $p_1$ or $p_2$). Thus $$|A_3| = n\left( 1 - \frac{1}{p_1}\right) \left( 1 - \frac{1}{p_2}\right) - \frac{n}{p_3}\left( 1 - \frac{1}{p_1}\right) \left( 1 - \frac{1}{p_2}\right) = n\left( 1 - \frac{1}{p_1}\right) \left( 1 - \frac{1}{p_2}\right)\left( 1 - \frac{1}{p_3}\right)$$
Suppose that $|A_{r-1} | = n\left( 1 - \frac{1}{p_1}\right)\cdots \left( 1 - \frac{1}{p_{r-1}}\right)$.
Let $A_r = A\setminus(P_1\cup \cdots \cup P_{r-1}) = A_{r-1} \setminus (P_r\setminus (P_1\cup \cdots \cup P_{r-1}))$ be the set of elements from $A$ that are not divisible by any of $p_1$, ..., $p_{r}$. Thus $$|A_r|= n\left( 1 - \frac{1}{p_1}\right)\cdots \left( 1 - \frac{1}{p_{r-1}}\right) - \frac{n}{p_r}\left( 1 - \frac{1}{p_1}\right)\cdots \left( 1 - \frac{1}{p_{r-1}}\right)= n\left( 1 - \frac{1}{p_1}\right)\cdots \left( 1 - \frac{1}{p_{r}}\right).$$