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)
$\begingroup$
$\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$– reunsFeb 18, 2016 at 2:38
-
$\begingroup$ @user1952009 What if $n$ is not of prime power? $\endgroup$– user5826Feb 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$– reunsFeb 18, 2016 at 2:55
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
2
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.
-
$\begingroup$ I don't see how this adds any clarification to the proof. $\endgroup$– user5826Feb 18, 2016 at 1:59
-
$\begingroup$
$\endgroup$
2
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)$.
answered Feb 16, 2016 at 7:00
$\begingroup$
$\endgroup$
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.$
answered Feb 16, 2016 at 20:48