Question 1

I think Phi[a*b] = phi[a]*phi[b] only works if both a and b are relatively prime.  Is that right?

Accepted Answer

You are correct. Note that Brit said on 1:50 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)

Question 2

In the graph at 1:11 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?

Accepted Answer

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

Question 3

Could somebody tell me how the phi function works?

Accepted Answer

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!

Question 4

This is very confusing. Can anyone explain this method?

Accepted Answer

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.

Question 5

My son does not follow the part where, at 0:48, 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

Accepted Answer

simply count how many integers share no factor with 8, you always include 1. So: 1,3,5,7 = 4  
phi(8) = 4

Question 6

Can't you find the phi of anything by figuring out its prime factorization?

Accepted Answer

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

Question 7

Why does phi(8) = 4??
Please answer.

Accepted Answer

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

Question 8

1:10 Don't prime numbers do have factors greater than 1 (themselves)?

Accepted Answer

Yes, but generally we don't count that and it is not counted to calculate the (phi) of a number.

Question 9

1:51 "remember: we are using gcd(a,b) = 1" What is that supposed to mean?

Accepted Answer

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

Question 10

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.

Accepted Answer

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.

Computer science

Course: Computer science > Unit 2

Euler's totient function

Want to join the conversation?

Video transcript