Intereting Posts

Prove that $6$ divides $n(n + 1)(n + 2)$
Math competition problem, prove that $\int_{-\infty}^\infty e^{-\pi x^2 \left(\frac{\alpha +x}{\beta +x}\right)^2}dx=1~$ for $~0<\beta<\alpha$.
Evaluating $\int \frac{\mathrm dz}{z^3 \sqrt{z^2 – 4}}$
statistical distance identity
Approximate spectral decomposition
extended stars-and-bars problem(where the upper limit of the variable is bounded)
Prove that $\frac{a_1^2}{a_1+a_2}+\frac{a_2^2}{a_2+a_3}+ \cdots \frac{a_n^2}{a_n+a_1} \geq \frac12$
How should I calculate the $n$th derivative of $f(x)=x^x$?
Linear transformations and norm
totient function series diverges?
How to prove that given set is a connected subset of the space of matrices?
Are 14 and 21 the only “interesting” numbers?
Homogeneous ideal and degree of generators
Determine cycle from adjacency matrix
Showing that left invariant vector fields commute with right invariant vector fields

Here is a very elementary number theory proof using strong induction. Please mark/grade.

Prove that $$\sum_{d|n}\phi(d)=n$$where $\phi$ is the Euler’s phi function, $n,d\in\mathbb{N}$

First, when n=1,$$\sum_{d|1}\phi(d)=\phi(1)=1$$

Second, assume $$\sum_{d|k}\phi(d)=k\;\forall k\lt n,\;k\in\mathbb{N}$$

and let $n=p^kq, \;p\nmid q, p$ is prime,

Then $$\sum_{d|n}\phi(d)$$

$$=\sum_{0\le j\le k,\;e|q}\phi(p^je)$$

$$=\sum_{0\le j\le k,\;e|q}\phi(p^j)\phi(e)$$

$$=\sum_{0\le j\le k}\phi(p^j)\sum_{e|q}\phi(e)$$

$$=(\phi(1)+\sum_{1\le j\le k}(p^j-p^{j-1}))q$$

$$=(1+p^k-1)q$$

$$=p^kq$$

$$=n$$

By strong induction, $$\sum_{d|n}\phi(d)=n\;\forall n\in\mathbb{N}$$

Is my proof ok? Also, is there some more elegant proof? Thank you.

- Prove that $\lim_{n\to\infty}a_n\le \lim_{n\to\infty}b_n$
- Better proof for $\frac{1+\cos x + \sin x}{1 - \cos x + \sin x} \equiv \frac{1+\cos x}{\sin x}$
- Irrational numbers to the power of other irrational numbers: A beautiful proof question
- 'Every open set in $\mathbb{R}$ is the union of disjoint open intervals.' How do you prove this without indexing intervals with $\mathbb{Q}$?
- If $n$ is squarefree, $k\ge 2$, then $\exists f\in\Bbb Z : f(\overline x)\equiv 0\pmod n\iff \overline x\equiv \overline 0\pmod n$
- Prove that a continuous function on a closed interval attains a maximum

- For prime $p>2: 1^23^25^2\cdot\cdot\cdot(p-2)^2 \equiv (-1)^{\frac{p+1}{2}} \pmod p$
- Conjecture about the product of the primitive roots modulo a prime number ($\prod Pr_p$)
- Prove that if $n$ is a composite, then $2^n-1$ is composite.
- Proving $\int_{0}^{\pi/2}x\sqrt{\tan{x}}\log{\sin{x}}\,\mathrm dx=-\frac{\pi\sqrt{2}}{48}(\pi^2+12\pi \log{2}+24\log^2{2}) $
- What is the remainder of $16!$ is divided by 19?
- Why can't prime numbers satisfy the Pythagoras Theorem? That is, why can't a set of 3 prime numbers be a Pythagorean triplet?
- Number of solutions for $\frac{1}{X} + \frac{1}{Y} = \frac{1}{N!}$ where $1 \leq N \leq 10^6$
- Show that there exist no $a, b, c \in \mathbb Z^+$ such that $a^3 + 2b^3 = 4c^3$
- On the norm formula $N(IJ) = N(I)N(J)$ in an order of an algebraic number field
- Proof that $\sqrt{3}$ is irrational

Here is the cutest proof I know of this fact. Consider the $n$ fractions $$\frac{1}{n},\frac{2}{n} \ldots \frac{n}{n}$$

There are $\varphi(n)$ fractions which do not reduce at all. In fact, for every $d|n$, there are $\phi(d)$ fractions which reduce by exactly $n/d$. How many fractions do you have?

In the cyclic group $\mathbb Z_n$there are $\varphi(d)$ elements of order $d$ if $d|n$. Since by lagrange every element has an order that divides $n$ we conclude the number of elements in $\mathbb Z_n$ is $\sum\limits_{d|n}\varphi(d)$.

Your proof is correct, but can be put more succinctly by proving the more general theorem that if $f(n)$ is multiplicative[*], then:

$$g(n)=\sum_{d\mid n} f(d)$$ is also multiplicative.

So, since $\phi(n)$ is multiplicative, you only need to check that for $n=p^k$ a prime power that:

$$p^k=\sum_{d\mid p^k} \phi(d)$$

Which you’ve done.

[*] Multiplicative means that if $m,n$ relatively prime, then $f(mn)=f(m)f(n)$.

- Recommendation on stochastic process books
- Homological algebra in PDE
- Proof of a special case of Fermat's Last Theorem.
- Zeroes of exact differential forms on compact manifold
- Must $k$-subalgebra of $k$ be finitely generated?
- picking a witness requires the Axiom of Choice?
- Operator norm and tensor norms
- How does “If $P$ then $Q$” have the same meaning as “$Q$ only if $P$ ”?
- Showing that $2 \Gamma(a) \zeta(a) \left(1-\frac{1}{2^{a}} \right) = \int_{0}^{\infty}\left( \frac{x^{a-1}}{\sinh x} – x^{a-2} \right) \, dx$
- How should I understand the $\sigma$-algebra in Kolmogorov's zero-one law?
- Why don't I get $e$ when I solve $\lim_{n\to \infty}(1 + \frac{1}{n})^n$?
- Evaluate $ \int_{0}^{\pi/2}\frac{1+\tanh x}{1+\tan x}dx $
- Properties of squares in $\mathbb Q_p$
- Dirichlet L-series and Gamma function question
- Why does Group Theory not come in here?