Proof of multiplicative property of Euler's Totient function using Combinatorics inclusion exclusion principle - pending

Let's take an example.
n = 10
Prime factors; 2,5

To find Phi(10)
We do 10 - 10/5 - 10/2, basically subtract all numbers divisible by one of the prime factors.
But that would cancel out the number 10 twice since it's divisible by both 2,5.
So we add that again.

It can be written as:
n - n(1) + n(2)
Where n(1) = numbers divisible by 1 prime factor.
n(2) = numbers divisible by 2 prime factors.

In this case: 10 - 10/5 - 10/2 + 10/10 = 10 - (7) + 1 = 4 which is indeed correct.
1,3,7,9 are co prime to 10.


To make it general:
Let n = p1^a1 * p2 ^ a2 ... pk ^ ak
Phi(n) = n - n(1) + n(2) - n(3) ... (-1)^k.n(k) where k is the number of prime factors of n.
= n - (n/p1 + n/p2 .. n/pk) + Sigma(n/p_i.p_j) ...
= n [1 - sigma(1/p_i) + sigma(1/p_i.p_j) - ...]
= n (1 - 1/p1) (1 - 1/p2) ..(1-1/pk)


Now let m = q1^a1 * q2 ^ a2 ... qk1 ^ ak1
And let gcd(m,n) = 1 i.e. they are coprime. So no common factors.
Phi(m) = m (1 - 1/q1) (1 - 1/q2) ..(1-1/qk)

And Phi(mn) = mn (1 - 1/q1) (1 - 1/q2) ..(1-1/qk)  (1 - 1/p1) (1 - 1/p2) ..(1-1/pk)
= Phi(m) * Phi(n)

QED