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

Measuring the divisibility of a number. Created by Brit Cruise.

Want to join the conversation?

  • leaf green style avatar for user Eddie
    I think Phi[a*b] = phi[a]*phi[b] only works if both a and b are relatively prime. Is that right?
    (61 votes)
    Default Khan Academy avatar avatar for user
    • leaf red style avatar for user DEHD93
      You are correct. Note that Brit said on that Euler's Phi function is multiplicative, not completely multiplicative.
      If a function f is multiplicative, then if (a,b) = 1 (gcd) → f(a*b) = f(a)*f(b)
      If a function f is completely multiplicative, then for every a and b → f(a*b) = f(a)*f(b)
      (66 votes)
  • piceratops ultimate style avatar for user Ari Mendelson
    In the graph at in the video, it seems that the set of dots coalesces into a straight line. You said those were the prime numbers. But there seems to be at least three other sets of dots that more or less coalesce into straight lines as well. Is there anything special about those sets of numbers?
    (26 votes)
    Default Khan Academy avatar avatar for user
    • aqualine ultimate style avatar for user Hannah
      The above answer is very helpful, though having a miscalculation

      When n and p are relatively prime, φ(n*p) = φ(n) * φ(p)
      Suppose p is a prime number
      φ(2p) = φ(2) * φ(p) = 1 * (p-1) = p - 1 -> k = 1/2
      φ(3p) = φ(3) * φ(p) = 2 * (p-1) = 2p - 2 -> k = 2/3
      φ(5p) = φ(5) * φ(p) = 4 * (p-1) = 4p - 4 -> k=4/5
      φ(6p) = φ(2) * φ(3) * φ(p) = 1 * 2 * (p-1) = 2p - 2 -> k = 2/6 = 1/3
      φ(7p) = φ(7) * φ(p) = 6 * (p-1) = 6p - 6 -> k = 6/7
      φ(10p) = φ(2) * φ(5) * φ(p) = 1 * 4 * (p-1) = 4p - 4 -> k = 4/10 = 2/5
      ... ...
      There're many possible values for the slope k
      However, the smaller the n is, the clearer the straight line can be seen
      (8 votes)
  • winston baby style avatar for user Markiv
    Could somebody tell me how the phi function works?
    (7 votes)
    Default Khan Academy avatar avatar for user
    • leaf red style avatar for user Noble Mushtak
      Here's how the phi function works.
      The phi function of n (n is a counting number, such as 1 2, 3, ...) counts the number of numbers that are less than or equal to n and only share the factor of 1 with n.
      Example:
      phi(15)
      1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
      15 has the factors of 3 and 5, so all multiples of 3 and 5 share the factor of 3 or 5 with 15. Therefore, they aren't counted.
      1, 2, 4, 7, 8, 11, 13, 14
      There are 8 numbers that only share the factor of 1 with 15. Therefore, phi(15)=8.

      I hope this helps!
      (24 votes)
  • hopper cool style avatar for user Yosef
    This is very confusing. Can anyone explain this method?
    (7 votes)
    Default Khan Academy avatar avatar for user
    • hopper cool style avatar for user Chuck Towle
      The proof of Phi(1st Prime) * Phi(2nd Prime) =Phi(1st Prime * 2nd Prime) seems obvious to me.
      Assume A and B are Prime
      We know that Phi(A) = A-1 and Phi(B) = B-1

      Between 1 and (A*B), inclusive, there are B occurrences of numbers divisible by A by the definition of multiplication. Each time you add another A, you find another mutiple of A. And if you add A to itself B times, you would have B occurrences of multiples of A.
      And between 1 and (A*B) there are also A occurrences of numbers divisible by B.
      And because A and B are primes, there are no other occurences where the multiples overlap.
      When you exclude the final number (A*B) there are (A-1) occurrences of numbers divisible by A and there are (B-1) occurences of numbers divisible by A.
      The total numbers below (A*B) that are divisible by A or B is (A-1)+(B-1).
      So the PHI(A*B) = All Numbers less than (A*B) less (A-1)+(B-1)
      PHI(A*B) = (A*B-1) - ((A-1)+(B-1))
      = A*B - 1- A + 1 - B + 1
      = A*B -A - B +1 =(A-1)(B-1)
      So Phi(A) = (A-1) and Phi(B) = (B-1) and Phi(A*B) = (A-1)*(B-1)
      So for all primes numbers A and B, Phi(A)*Phi(B)=Phi(A*B)
      I am not sure this is very eloquent, but I think the proof is correct.
      (13 votes)
  • blobby green style avatar for user Leila Wheless
    My son does not follow the part where, at , when trying to find the phi of 8, the number 4 is given as a solution. He can't understand what "4" has to do with any of it. Thanks!! LW
    (4 votes)
    Default Khan Academy avatar avatar for user
  • aqualine ultimate style avatar for user Thos Os Sal's Strong
    Can't you find the phi of anything by figuring out its prime factorization?
    (4 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      Yes, one can find the phi of a positive integer by figuring out its prime factorization

      In general, for each of its prime factors, p, with a multiplicity, k
      phi= product of ( p^(k-1)*(p-1) ) for all of its factors

      e.g. 360=8 * 9 * 5=2^3 * 3^2 * 5
      phi(360)= (2^2) * (2-1) * (3^1) * (3-1) * (5^0) * (5-1)
      phi(360)= 4 * 1 * 3 * 2 * 1 * 4
      phi(360)= 96

      Unfortunately, factoring numbers is a hard problem when the numbers become large. In fact, RSA and some other cryptographic schemes rely on large numbers being hard to factor (someone who could factor these big numbers would be able to crack these codes).

      Hope this makes sense
      (5 votes)
  • leaf grey style avatar for user Christopher Smitho (Offline)
    Why does phi(8) = 4??
    Please answer.
    (2 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Enn
      The Euler's Totient Function counts the numbers lesser than a number say n that do not share any common positive factor other than 1 with n or in other words are co-prime with n.
      For 8 :
      1 and 8 are co-prime as the only common factor is 1 itself
      2 and 8 have a common factor 2
      3 and 8 are co-prime
      4 and 8 have a common factor 2
      5 and 8 are co-prime
      6 and 8 have a common factor 2
      7 and 8 are co-prime
      8 and 8 have a common factor 2
      Hence, there are 4 numbers(1,3,5 and 7) that are lesser than 8 and are co-prime with it.
      So, phi(8) = 4
      (6 votes)
  • hopper cool style avatar for user Florian Melzer
    Don't prime numbers do have factors greater than 1 (themselves)?
    (2 votes)
    Default Khan Academy avatar avatar for user
  • hopper cool style avatar for user Florian Melzer
    "remember: we are using gcd(a,b) = 1" What is that supposed to mean?
    (2 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      It means the greatest common denominator (gcd) of a and b are 1.
      When the gcd(a,b)=1, then a and b are coprime, that is, they don't share any prime factors.
      We can only use phi(a*b)=phi(a)*phi(b) when a and b don't share common factors i.e. gcd(a,b)=1

      e.g phi(7)=6 ,phi(8)=4
      7 and 8 share no prime factors i.e. gcd(a,b)=1
      phi(56)=phi(7)*phi(8)=6*4=24

      e.g. phi(8)=4,phi(12)=4
      8 and 12 share common prime factors (both have 2 as a prime factor)
      gcd(8,12)=4
      phi(96)=32 which does not equal phi(8)*phi(12)=16

      Hope this makes sense
      (3 votes)
  • orange juice squid orange style avatar for user tigertcb
    Is there a good way to determine if a number is prime? It seems like the phi function is useful for primes, but only if we know from the start that the number is prime.
    (2 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      The 100% sure way to tell if n is prime is to check all numbers > 1 and <= sqrt(n) for factors. If there are none it is prime. Of course, for large numbers it's really slow.

      So, in practice probabilistic tests are used to see if n is probably prime. If we assume n is prime, then we can assume it's value of phi is just n-1. We can test whether that assumption is false, by using properties established by Euler's Theorem i.e. a^phi(n) mod n = 1 mod n, where a is coprime to n. If we can find any values of a that don't satisfy that property then n is not prime. If instead, we test a bunch of values of a, and none of them fail, we can become more and more satisfied that n is probably prime.
      (2 votes)

Video 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.