3
$\begingroup$

enter image description here


In the proof, it says "clearly equals $\phi(n_1)$". I don't see how this is clear. I also don't see how this implies $n=\sum_{d|n}\phi(n/d)$.

Can someone please clarify this proof?

(from A Course in Combinatorics book by van Lint/Wilson, page 92)

$\endgroup$
3
  • $\begingroup$ alternatively prove $\phi(nm) = \phi(n)\phi(m)$ when $gcd(n,m)=1$, prove $\sum_{n | d}\phi(d) = n$ when $n$ is a power of prime, and voila. $\endgroup$
    – reuns
    Feb 18, 2016 at 2:38
  • $\begingroup$ @user1952009 What if $n$ is not of prime power? $\endgroup$ Feb 18, 2016 at 2:45
  • $\begingroup$ the properties of $\sum_{d | n} f(d)$ when $f$ is a multiplicative function ensures that it is enough to prove it when $n$ is a prime power. again if $c = ab$ with $gcd(a,b) = 1$ and the formula is true for $n=a$ and $n=b$ then $\sum_{d | c} \phi(d) = \sum_{d | ab} \phi(d) = \sum_{d_1 | a , \, d_2 | b} \phi(d_1 d_2) = \sum_{d_1 | a} \sum_{d_2 | b} \phi(d_1) \phi(d_2) = a b = c$ $\endgroup$
    – reuns
    Feb 18, 2016 at 2:55

3 Answers 3

4
$\begingroup$

Let $S_d$ consists of all $m\in N$ such that $(m,n)=d$. We may then partition $N$ as $N= \bigcup_{d\in\mathbb{N}} S_d$, which implies that $n=\lvert N \rvert=\sum_{d\in\mathbb{N}} \lvert S_d \rvert$.

Now note that $m\in S_d$ implies that $1\leq m\leq n$ and $(m/d,n/d)=1$. The number of such values is $\phi(n/d)$, by definition of the $\phi$ function. And so $\lvert S_d \rvert = \phi(n/d)$, implying that $n=\sum_{d|n} \phi(n/d)$ as desired.

$\endgroup$
2
  • $\begingroup$ I don't see how this adds any clarification to the proof. $\endgroup$ Feb 18, 2016 at 1:59
  • $\begingroup$ I added some more details. $\endgroup$
    – dshin
    Feb 18, 2016 at 2:21
3
$\begingroup$

Note that $\left(m,n\right)=d$, $1\leq m\leq n$ if and only if $\left(m_{1},n_{1}\right)=1$ with $m_{1}=m/d$ and $n_{1}=n/d$ and $1\leq m_{1}\leq n/d$. So there is a correspondence between the number $m$ and the integers $m_{1}$. But the number of $m_{1}$ is $\phi\left(n/d\right)$.

$\endgroup$
2
  • $\begingroup$ Why is $1\le m_1 \le n/d$? $\endgroup$ Feb 16, 2016 at 7:22
  • $\begingroup$ @AlJebr Because $m \leq n$. $\endgroup$ Feb 16, 2016 at 7:24
0
$\begingroup$

The standard number theory approach is to define a function $f$ on the positive integers as "multiplicative" if $f(ab) = f(a) f(b),$ whenever $\gcd(a,b) = 1.$ A multiplicative function is defined by its values at primes and prime powers.

Next is a lemma, needs careful proof, if $f$ is multiplicative, then so is $$ g(n) = \sum_{d |n} f(d). $$

It is also necessary to prove that $\phi$ really is multiplicative.

With all that done, your Theorem 10.2 comes down to showing the equation when $n$ is $1$ or a prime $p$ or a prime power $p^k.$ Note that $\phi(1) = 1, \phi(p) = p-1, \phi(p^2) = p^2 - p, \phi(p^3) = p^3 - p^2,$ and so on. You could call it induction on the exponent $k.$

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