My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum

Thanks Tree1Thanks
  • 1 Post By 1ucid
LinkBack Thread Tools Display Modes
August 1st, 2018, 04:36 AM   #1
Joined: Aug 2015
From: Montenegro (Podgorica)

Posts: 37
Thanks: 4

Euler's Totient Little Trick

Euler's totient function uses this formula to count the numbers which are relatively prime to $n$:

$$\varphi(n)=n \prod_{p|n} \bigg(1-\frac{1}{p}\bigg)$$



$$\varphi(50)=50\cdot\bigg(1-\frac{1}{2}\bigg)\cdot\bigg(1-\frac{1}{5}\bigg)=(\cancel{2}\cdot \cancel{5} \cdot5) \cdot \frac{1}{\cancel{2}} \cdot \frac{4}{\cancel{5}}=5\cdot1\cdot4=20$$

every prime factor $p_i^1$ with power $1$ will just be $p_i-1$ and prime factors with power greater than $1$, $p^k$ can be written as $p^1 \cdot p^{k-1}$ and result of a totient function for that prime will be $(p-1) \cdot p^{k-1}$.

So in example above we have $50=2^1\cdot5^2$, $\varphi(50)=(2-1)\cdot(5^1-1)\cdot5^{2-1}=1\cdot4\cdot5=20$

another example, number $1350=2^1\cdot3^3\cdot5^2$

Thanks from 2sly4U
1ucid is offline  

  My Math Forum > College Math Forum > Number Theory

euler, totient, trick

Thread Tools
Display Modes

Similar Threads
Thread Thread Starter Forum Replies Last Post
Primality and Euler totient Bogauss Number Theory 9 May 29th, 2017 07:53 AM
Euler totient : phi(n)=phi(a)+phi(n-a) Bogauss Number Theory 8 March 22nd, 2012 09:04 AM
Euler totient puzzle Bogauss Number Theory 31 March 21st, 2012 08:48 PM
Goldbach and Euler totient momo Number Theory 11 February 16th, 2010 11:41 AM
Which number has the Euler's totient of ...?! Geir Number Theory 1 April 28th, 2009 05:00 AM

Copyright © 2019 My Math Forum. All rights reserved.