My Math Forum Euler's Totient Little Trick

 Number Theory Number Theory Math Forum

 August 1st, 2018, 04:36 AM #1 Member   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)$$ example: $n=50=2\cdot5\cdot5$ $$\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$$ since $$\bigg(1-\frac{1}{p}\bigg)=\frac{p-1}{p}$$ 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$ $\varphi(1350)=(2-1)\cdot(3-1)\cdot3^{3-1}\cdot(5-1)\cdot5^{2-1}=1\cdot(2\cdot3^2)\cdot(4\cdot5^1)=360$ Thanks from 2sly4U

 Tags euler, totient, trick

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Bogauss Number Theory 9 May 29th, 2017 07:53 AM Bogauss Number Theory 8 March 22nd, 2012 09:04 AM Bogauss Number Theory 31 March 21st, 2012 08:48 PM momo Number Theory 11 February 16th, 2010 11:41 AM Geir Number Theory 1 April 28th, 2009 05:00 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top