Monday, November 18, 2013

Euler's totient function

Its a very nice function on Natural numbers. A totient function on natural number n represented by φ(n) is defined as -
                  For prime p : -
                                 


Clearly φ(n) = # of mutual primes w.r.t n in the range of [ 1 ... n ].


Notation :- Z= [ 0 ... (n - 1) ]


Property : - 1. ∀ m,n ∈ Z ( Set of Natural Numbers ) s.t. gcd(m,n) = 1,

                             φ(m.n) = φ(m).φ(n)
                   2. ∀ m,n ∈ Z, φ(m.n) = φ(m).φ(n). gcd(m,n)/φ(gcd(m,n)) 
                   3.       
                   
                  4. For mutually prime a,n
                  5. 
                  6.  For ∀ a,n ∈ Z  and n > 1, 

If we inscribe  Möbius function and then some beautiful identity could be found.


For more see http://en.wikipedia.org/wiki/Euler's_totient_function


No comments:

Post a Comment