This is one of the very best math videos on youtube! It is clear in content and in presentation, and it gives us exactly what it promises to give. I can't begin to count the number of really awful math videos I have suffered through before finding this gem!
More informative than several chapters/several weeks of my Abstract Algebra course using Gallian 10th ed. While a good book, there is ample room for improvement. For one, a deep dive into groups first is less helpful than an exploration of groups, rings, and fields contemporaneously.
7 years later, this is super helpful. I really appreciate how powerful reducing polynomials mod p is. I assume it is the case that you can arbitrarily pick a mod p? That's startling to me, but clearly a great relief (if true).
This cleared up some misconceptions I had. This is especially helpful during lockdown, whereas before we would just be sitting around in Uni talking about our coursework and clearing stuff like this up. Thank you!
Very good video. I would like to add that in the brute force method you can say because f(0)=1 and f(1)=3, f has no linear factors so you can skip these right away and look for quadradic factors.
Also, having watched the video, I can actually determine whether polynomials are reducible in some cases (thanks to Eisenstein's criterion). Startling to suddenly have such insight (keeping in mind that not having roots is only part of the solution for degree >3
This is extremely extremely helpful thank you for making something that was explained in the most convoluted way in a lecture easy to understand in one video :)
For Eisenstein does the prime need to be prime in F for polynomials in F[x]? Obviously no because 2 and 3 are not prime in Q, but are considered as prime for the test for Q[x]. So is there any restriction on where p is prime? As of now I'm assuming p prime in Z.
I'm struggling with a counter example to both approaches: x^2+4x+16. By Eisenstein, p=2 (or using 2^2), it should be reducible. If we use Z_3 where p=3 x^2+x+1 shows it should be reducible when x=1 a factor. The original roots are complex to boot. If I introduce x=x+1, then it changes to x^2+6x+21. Then using p=3 satisfies Eisenstein. Is there a way to know when to not trust the false positive given by Eisenstein and the Zp test and/or which element to use to test?
Eisenstein's Criterion cannot tell you that a polynomial is *reducible,* only that it is irreducible. If the criterion fails to apply, then it just tells you nothing; that's not a "false positive."
@@HamblinMath Yes, I understand that. I misspoke and should have said a 'false negative'. Clearly the polynomial is irreducible but it was not caught by either test. Why did the tests fail?
@@brandonk9299 There's not really a reason why the test failed. There isn't one perfect way of telling whether a polynomial is irreducible. That's why we have the several different methods in this video.
08:14 Wouldn't it be faster to multiply two of the three remaining polynomials pairwise to see if we get our original polynomial, instead of doing the long division? (I mean, it's _long_ after all :J ) Or by evaluating the big polynomial at the roots of the shorter ones one by one? (If the big one contains the small one as one of its factors, and we made that factor 0 by substituting its root, the same should happen with the big polynomial at that root if they are supposed to be equal, right?)
in the last example, the polynomial has degree 3 before doing the reduction mod p, so whats the point in reducing if you're just going to do the degree 2,3 test anyway?
The number "-1" doesn't really exist in Z_5, so if we're going to talk about the polynomial "4x^3 + x^2 - x + 3" in Z_5[x], we need to rewrite its coefficients in Z_5.
@@HamblinMath ahhh I see, so if we only need consider the polynomial in Q[X], and it is of degree 2 or 3, it is enough to show using the rational roots test? In essence, if we need to show its irreducible in Q[X] and it’s of a higher degree than 3, THEN I should try the reduction mod P test? Thanks for the swift response by the way you did a great job at explaining in this video:)
@@elliotbradfield3234 There's no surefire way to know which tool(s) will work for any given polynomial. The problem with reducing mod p for a polynomial with degree 4 or higher is that you'd still need to consider the possibility that it has a degree 2 factor.
32:42 Is there any systematic way to come up with a polynomial in the modulus so that it would be GUARANTEED that for each argument it will give a DIFFERENT result? (that is, no situations like in your example, that f(2) = f(3) = f(1) = 2; all of them should give something else).
@@astrophilip Hmm... Indeed it seems to generate different results for each `x`. However, some arrangements of those results seem to be unreachable :/ Let's try the simplest one, for p=5, so p-1=4, and there's only one number coprime to it: 3, so let m=3, and then a·x³+c is our polynomial. First, let's check different a's in columns: x | x³ 2·x³ 3·x³ 4·x³ 0 | 0 0 0 0 1 | 1 2 3 4 2 | 3 1 4 2 3 | 2 4 1 3 4 | 4 3 2 1 For each of these columns, we can shift it by the offset c around the modulus and get 4 other such tables, or 4·5=20 different arrangements of the numbers from 0 to 4. But the number of all POSSIBLE arrangements is of course 5!=120, so we're missing 100 of them :q Even if we suppose that we only use the numbers 1..4 for our x, and replace 0 with whatever number is missing in the +c tables (so that the results were also in the 1..4 range), it's still only 20 out of 4!=24 possible arrangements. Here are the ones we're missing for 4-element sets: 1234, 2413, 3142, 4321 The 1234 can be accounted for if we allow the "identity" function x¹, but what about the other three? *Edit:* Nevermind, it seems that a·x¹ does the job, since: 1,2,3,4 ·2 = 2,4,1,3 1,2,3,4 ·3 = 3,1,4,2 1,2,3,4 ·4 = 4,3,2,1 Now I need to check if it still works for bigger moduli...
You said that if a polynomial has a root, it is reducible. But x^2+2 has root 1 in Z_3.. 1^2+2 = 3 = 0 in Z_3 and I can not find any factors of this polynomial. Can you help me please?
You are correct that 1 is a root of x^2+2, and thus x^2+2 must be reducible. In fact, we know that x - 1 (which is equal to x+2 in Z_3) must be a factor of x^2+2. Doing polynomial long division shows us that x^2+2 = (x+2)(x+1).
No, if you can't find a prime for which Eisenstein's criterion applies, you cannot conclude anything about the polynomial. For example, neither x^2 + 1 and x^2 - 1 have a prime that works for Eisenstein's criterion, and one is irreducible and the other is reducible.
It has to have a factor of a combination of (1 and 3) or (2 and 2). If you're going to prove either, you only need to prove one of the factors. The 1 and 3 combination can't exist if there is no 1. Thus, to save yourself the time, you only need to prove that 1 or 2 can't exist, and leave 3 alone. You can use 3, but you're just creating more work for yourself for the same outcome.
this man explains everything so well. im pretty sure a fifth-grader can understand irreducible polynomials by watching this video LMAOO
AGREE
So true
Yess Yess
This is the most clear and well organized explanation ever. Thank you soooo much!
This is one of the very best math videos on youtube!
It is clear in content and in presentation, and it gives us
exactly what it promises to give. I can't begin to count
the number of really awful math videos I have suffered
through before finding this gem!
gotta love line wrapping
It's so true. 1/10 math videos are worthwhile.
More informative than several chapters/several weeks of my Abstract Algebra course using Gallian 10th ed. While a good book, there is ample room for improvement. For one, a deep dive into groups first is less helpful than an exploration of groups, rings, and fields contemporaneously.
For the first time in forever, I learned irreducible polynomial!!!!! Thank you James for such useful video!! :)
7 years later, this is super helpful. I really appreciate how powerful reducing polynomials mod p is.
I assume it is the case that you can arbitrarily pick a mod p? That's startling to me, but clearly a great relief (if true).
Teaching this way is absolutely magical. Wow sir i got refreshed by ur lecture. Thanks a ton sir
THIS IS AMAZING. THANK YOU!
Yuppp it is really
Hi
OH MY GOD YESSS
I think you saved my life. So insanely helpful and explained amazingly well.
this is actually amazingly clear and helpful, thank you so much!
This cleared up some misconceptions I had. This is especially helpful during lockdown, whereas before we would just be sitting around in Uni talking about our coursework and clearing stuff like this up. Thank you!
Really great explanation and method! You deserve so many more views thank you!
I am a little bit shocked. What a great explanation ...
thank you Sir
Very good video. I would like to add that in the brute force method you can say because f(0)=1 and f(1)=3, f has no linear factors so you can skip these right away and look for quadradic factors.
Excellent. I’m not strong at algebra and I understood all. Nice job
Honestly, this is very good. More of this please.
what a classy class sir. May Allah bless you. Was stuck in this topic. thank you so much sir
damn, i have my abstract algebra exam tomorrow and this helped loads
Excellent explanation Thank you so much Sir 🙏🏻
Also, having watched the video, I can actually determine whether polynomials are reducible in some cases (thanks to Eisenstein's criterion). Startling to suddenly have such insight (keeping in mind that not having roots is only part of the solution for degree >3
Nice revision about polynomial division and also methods to check irreducibility (especially method 1 and 2)
Thank you Sir, you gave me exactly what I need. May God bless your work
This is extremely extremely helpful thank you for making something that was explained in the most convoluted way in a lecture easy to understand in one video :)
This is extremely extremely helpful thank you
Completely thankful. Cheers from Granada, Spain.
Very helpful, thank you!
holy shit this is my saving grace. thank you so much
My lifesaver video
Absolutely CRYSTAL CLEAR！Thank you very much sir!
V nice explanation ✨
Thank You sir very very much. It's so easy to understand the concept of it.
You made this concept really easy for me.... Thanku so much 😊
Cheers James, this helped me alot in Ring Theory.
Thanks a lot @James Hamblin
This is so well explained!!!!!!!!!!!!!!!!!!!!!! Thank you so much.
Very nice..its help me a lots🙂
Thank you sir
short+sharp=amazing job!
Sooooo good.
So well explained! Watching your video gave me confidence that I can pass my Crypto class :)
You are amazing. Thanks ❤
Thank you so much, James! Very helpful!
because deg f has to be the same as deg f mod p
and so p prime and p not divide with the leading coefficient
great video
Super helpful and clear, thank you so very much!
Thanks for this video🙂
Thank you so so much. Great explanations.
wish you said something about if eisenstein's criterion were not fulfiled
For Eisenstein does the prime need to be prime in F for polynomials in F[x]? Obviously no because 2 and 3 are not prime in Q, but are considered as prime for the test for Q[x]. So is there any restriction on where p is prime? As of now I'm assuming p prime in Z.
Correct, the criterion as I've stated it only applies in Q for primes in Z.
thank u very much sir u have explained in a very nice manner
Thank you very much. It was really helpful!!
I'm struggling with a counter example to both approaches: x^2+4x+16. By Eisenstein, p=2 (or using 2^2), it should be reducible. If we use Z_3 where p=3 x^2+x+1 shows it should be reducible when x=1 a factor. The original roots are complex to boot. If I introduce x=x+1, then it changes to x^2+6x+21. Then using p=3 satisfies Eisenstein. Is there a way to know when to not trust the false positive given by Eisenstein and the Zp test and/or which element to use to test?
Eisenstein's Criterion cannot tell you that a polynomial is *reducible,* only that it is irreducible. If the criterion fails to apply, then it just tells you nothing; that's not a "false positive."
@@HamblinMath Yes, I understand that. I misspoke and should have said a 'false negative'. Clearly the polynomial is irreducible but it was not caught by either test. Why did the tests fail?
@@brandonk9299 There's not really a reason why the test failed. There isn't one perfect way of telling whether a polynomial is irreducible. That's why we have the several different methods in this video.
Sir if f(x)=x^3-tx-1, given: 't' is integer. For which value of 't', f(x)is irrudicible over Q[x].
just want to say thanks for this video!
respect man!!!
Thank you sir 🥰
legend
very good thank you
Sir how we can select the value of p in given polinomial?
08:14 Wouldn't it be faster to multiply two of the three remaining polynomials pairwise to see if we get our original polynomial, instead of doing the long division? (I mean, it's _long_ after all :J ) Or by evaluating the big polynomial at the roots of the shorter ones one by one? (If the big one contains the small one as one of its factors, and we made that factor 0 by substituting its root, the same should happen with the big polynomial at that root if they are supposed to be equal, right?)
Thank you james. It helped
thank you very much
That's one amazing video
Awesome video! Has helped a lot, Thankss :)))))
Having watched this video, I feel like just stop attending my abstract algebra class.😀👍👍
in the last example, the polynomial has degree 3 before doing the reduction mod p, so whats the point in reducing if you're just going to do the degree 2,3 test anyway?
The number "-1" doesn't really exist in Z_5, so if we're going to talk about the polynomial "4x^3 + x^2 - x + 3" in Z_5[x], we need to rewrite its coefficients in Z_5.
@@HamblinMath ahhh I see, so if we only need consider the polynomial in Q[X], and it is of degree 2 or 3, it is enough to show using the rational roots test? In essence, if we need to show its irreducible in Q[X] and it’s of a higher degree than 3, THEN I should try the reduction mod P test? Thanks for the swift response by the way you did a great job at explaining in this video:)
@@elliotbradfield3234 There's no surefire way to know which tool(s) will work for any given polynomial. The problem with reducing mod p for a polynomial with degree 4 or higher is that you'd still need to consider the possibility that it has a degree 2 factor.
Thank you it's very satisfying
Thank you a lot !
Thnku so much sir
Finally understand.....
Thank you sir
Thanks a ton , professor !!
Your explanation is really great !!
Please upload other concepts too !!
very clear ... thank you!
so helpful, thank you!
32:42 Is there any systematic way to come up with a polynomial in the modulus so that it would be GUARANTEED that for each argument it will give a DIFFERENT result? (that is, no situations like in your example, that f(2) = f(3) = f(1) = 2; all of them should give something else).
a*x^m + c, where m is relatively prime to (p-1) should work. i wonder if there are other cases
@@astrophilip Hmm... Indeed it seems to generate different results for each `x`. However, some arrangements of those results seem to be unreachable :/
Let's try the simplest one, for p=5, so p-1=4, and there's only one number coprime to it: 3, so let m=3, and then a·x³+c is our polynomial.
First, let's check different a's in columns:
x | x³ 2·x³ 3·x³ 4·x³
0 | 0 0 0 0
1 | 1 2 3 4
2 | 3 1 4 2
3 | 2 4 1 3
4 | 4 3 2 1
For each of these columns, we can shift it by the offset c around the modulus and get 4 other such tables, or 4·5=20 different arrangements of the numbers from 0 to 4. But the number of all POSSIBLE arrangements is of course 5!=120, so we're missing 100 of them :q
Even if we suppose that we only use the numbers 1..4 for our x, and replace 0 with whatever number is missing in the +c tables (so that the results were also in the 1..4 range), it's still only 20 out of 4!=24 possible arrangements. Here are the ones we're missing for 4-element sets:
1234, 2413, 3142, 4321
The 1234 can be accounted for if we allow the "identity" function x¹, but what about the other three?
*Edit:* Nevermind, it seems that a·x¹ does the job, since:
1,2,3,4 ·2 = 2,4,1,3
1,2,3,4 ·3 = 3,1,4,2
1,2,3,4 ·4 = 4,3,2,1
Now I need to check if it still works for bigger moduli...
Sir , what is the counter example for the converse statement of mod p test???
Amazing!! Thank you!
THANKS A LOT
Thanks so much for this video
Nice job!!!!! Thank you!
You said that if a polynomial has a root, it is reducible. But x^2+2 has root 1 in Z_3.. 1^2+2 = 3 = 0 in Z_3 and I can not find any factors of this polynomial. Can you help me please?
You are correct that 1 is a root of x^2+2, and thus x^2+2 must be reducible. In fact, we know that x - 1 (which is equal to x+2 in Z_3) must be a factor of x^2+2. Doing polynomial long division shows us that x^2+2 = (x+2)(x+1).
@@HamblinMath Oh, I have not realised these! Thank you very much for a quick response! By the way, perfect video.
Is x^2 + 2x +2 in F3[x] irreducible in F3[x] ?
Thanks Bro
Show that a polynomial of degree 3 in z3[x]
Please solve my problem..i am in troublee...please sir
fanastic!
Just wondering, when is Rabin's test for irreducibilty used?
Thank you sir!!!
Very helpful
Thank you 🥈
wow... nice,,,,
If a polynomial fails eisensteins criterion, does that mean it is reducible? Or does it not help us at all?
No, if you can't find a prime for which Eisenstein's criterion applies, you cannot conclude anything about the polynomial. For example, neither x^2 + 1 and x^2 - 1 have a prime that works for Eisenstein's criterion, and one is irreducible and the other is reducible.
James Hamblin thank you so much!
Thank you..
Supprbbb🔥
Good work sir. Please upload sylow's theorem problems
what about x^3+2x+3 I have two roots but I cant reduce it!
If x=a is a root of your polynomial, then x-a is a factor. If you can't see how to factor it, try polynomial long division.
Its really helped me a lot thanks sir
hi
i need pdf file about this lecture ? please
Wow.!!!!!!!!
At 5:10 why do you take 1 amd 2 but not 3?
if we choose degree three, there are more cases to consider and hence clumsy.
namely,
x^3+x^2+x+1
x^3+x^2+x
x^3+x^2+1
x^3+x+1
x^3+x
x^3+1
x^3
It has to have a factor of a combination of (1 and 3) or (2 and 2). If you're going to prove either, you only need to prove one of the factors. The 1 and 3 combination can't exist if there is no 1. Thus, to save yourself the time, you only need to prove that 1 or 2 can't exist, and leave 3 alone. You can use 3, but you're just creating more work for yourself for the same outcome.
👍
ty