User Name Remember Me? Password

 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 Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded 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      