1
$\begingroup$

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])$.

$\endgroup$
  • $\begingroup$ ...what, exactly, does "without resorting to prime numbers" mean? $\endgroup$ – user361424 Dec 8 '16 at 7:30
  • $\begingroup$ Certain proofs in basic number theory are made significantly easier by assuming the existence of prime numbers and using the properties of prime numbers. I have observed that certain proofs go through without mentioning primes at all. e.g. With prime numbers, the proof of $mn=gcd(m,n)lcm(m,n)$ is as simple as observing $x+y=\min(x,y) + \max(x,y)$. Without prime numbers the proof is doable but much harder. $\endgroup$ – Gautam Shenoy Dec 8 '16 at 10:01
  • $\begingroup$ Why do you think that proving $mn=gcd(m,n)lcm(m,n)$ without prime numbers is hard? It can be proved easily by noting that $m\mid mn/gcd(m,n)$ and $n\mid mn/gcd(m,n)$ implies $lcm(m,n)\mid mn/gcd(m,n)$ so $gcd(m,n)lcm(m,n)\mid mn$, and reciprocally $mn/lcm(m,n)\mid m$ and $mn/lcm(m,n)\mid n$ implies $mn/lcm(m,n)\mid gcd(m,n)$ so $mn\mid gcd(m,n)lcm(m,n)$. Besides, trying to prove theorems in number theory without using prime numbers is like trying to prove a statement involving natural numbers without using induction. $\endgroup$ – Xam Feb 13 '17 at 18:31
  • $\begingroup$ @Xam: It's not hard. It's harder (in a relative sense) without primes. It's basically a challenge to prove statements without resorting to existence of prime numbers. Since you mentioned induction, I believe that a proof by induction is basically an exhaustive verification that usually does not reveal much about the structure of the problem. Often you need to know the answer (or a good guess) before induction can be used. $\endgroup$ – Gautam Shenoy Feb 13 '17 at 18:55
  • $\begingroup$ @Xam, if you can prove something without using primes, then you have proved that it holds true, not just in the integers, but in other systems that have gcd and lcm but don't have primes. $\endgroup$ – Gerry Myerson Feb 14 '17 at 12:08
0
$\begingroup$

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, $q\frac{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}_1\frac{n}{d} - \bar{q}_2 - \hat{q}_2\frac{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\}} = a\sum_{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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.