1. Euler’s Totient Function #

Created Thursday 30 July 2020

Denoted by φ(n) → Number of ‘m’ such that:

1. 1<=m<n
2. gcd(m, n) = 1
3. m ∈ N

e.g φ(3) = 2 {1, 2} φ(4) = 2 {1, 3} φ(5) = 4 {1, 2, 3, 4}

1. Multiplicative properties:
   • *φ(ab) = φ(a)φ(b) if gcd(a, b) = 1
   • Proof omitted
2. Prime property:

φ(p^a^) = p^a^-p^a-1^=p^a^(1-1/p) More specifically φ§ = p-1

3. Generator function:

Any number can be expressed as a product of its’s powers of distinct primes. And all of the powers of primes are coprime. So φ(n) = φ(p~1~^a^) * φ(p~2~^b^) … φ(p~k~^k^) Using prime property, we can say φ(n) = n(1-1/p~1~)*(1-1/p~2~)…*

We can find φ(n) using the generator property. T.C = Sieve of Eratosthenes