If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Main content

# Euler's totient function

## Video transcript

oiler continue to investigate properties of numbers specifically the distribution of prime numbers one important function he defined is called the Phi function it measures the break ability of a number so given a number say n it outputs how many integers are less than or equal to n that do not share any common factor with n for example if we want to find the Phi of 8 we look at all values from 1 to 8 then we count how many integers 8 does not share a factor greater than 1 with notice 6 is not counted because it shares a factor of 2 well 1 3 5 & 7 are all counted because they only share a factor of 1 therefore Phi of 8 equals 4 what's interesting is that calculating the Phi function is hard except in one case look at this graph it is a plot of values of Phi over integers from 1 to a thousand now notice any predictable pattern the straight line of points along the top represent all the prime numbers since prime numbers have no factors greater than 1 the Phi of any prime number P is simply P minus 1 to calculate Phi of 7 a prime number we count all integers except 7 since none of them share a factor with 7 Phi of 7 equals 6 so if you're asked to find Phi of 20 1377 a prime number you would only need to subtract one to get the solution 20 1376 Phi of any prime is easy to compute this leads to an interesting result based on the fact that the Phi function is also multiplicative that is Phi a times B equals Phi a times Phi B if we know some number n is the product of two primes P 1 and P 2 then Phi of n is just the value of Phi for each prime multiplied together or P 1 minus 1 times p2 minus one