About this video
This video introduces Euler's phi function, which counts how many whole numbers from 1 to N share no common factor (other than 1) with N. Computing phi is hard in general, but for a prime P it is simply P - 1, and because phi is multiplicative, phi of a product of two primes is (P1 - 1) x (P2 - 1).
You'll be able to
- calculate phi(N) for a small N by counting numbers that share no factor with N.
- explain why phi(P) = P - 1 when P is prime.
- use phi(P1 x P2) = (P1 - 1)(P2 - 1) for a product of two primes.
Key words
- phi function
- Euler's function phi(N): how many integers from 1 to N share no common factor greater than 1 with N.
- common factor
- A number that divides evenly into two numbers, like 2 for 6 and 8.
- prime number
- A number greater than 1 whose only factors are 1 and itself.
- multiplicative
- A property where phi(A x B) = phi(A) x phi(B), as used in the video for products of primes.
Transcript
- [Voiceover] Euler continued to investigate properties of numbers, specifically the distribution of prime numbers. One important function he defined is called the phi function. It measures the breakability 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 eight we look at all values from one to eight, then we count how many integers eight does not share a factor greater than one with. Notice six is not counted, because it shares a factor of two, while one, three, five and seven are all counted, because they only share a factor of one.
Therefore, phi of eight equals four. 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 one to 1,000. 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 one, the phi of any prime number, P, is simply P minus one. To calculate phi of seven, a prime number, we count all integers, except seven, since none of them share a factor with seven. Phi of seven equals six. So, if you're asked to find phi of 21,377, a prime number, you would only need to subtract one to get the solution, 21,376.
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 one and P two, then phi of N is just the value of phi for each prime multiplied together, or P one minus one, times P two minus one.
Video © Khan Academy, used under CC BY-NC-SA. Watch on Khan Academy. Puzzicle is not affiliated with Khan Academy.