Skip to content

Files

Latest commit

305e48d · Oct 19, 2018

History

History

eulers_totient_function

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
Oct 6, 2018
Oct 19, 2018
Oct 6, 2018
Oct 6, 2018

readme.md

Euler's Totient Function

Euler’s Totient function Φ(n) for an input n is count of numbers in {1, 2, 3, …, n} that are relatively prime to n, i.e., the numbers whose GCD (Greatest Common Divisor) with n is 1.

Φ(1) = 1
gcd(1, 1) is 1

Φ(2) = 1
gcd(1, 2) is 1, but gcd(2, 2) is 2.

Φ(3) = 2
gcd(1, 3) is 1 and gcd(2, 3) is 1

Φ(4) = 2
gcd(1, 4) is 1 and gcd(3, 4) is 1

Φ(5) = 4
gcd(1, 5) is 1, gcd(2, 5) is 1, 
gcd(3, 5) is 1 and gcd(4, 5) is 1

Φ(6) = 2
gcd(1, 6) is 1 and gcd(5, 6) is 1

How to compute Φ(n) for an input n?

A simple solution is to iterate through all numbers from 1 to n-1 and count numbers with gcd with n as 1.