In number theory, it's often required to check whether the proof of an expression can be done without resorting to prime numbers (Hence the prime free part). We are allowed to use concepts of coprime numbers though.
Now I have seen a prime free proof of $$\phi(mn)=\phi(m)\phi(n)$$ when $gcd(m,n):=(m,n)=1$. There is a generalization for any $m$ and $n$ given by $$\phi(mn) = \frac{d\phi(m)\phi(n)}{\phi(d)}$$ where $d=(m,n)$. So I started proving this as follows (no primes allowed):
Proof: $$\phi(mn) = \sum_{k=1}^{mn}1_{\left\{(k,mn)=1\right\}}$$ $$= \sum_{k=1}^{mn}1_{\left\{(k,m)=1\right\}}1_{\left\{(k,n)=1\right\}}$$ Let $k=(q-1)m+r$ where $q=\{1,2,\cdots, n\}$ and $r=\{1,2,\cdots, m\}$. Then we get $$\phi(mn) = \sum_{r=1}^m\sum_{q=1}^n 1_{\{((q-1)m+r,m)=1\}}1_{\{((q-1)m+r,n)\}}$$ $$=\sum_{r=1}^m1_{\{(r,m)=1\}}\sum_{q=1}^n1_{\{((q-1)m+r,n)\}}$$
Given $r$, consider the collection $\{(q-1)m+r\}_{q=1}^n$ modulo n. Now pick any $q_1 \in \{1,2,...n\}$. Let $q_2=q_1+\frac{n}{d}$. Then we can easily see $q_1m=q_2m \mbox{ mod } n$. Hence we get $d$ repetitions of some of the residues from $q=1$ to $n/d$ $$\sum_{q=1}^n1_{\{((q-1)m+r,n)\}} = d\sum_{q=1}^{n/d}1_{\{((q-1)m+r,n)\}}$$
So if I can show $$\sum_{q=1}^{n/d}1_{\{((q-1)m+r,n)\}} =\frac{\phi(n)}{\phi(d)},$$ I would be done. Note that RHS is an integer (although I am looking ahead and claiming it, I'm not using that here yet).
Unfortunately, I do not know what to do at this point. It's like I should expand the sum in some way and then divide it again or something like that...
I'd be grateful if someone could offer some useful advice on this matter. Most books I know use the prime number representation to prove it but I think it can be done without it.
I have given an answer below. I think it is correct but I am open to ideas on how to improve it.
Update: I have corrected some errors. Now that I've proved this is prime free, the following are also prime free as corollaries:
a) $d|n \Rightarrow \phi(d) | \phi(n)$.
b) If $lcm(m,n) := [m,n]$, then $\phi(m)\phi(n) = \phi((m,n))\phi([m,n])$.