My Math Forum  

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

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
August 1st, 2018, 04:36 AM   #1
Member
 
Joined: Aug 2015
From: Montenegro (Podgorica)

Posts: 36
Thanks: 2

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$
1ucid is offline  
 
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
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 © 2018 My Math Forum. All rights reserved.