The tricky case is phi(p^k), when we’re multiplying p to itself. For example, phi(3)=(3-1)=2, but phi(3*3)=phi(9)=6, which is different from the answer 2*2 we might expect. For phi(p^k), we can start with all the natural numbers from 1 to p^k and then weed out all the natural numbers that share a factor with p^k. Since prime factorization is unique, and p^k is already in prime factorized form (hooray!), we can see that the only natural numbers we need to weed out are the multiples of p, up to the natural number p^k itself. There are (p^k)/p many of them. We get: phi(p^k) = p^k - (p^k)/p Simplified, this works out to a formula that fits the phi(p) formula we already know! Punchline: phi(p^k) = (p^(k-1))*(p-1)
To the point and very clear. Finally a video that doesn't need to be watched at 2x speed for efficiency, but one that clearly explains everything efficiently. Hats off!
Wow, crazy how hard it was to find a solid explanation that was easy to grasp. Not to mention in little over 2 minutes! Well done.
You just helped explain an entire cryptography chapter in 2 minutes. Thank you!
0:12 what is meant by breakability of a number?
@@sumittete2804 how many times you can factor it i presume
@@dacho707 Thanks 🙏
NO he didn't
Keep in mind phi is multiplicative only when both factors are coprime. Otherwise a very clean explanation.
thanks man
2:02 This is mentioned in the video. P1 and P2 are prime, and therefore coprime
The tricky case is phi(p^k), when we’re multiplying p to itself.
For example,
phi(3)=(3-1)=2, but
phi(3*3)=phi(9)=6, which is different from the answer 2*2 we might expect.
For phi(p^k), we can start with all the natural numbers from 1 to p^k and then weed out all the natural numbers that share a factor with p^k.
Since prime factorization is unique, and p^k is already in prime factorized form (hooray!), we can see that the only natural numbers we need to weed out are the multiples of p, up to the natural number p^k itself. There are (p^k)/p many of them.
We get:
phi(p^k) = p^k - (p^k)/p
Simplified, this works out to a formula that fits the phi(p) formula we already know!
Punchline:
phi(p^k) = (p^(k-1))*(p-1)
To the point and very clear. Finally a video that doesn't need to be watched at 2x speed for efficiency, but one that clearly explains everything efficiently. Hats off!
The greatest two minutes on the entire internet
Phi is only multiplicative if the two numbers are prime. phi(20*34) doesn't equal phi(20)*phi(34).
+Amelia Hartman I think you mean co-prime? e.g. phi(49) = 42 however phi(7)*phi(7) = 36
:54 "Look at this graph"
thumbs down for incorrect statement. phi function is only multiplicative if the two numbers are coprime
the first example that comes to my mind is phi(4) which is equal to 2 (1, 3) and 4 is equal to 2 * 2 so phi(4) would be (2 - 1)*(2 - 1) which is 1.
i think he said if a number is product of two different primes!
he said product of two primes
That's self explainable
@@lassekoivisto4422 Which is a false statement. Phi(25) != Phi(5) * Phi(5)
Could you please help? How do we find n, from fi(n)=20, for example? I mean by pen and paper.
+Petr Fedosov 8
find factors of numbers less than 20 and see how many of them have no factor common with 20.
0:12 what is meant by breakability of a number?
late but it means if or not it can be broken down into factors. Eg 10 can be 5 x5, 15 is 5x3 etc
But why is that the phi(121) = 110? Shouldn't it be 100 since phi(11*11) = 10 * 10???
Oh, I get it. 11 and 11 are not coprime. :)
@@geraldinesanchez4203 you could have deleted your comment
So solve Fermat's little theorem faster ?
0:54 nickel back
Every time it makes me laugh! xD
So totient of a product of 2 different primes is always divisible by 4
May I know why 1 isn't counted? Like 1 and 8 shares the common factor of 1 isn't it?
It doesn't matter, even if you multiply one you'll still get the same answer.
What about phi(25)?
phi(25)=phi(5*5). Since 5 is prime, we should be able to say phi(25)=phi(5*5)=(5-1)(5-1)=16, but phi(25)=20.
+Jordan Engstrom should gcd(n,m)=1
Jordan Engstrom because p^n = p^n - p^(n-1)
Phi(n)=p-1*q-1 where p and q are prime and p!=q
th-cam.com/video/vpJrPYIT9Hc/w-d-xo.html
Have watched this video several times and I always enjoy it
0:12 what is meant by breakability of a number?
@@sumittete2804how many factors it can be broken into.
background music was creepy as hell
good