Euler $\phi$ function

Number theory
Post Reply
tziaxri
Posts: 7
Joined: Mon Nov 09, 2015 4:32 pm

Euler $\phi$ function

#1

Post by tziaxri »

Prove that

\[ \forall n\geq1 : \displaystyle\mathop{\sum}\limits_{d|n}\phi(d)=n \] where: \[ \phi(n) = \rvert\bigl\{k\in \mathbb{N} \rvert 1 \leq k \leq n \wedge (k,n)=1 \bigl\}\rvert \]

is the Euler phi function.
User avatar
Grigorios Kostakos
Founder
Founder
Posts: 461
Joined: Mon Nov 09, 2015 1:36 am
Location: Ioannina, Greece

Re: Euler $\phi$ function

#2

Post by Grigorios Kostakos »

tziaxri wrote:Prove that

\[ \forall n\geq1 : \displaystyle\mathop{\sum}\limits_{d|n}\phi(d)=n \] where: \[ \phi(n) = \rvert\bigl\{k\in \mathbb{N} \rvert 1 \leq k \leq n \wedge (k,n)=1 \bigl\}\rvert \]

is the Euler phi function.
We give the classical proof which can be found in almost every number theory book. For example: Hardy and Wright, Introduction to the Theory of Numbers.

For \(n=1\) is trivial. If \(n>1\) and \(n=\mathop{\prod}\limits_{i=1}^{k}p_i^{r_i}\) is the unique-prime-factorization of \(n\), then the divisors of \(n\) are the numbers \(d=\mathop{\prod}\limits_{i=1}^{k}p_i^{s_i}\,, \; s_i\leqslant r_i\,,\) for every prime \(p_i\). The function \[F(n):=\displaystyle\mathop{\sum}\limits_{d|n}\phi(d)\,,\quad n\in {\mathbb{N}}\,,\] is multiplicative. For every \(i=1,2,\ldots, k\,,\) we have
\begin{align*}
F(p_i^{r_i})&=\displaystyle\mathop{\sum}\limits_{j=0}^{r_i}\phi(p_i^{j})\\
&=\phi(1)+\mathop{\sum}\limits_{j=1}^{r_i}\phi(p_i^{j})\\
&=1+\mathop{\sum}\limits_{j=1}^{r_i}(p_i^{j}-p_i^{j-1})\\
&=p_i^{r_i}\,.
\end{align*} And from the multiplicity of \(F\) we have \[F(n)=\displaystyle\mathop{\prod}\limits_{i=1}^{k}F(p_i^{r_i})=\mathop{\prod}\limits_{i=1}^{k}p_i^{r_i}=n\,.\]
Grigorios Kostakos
Post Reply

Create an account or sign in to join the discussion

You need to be a member in order to post a reply

Create an account

Not a member? register to join our community
Members can start their own topics & subscribe to topics
It’s free and only takes a minute

Register

Sign in

Who is online

Users browsing this forum: No registered users and 8 guests