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!
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!
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.
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 :)
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.
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?)
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...
When you were testing mod p 32:28 , and you said that 4x³+x²+4x+3 was irreducible in Z_5[x], testing all elements from Z_5 on f(x) is not a condition to prove that. Consider x⁴+2x²+1, if we follow your method in Z_3[x] f(0)=1, f(1)=1 and f(2)=1. Then the pollinomial should be irreducible, but x⁴+2x²+1=(x²+1)².
@@elianof3352 As stated in the video, testing all possible roots to show that a polynomial is reducible only works for polynomials of degree 2 or 3. Your example illustrates why it doesn't work for polynomials of degree 4 or higher.
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.
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.
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.
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
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.
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 because -x^3 is congruent to x^3 in mod 2. In fact, -1 doesn't exist in Z_2, so -x^3 is just incorrect. It is so easy to miss these small things in an Abstract Algebra text, as they are barely explained if at all.
This is the most clear and well organized explanation ever. Thank you soooo much!
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 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.
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).
I think you saved my life. So insanely helpful and explained amazingly well.
Teaching this way is absolutely magical. Wow sir i got refreshed by ur lecture. Thanks a ton sir
Really great explanation and method! You deserve so many more views thank you!
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!
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.
this is actually amazingly clear and helpful, thank you so much!
THIS IS AMAZING. THANK YOU!
Yuppp it is really
Hi
OH MY GOD YESSS
what a classy class sir. May Allah bless you. Was stuck in this topic. thank you so much sir
Honestly, this is very good. More of this please.
Excellent. I’m not strong at algebra and I understood all. Nice job
I am a little bit shocked. What a great explanation ...
thank you Sir
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 :)
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.
Very helpful, thank you!
Thank you Sir, you gave me exactly what I need. May God bless your work
Excellent explanation Thank you so much Sir 🙏🏻
Completely thankful. Cheers from Granada, Spain.
Nice revision about polynomial division and also methods to check irreducibility (especially method 1 and 2)
Cheers James, this helped me alot in Ring Theory.
This is so well explained!!!!!!!!!!!!!!!!!!!!!! Thank you so much.
Thank You sir very very much. It's so easy to understand the concept of it.
damn, i have my abstract algebra exam tomorrow and this helped loads
Very nice..its help me a lots🙂
Thank you sir
You made this concept really easy for me.... Thanku so much 😊
Absolutely CRYSTAL CLEAR！Thank you very much sir!
This is extremely extremely helpful thank you
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?)
wish you said something about if eisenstein's criterion were not fulfiled
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...
When you were testing mod p 32:28 , and you said that 4x³+x²+4x+3 was irreducible in Z_5[x], testing all elements from Z_5 on f(x) is not a condition to prove that. Consider x⁴+2x²+1, if we follow your method in Z_3[x]
f(0)=1,
f(1)=1 and
f(2)=1. Then the pollinomial should be irreducible, but x⁴+2x²+1=(x²+1)².
@@elianof3352 As stated in the video, testing all possible roots to show that a polynomial is reducible only works for polynomials of degree 2 or 3. Your example illustrates why it doesn't work for polynomials of degree 4 or higher.
holy shit this is my saving grace. thank you so much
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.
Thank you so much, James! Very helpful!
Sir how we can select the value of p in given polinomial?
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.
short+sharp=amazing job!
So well explained! Watching your video gave me confidence that I can pass my Crypto 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.
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
Super helpful and clear, thank you so very much!
V nice explanation ✨
Thank you so so much. Great explanations.
Sir , what is the counter example for the converse statement of mod p test???
Sir if f(x)=x^3-tx-1, given: 't' is integer. For which value of 't', f(x)is irrudicible over Q[x].
thank u very much sir u have explained in a very nice manner
Just wondering, when is Rabin's test for irreducibilty used?
You are amazing. Thanks ❤
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
Thanks a lot @James Hamblin
My lifesaver video
Is x^2 + 2x +2 in F3[x] irreducible in F3[x] ?
Thank you very much. It was really helpful!!
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!
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.
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.
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.
hi
i need pdf file about this lecture ? please
just want to say thanks for this video!
Awesome video! Has helped a lot, Thankss :)))))
Thanks for this video🙂
Sooooo good.
Thanks a ton , professor !!
Your explanation is really great !!
Please upload other concepts too !!
Thank you james. It helped
Show that a polynomial of degree 3 in z3[x]
Please solve my problem..i am in troublee...please sir
great video
That's one amazing video
Thank you it's very satisfying
so helpful, thank you!
very clear ... thank you!
Thank you sir 🥰
Amazing!! Thank you!
respect man!!!
Thanks so much for this video
Nice job!!!!! Thank you!
very good thank you
Thank you a lot !
Thank you sir!!!
Having watched this video, I feel like just stop attending my abstract algebra class.😀👍👍
Thnku so much sir
thank you very much
Thank you 🥈
Thank you sir
Good work sir. Please upload sylow's theorem problems
Very helpful
wow... nice,,,,
THANKS A LOT
legend
Supprbbb🔥
Thanks Bro
Thank you..
Its really helped me a lot thanks sir
Finally understand.....
fanastic!
👍
08:37 it should be -x^3+x+1
no because -x^3 is congruent to x^3 in mod 2. In fact, -1 doesn't exist in Z_2, so -x^3 is just incorrect. It is so easy to miss these small things in an Abstract Algebra text, as they are barely explained if at all.