Jtdylktuy

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{dphi(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)=1right}}$$
$$= sum_{k=1}^{mn}1_{left{(k,m)=1right}}1_{left{(k,n)=1right}}$$
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}^msum_{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)}} = dsum_{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])$.

I believe I have it. We need to show the following:

1. Show that $$sum_{q=0}^{n/d-1} 1_{{(qm+r,n)=1}} = sum_{q=0}^{n/d-1} 1_{{(qm+r,n/d)=1}}$$
   


2. Show that $$sum_{q=0}^{n/d-1} 1_{{(qm+r,n/d)=1}} = sum_{q=0}^{n/d-1} 1_{{(qd+r,n/d)=1}}$$
   


3. Show that $$sum_{q=0}^{n/d-1} 1_{{(qd+r,n/d)=1}} = sum_{q=0}^{n/d-1} 1_{{(qd+1,n/d)=1}}=frac{phi(n)}{phi(d)}$$
   where $r$ satisfies $(r,m)=1$.

Note that the conditions on $r$ is actually met since the indicator function of the same is active. Note that $d>1$ else it boils down to the coprime case.

Proof of 1:

Just use $(a,bc)=1 iff (a,b)=(a,c)=1$. And observe $(qm+r,d)=(r,d)=1$.

Proof of 2:
We have $qm+r = (q.frac{m}{d}.d + r$.
By division algo, $qfrac{m}{d} = hat{q}frac{n}{d} + bar{q}$ where both $q, bar{q} in {0, 1, 2, cdots, n/d - 1}$. So modulo $n/d$, $qm+r = bar{q}d + r$.

Now we need to show that if $q_1 ne q_2$ and $|q_1 - q_2| < n/d$, then $bar{q}_1 ne bar{q}_2$ (all mod $n/d$). To see this, suppose not, then we have
begin{eqnarray}
bar{q}_1 - bar{q}_2 &=& 0 mod n/d \
bar{q}_1 + hat{q}_1frac{n}{d} - bar{q}_2 - hat{q}_2frac{n}{d} &=& 0 mod n/d \
(q_1 - q_2)frac{m}{d} &=& 0 mod n/d \
q_1 &=& q_2 mod n/d Rightarrow!Leftarrow
end{eqnarray}
where the second to last step follows since $(frac{m}{d}, frac{n}{d}) = 1$. Thus the ${hat{q}}$ are a permutation of ${q}$ and so the result follows.

Proof of 3:
(If someone can improve this argument, i'll be very happy.)

We may assume that $0<r <d$. This is because
$$r=ad+r' Rightarrow sum_{q=0}^{n/d-1} 1_{{(qd+r,n/d)=1}}=sum_{q=0}^{n/d-1} 1_{{((q+a)d+r',n/d)=1}}\
= sum_{q=a}^{n/d+a-1} 1_{{(qd+r',n/d)=1}}=sum_{q=a}^{n/d-1} 1_{{(qd+r',n/d)=1}}+sum_{q=n/d}^{n/d+a-1} 1_{{(qd+r',n/d)=1}}\
=sum_{q=a}^{n/d-1} 1_{{(qd+r',n/d)=1}}+sum_{q=n/d}^{n/d+a-1} 1_{{((q-n/d)d+r',n/d)=1}}\
=sum_{q=a}^{n/d-1} 1_{{(qd+r',n/d)=1}}+sum_{q=0}^{a-1} 1_{{(qd+r',n/d)=1}}= sum_{q=0}^{n/d-1} 1_{{(qd+r',n/d)=1}}$$

where $0< r'<d$. Hence let $0<r<d$.

Now we want to show that $sum_{q=0}^{n/d-1} 1_{{(qd+r,n/d)=1}}$ is independent of $r$ under the given conditions. We either have $(d,n/d)=1$ or $(d,n/d)>1$.

Suppose $(d,n/d)=a>1$, then we can show using the method in the question (and using point 2 from answer) that:
$$sum_{q=0}^{n/d-1} 1_{{(qd+r,n/d)=1}} = asum_{q=0}^{n/(ad)-1} 1_{{(qa+r,n/(ad))=1}}$$
This $a$ does not depend on $r$ either. Now we check if $(a,n/da)$ is $1$ or not. If not, we repeat this procedure until a point comes when they will be coprime. This procedure has to stop since at each stage $a>1$ and we are reducing the number of terms in the sum by that much. Then we proceed as below.

But when $(d,n/d)=1$, ${qd+r}$ contains all the residues of $n/d$ and is independent of $r$. At no stage was the value of $r$ used. Thus when we finally write out this expression's value, it will be independent of $r$.
Thus:
$$phi(n) =sum_{q=0}^{n/d-1} sum_{j=1}^d 1_{{(qd+j,n/d)=1}}1_{{(j,d)=1}} \
= sum_{j=1}^d left[sum_{q=0}^{n/d-1} 1_{{(qd+r,n/d)=1}}right]1_{{(j,d)=1}} \
=sum_{q=0}^{n/d-1} 1_{{(qd+r,n/d)=1}}phi(d)$$

Hence we have the prime free proof.