24
$\begingroup$

If $k$ is a positive natural number then $\phi(k)$ denotes the number of natural numbers less than $k$ which are prime to $k$. I have seen proofs that $n = \sum_{k|n} \phi(k)$ which basically partitions $\mathbb{Z}/n\mathbb{Z}$ into subsets of elements of order $k$ (of which there are $\phi(k)$-many) as $k$ ranges over divisors of $n$.

But everything we know about $\mathbb{Z}/n\mathbb{Z}$ comes from elementary number theory (division with remainder, bezout relations, divisibility), so the above relation should be provable without invoking the structure of the group $\mathbb{Z}/n\mathbb{Z}$. Does anyone have a nice, clear, proof which avoids $\mathbb{Z}/n\mathbb{Z}$?

$\endgroup$
19
$\begingroup$

Clearly $n$ counts the number of elements in the set $ \{1,\ldots,n\}$. This suggests that to get a combinatorial proof we should count the number of elements in this set in a different way and get $\sum_{k \mid n} \varphi(k)$.

For $k \mid n$, let $S(k)$ be the set of $m \in \{1,\ldots,n\}$ such that $\gcd(m,n) = k$. Since for all $m \in \{1,\ldots,n\}$, $\gcd(m,n)$ is a divisor of $n$, we have $\sum_{k \mid n} \# S(k) = n$.

Now I claim that for all $k \mid n$, $\# S(k) = \varphi(\frac{n}{k})$. This implies the result because as $k$ runs through all positive divisors of $n$ so does $\frac{n}{k}$. Can you see how to establish this equality?

$\endgroup$
  • $\begingroup$ Yes I can see how to establish that equality. Very nice! $\endgroup$ – JessicaB Sep 12 '12 at 14:56
  • 3
    $\begingroup$ @JessicaB But this is basically the same proof as the one you mentioned in your original question, just phrased slightly differently. To say that $\gcd(m,n)=k$ is the same as saying that $m$ has order $n/k$ in the group $\mathbb{Z}/n\mathbb{Z}$. $\endgroup$ – Ted Sep 12 '12 at 16:01
  • 5
    $\begingroup$ @Ted I think my question was phrased sufficiently clearly to convey that I was expecting an elementary number theory re-phrasing of "the same proof." That said, I disagree with the spirit of your assertion, for the following reason: in order to "see it from the group structure of $\mathbb{Z}/n\mathbb{Z}$," one is actually required to write a lot more. Can we really say that two proofs are 'basically the same' if they use the same ingredients, but one is much longer and introduces needless language? (order, generator, etc). $\endgroup$ – JessicaB Sep 12 '12 at 17:46
29
$\begingroup$

Write the fractions $1/n,2/n,3/n \dots ,n/n$ in the simplest form and you can observe that each fraction is of the form $s/t$ where $t$ divides $n$ and $(s,t)=1$. So the number of the fractions is the same as $\sum_{k|n}{\phi(k)}$ which is equal to $n$.

$\endgroup$
  • $\begingroup$ It might be worth noting that reducing to lowest common terms does not "equalize" any of the $n$ fractions (they remain unequal as before). $\endgroup$ – hardmath Sep 12 '12 at 14:43
  • 2
    $\begingroup$ @hardmath: Actually, that's not even required. Anyone who feels like $\frac24\ne\frac12$ still keeps $n$ objects with all divisors $d$ occuring as denominator etc. $\endgroup$ – Hagen von Eitzen Sep 12 '12 at 14:52
  • 2
    $\begingroup$ This is perhaps my favorite proof of this result. I believe I first encountered it in Hardy and Wright's book on number theory, but I could be wrong. $\endgroup$ – Chris Leary Sep 12 '12 at 15:07
  • 1
    $\begingroup$ @ChrisLeary, it's my favorite proof too. And you're right, it's in Hardy and Wright, §16.2, at least in my 5th ed. $\endgroup$ – lhf Sep 13 '12 at 0:09
8
$\begingroup$

Here is a proof using induction on $n$. The case $n=1$ is clear as $\phi(1)=1$.

Let $n>1$ and assume the result for positive integers less than $n$. Choose a prime divisor $p$ of $n$ and write $n=mp^k$ for $m$ and $p$ coprime. The divisors of $n$ are precisely the $dp^i$ for $d|m$ and $0\leq i\leq k$, so we obtain

