Prove-that-n-n-k-1-1-p-k-n-Euler-totient-function-

Question Number 142880 by Dwaipayan Shikari last updated on 06/Jun/21

P r o v e t h a t \boldsymbol ϕ (n) = n \prod_{k} (1 - \frac{1}{p_{k}}) ϕ (n) : E u l e r t o t i e n t f u n c t i o n

Answered by Snail last updated on 06/Jun/21

I a m c o n s i d e r i n g t h a t u k n o w ϕ (n) i s m u l t i p l i c a t i v e

f u n c t i o n i . e ϕ (a b) = ϕ (a) ϕ (b) . . w h e r e a a n d b

a r e c o p r i m e

L e t p_{1} \dots \dots \dots \dots . p_{k} a r e d i s t i n c t p r i m d f a c t o r s o f n

n = p_{1}^{k_{1}} \dots \dots \dots p_{k}^{k_{r}} [h e r e r = k a s k = n u m b e r o f t e r m s]

ϕ (n) = ϕ (p_{1}^{k_{1}} \dots . . p_{k}^{k_{r}}) = ϕ (p_{1}^{k_{1}}) \dots \dots ϕ (p_{k}^{k_{r}}) \dots . (1)

N o w t h e n u m b e r o f i n t e g e r s w h i c h a r e n o t

c o p r i m e t o p^{k} \dots (p . 1), (p . 2), (p . 3), \dots \dots . . (p . p^{k - 1})

ϕ (p^{k}) = n u m b d r o f i n t e g e r s c o p r i m d t o p^{k} a n d < p^{k}

= p^{k} - p^{k - 1} = p^{k} (1 - \frac{1}{p})

N o w u s i n g t h i s i n (1)

= p_{1}^{k_{1}} (1 - \frac{1}{p_{1}}) p_{2}^{k_{2}} (1 - \frac{1}{p_{2}}) \dots p_{k}^{k_{r}} (1 - \frac{1}{p_{r}})

= p_{1}^{k_{1}} p_{2}^{k_{2}} \dots . . p_{r}^{k_{r}} (1 - \frac{1}{p_{1}}) \dots . . (1 - \frac{1}{p_{r}})

= n (1 - \frac{1}{p_{1}}) (1 - \frac{1}{p_{2}}) \dots . (1 - \frac{1}{p_{k}})

P r o v e d \dots .

Commented by Dwaipayan Shikari last updated on 07/Jun/21

T h a n k s

T h a n k s