Euler Phi's Function
Explore Euler’s Phi function to understand how to find the count of positive integers that are coprime with a given number. This lesson guides you through the formula and step-by-step implementation to solidify your grasp of number theory concepts critical for coding interviews.
We'll cover the following...
We'll cover the following...
Introduction
Euler’s Phi function (also known as totient function, denoted by ) is a function on natural numbers that gives the count of positive integers co-prime with the corresponding natural number, i.e., the numbers whose GCD (Greatest Common Divisor) with N is 1. So we can say the following:
(1) = 1 because gcd(1, 1) is 1.
(2) = 1 because gcd(1, 2) is 1, but gcd(2, 2) is 2.
(3) = 2 because gcd(1, 3) is 1 and gcd(2, 3) is 1.
...