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.

### Course: Computer science theory>Unit 2

Lesson 4: Modern cryptography

# Euler's totient function

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

## Want to join the conversation?

• I think Phi[a*b] = phi[a]*phi[b] only works if both a and b are relatively prime. Is that right?
• 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)
• 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?
• 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
• Could somebody tell me how the phi function works?
• 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!
• This is very confusing. Can anyone explain this method?
• 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.
• 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
• simply count how many integers share no factor with 8, you always include 1. So: 1,3,5,7 = 4
phi(8) = 4
• Can't you find the phi of anything by figuring out its prime factorization?
• 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
• Why does phi(8) = 4??
• 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
• Don't prime numbers do have factors greater than 1 (themselves)?
• Yes, but generally we don't count that and it is not counted to calculate the (phi) of a number.
• "remember: we are using gcd(a,b) = 1" What is that supposed to mean?
• 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