notes

Personal notes
git clone git://git.laack.co/notes.git
Log | Files | Refs

EulersTotientFunction.md (777B)

      1 # Euler's Totient Function
      2 
      3 **Source:** Computer and Network Security
      4 
      5 **Chapter:** 2.5
      6 
      7 **Definition:** Euler's totient function, denoted as $\phi$, is the number of positive integers less than $n$ and relatively prime to $n$.
      8 
      9 Note: $\phi(1) = 1$ by convention, which does not make much sense.
     10 
     11 ## Work
     12 
     13 Determine $\phi(37).
     14 
     15 To find $\phi(37)$ we notice 37 is prime and thus all integers less than it are relatively prime to it thus $\phi(37) = 36$. 
     16 
     17 Determine $\phi(35)$. 
     18 
     19 By evaluating 1-34 we find the following are relatively prime to 35:
     20 
     21 1, 2, 3, 4, 6, 8, 9, 11, 12, 13, 16, 17, 18, 19, 22, 23, 24, 26, 27, 29, 31, 32, 33, 34
     22 
     23 Given this we see $\phi(35) = 24$.
     24 
     25 ## Corollaries
     26 
     27 Where n is defined as pq:
     28 
     29 $\phi(n) = \phi(pq) = \phi(p) * \phi(q) = (p-1) * (q - 1)$.