\begin{align*} \sum_{d|n}\phi(d)&=\sum_{i=0}^{k}\sum_{d|m}\phi(dp^i)=\sum_{i=0}^{k}\phi(p^i)\sum_{d|m}\phi(d)=m\sum_{i=0}^{k}\phi(p^i)\\ &=m\left(1+\sum_{i=1}^{k}(p^i-p^{i-1})\right)=mp^k=n. \end{align*}

$\endgroup$
5
$\begingroup$

Consider all proper fractions of the form $a/n$. There are $n$ of those. When you consider their reduced forms you get fractions of the form $b/d$ with $d|n$ and $(b,d)=1$. There are $\phi(d)$ of those. The result follows.

$\endgroup$
2
$\begingroup$

This proof uses Möbius inversion, and is pretty quick! Recall the function $$ \mu(n) = \begin{cases} (-1)^{\nu(n)} \qquad \text{if $n$ is square free} \\ 0 \,\,\qquad\qquad\text{otherwise}, \end{cases} $$ where $\nu(n)$ is the number of distinct prime divisors of $n$. The Möbius inversion formula says that $$ f(n)=\sum_{d\mid n} g(d) $$ if and only if $$ g(n)=\sum_{d\mid n}\mu(d)f(n/d). $$ Putting $f(n)=n$ and $g(n)=\varphi(n)$, by Möbius it suffices to show $$ \varphi(n)=\sum_{d\mid n}\mu(d)\frac{n}{d}, $$ and this is true since \begin{align*} \varphi(n)&=n \prod_{p\mid n}\bigg(1-\frac{1}{p}\bigg)\\ &=n \sum_{d\mid n}\frac{\mu(d)}{d}\\ &=\sum_{d\mid n}\mu(d)\frac{n}{d}. \end{align*}

(Note that $\prod_{p\mid n}\big(1-\frac{1}{p}\big)=\sum_{d\mid n}\frac{\mu(d)}{d}$ since terms in the sum are zero except at divisors of $d$ that consist of distinct primes, and multiplying out the product on the right gives precisely this sum.)

$\endgroup$
1
$\begingroup$

I have a pretty cool inductive proof.

The Base Case is trivial.

Now, assume that for some positive integer $m$ we had

$\sum_{m|n} \phi(m) = n$

Now, I will show that for any prime power $p^d$, we must have $\sum_{m|p^dn} \phi(m) = p^dn$

For the sake of convenience, we may assume that $\gcd(p,n) = 1$. If this was not the case, just repeat the proof but instead of using $n$ use $\frac{n}{\text{ord}_p(n)}$ instead.

Now,

$$ \begin{align} \sum_{m|p^dn} \phi(m) &= \sum_{m|n} \phi(m) + \sum_{p|m|pn} \phi(m) + ... + \sum_{p^d|m|p^dn} \phi(m) \\ &= n+\sum_{k|n} \phi(p)\phi(k) + \sum_{k|n} \phi(p^2)\phi(k) + ... + \sum_{k|n} \phi(p^d)\phi(k) \\ &= n+\phi(p)*n+\phi(p^2)*n+...+\phi(p^d)*n \\ &= n(1+(p-1)+p(p-1)+p^2(p-1)+...+p^{d-1}(p-1)) \\ &= n(1+(p-1)\frac{p^d-1}{p-1}) \\ &= n*p^d \end{align} $$

thus proving the inductive step thus completing the proof.

$\endgroup$
  • 1
    $\begingroup$ The base case consists of showing the equality holds for all primes $n$ (I guess that's what you called trivial?) but you also need to prove that the inductive step does not just work for prime powers, but for any composite $n = p \cdot q$. $\endgroup$ – TMM Oct 1 '16 at 21:41
1
$\begingroup$

Claim:Number of positive integers pair $(a, b) $ satisfying : $n=a+b$ (for given $n$) $\gcd(a, b) =d$ and $d|n$ is $\phi(n/d) $.

Proof: Let $a=xd$ and $b=yd$ We want number of solution for $x+y=\frac{n}{d}$ such that $\gcd(x, y) =1$.

$\gcd(x,y)=\gcd(x,x+y)=\gcd(x,n/d)=1$

Solution for $x+y=n/d$, $\gcd(x,y)=1$ is $\phi(n/d) $. ________________________

Number of positive integers pair $(a, b) $ satisfying $a+b=n$ is $n$.

But this can counted in different way: If $(a, b) $ is solution then $\gcd(a, b) =d$ for some divisor $d$ of $n$.

So we can use our claim to write $\sum_{d|n} \phi(n/d) =\sum_{d|n}\phi(d)=$ Number of solution $=n.$

$\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.