1 00:00:00,000 --> 00:00:01,733 Roots over a field. 2 00:00:01,733 --> 00:00:03,100 3 00:00:03,100 --> 00:00:06,900 So this is one of my favorite propositions, 
but it doesn’t have a name. 4 00:00:06,900 --> 00:00:07,900 5 00:00:07,900 --> 00:00:10,466 Well it doesn’t have a name in this course, 
and it doesn't have a name in general, but 6 00:00:10,466 --> 00:00:14,666 polynomials over any field F of degree 
n greater than or equal to 1 have 7 00:00:14,666 --> 00:00:15,466 8 00:00:15,466 --> 00:00:18,300 at most n roots. Okay? 9 00:00:18,300 --> 00:00:19,300 10 00:00:19,300 --> 00:00:22,733 And it turns out that - so, 
you can approach this in 11 00:00:22,733 --> 00:00:27,166 two ways, you can try to approach this by contradiction 
or you can try to approach this by induction. 12 00:00:27,166 --> 00:00:29,466 The reason why I avoid using 
contradiction is because 13 00:00:29,466 --> 00:00:33,733 what's going to happen is you end up with what 
I like to call a “dot dot dot argument”, where 14 00:00:33,733 --> 00:00:37,533 what you're doing is you do some work 
and you say, “Well just repeat this work 15 00:00:37,533 --> 00:00:41,466 you know because n is a finite number you 
have to only repeat this finitely many times.” 16 00:00:41,466 --> 00:00:44,233 When you want to write a proof like that 
to actually write it out formally, you 17 00:00:44,233 --> 00:00:46,133 probably are going to need to use induction. 18 00:00:46,133 --> 00:00:48,800 So that's what we're going to use here, 
instead of using a “dot dot dot argument”, 19 00:00:48,800 --> 00:00:50,700 we're going to actually just 
formally prove this by induction. 20 00:00:50,700 --> 00:00:55,566 This is a formal proofs class so we should 
probably try to be as formal as we can. 21 00:00:55,566 --> 00:00:56,666 22 00:00:56,666 --> 00:00:59,166 So let P of n be the statement 
that all polynomials over F 23 00:00:59,166 --> 00:01:01,566 of degree n have at most n roots. 24 00:01:01,566 --> 00:01:03,333 So we prove this by induction. 25 00:01:03,333 --> 00:01:04,066 26 00:01:04,066 --> 00:01:08,333 So what does induction need? Need a base 
case, inductive hypothesis, and inductive conclusion. 27 00:01:08,333 --> 00:01:11,033 So notice here that I've outlined 
what P of n actually is 28 00:01:11,033 --> 00:01:14,166 and I find that for a lot of students 
learning induction for the first time, 29 00:01:14,166 --> 00:01:16,300 this is a very useful trick. 30 00:01:16,300 --> 00:01:18,700 Actually write down what you're trying to prove. 31 00:01:18,700 --> 00:01:21,333 Make sure you understand 
where the n falls, so here the n 32 00:01:21,333 --> 00:01:24,866 falls in two spots, there's one 
spot and there's another spot, 33 00:01:24,866 --> 00:01:27,000 and once you have that, really 
understand what the statement is, 34 00:01:27,000 --> 00:01:29,000 you can try to go through the proof. 35 00:01:29,000 --> 00:01:32,333 I really encourage 
students to not just try to… 36 00:01:32,333 --> 00:01:33,066 37 00:01:33,066 --> 00:01:37,000 not just try to blindly go through a proof. Really 
try to understand what you're trying to prove 38 00:01:37,000 --> 00:01:42,233 and then try to prove it. That sounds obvious, 
but a lot of students will try to go through 39 00:01:42,233 --> 00:01:44,466 a question without knowing 
what the question’s asking. 40 00:01:44,466 --> 00:01:46,766 Make sure you understand 
the statement of the question. 41 00:01:46,766 --> 00:01:51,133 If you don't understand the statement, it's 
very difficult to actually go through a proof. 42 00:01:51,133 --> 00:01:52,266 43 00:01:52,266 --> 00:01:54,700 Okay, so let's proceed. 44 00:01:54,700 --> 00:01:57,800 Base case, well the base case, 
what does the base case say? 45 00:01:57,800 --> 00:02:01,666 All polynomials of degree 
1 have at most 1 root. 46 00:02:01,666 --> 00:02:04,900 Okay, so grammatically it's 
not correct, but that's fine. 47 00:02:04,900 --> 00:02:07,166 So when n equals 1, let's 
take our linear polynomial, 48 00:02:07,166 --> 00:02:11,200 it’s degree 1 a x plus b inside 
our polynomial ring over F, 49 00:02:11,200 --> 00:02:15,533 with a non-zero, right? We know that a 
is non-zero because it has degree 1. 50 00:02:15,533 --> 00:02:18,266 Then if I solve for this, if 
I find a root of this, I can 51 00:02:18,266 --> 00:02:22,733 see that x is equal to negative 
a inverse times b is a root. 52 00:02:22,733 --> 00:02:24,500 Notice that this makes sense because 53 00:02:24,500 --> 00:02:27,433 a is a non-zero element, 
which is invertible in a field, 54 00:02:27,433 --> 00:02:28,266 55 00:02:28,266 --> 00:02:30,933 and I’m multiplying by negative 1 
and by b, which both are in my field. 56 00:02:30,933 --> 00:02:34,066 This is perfectly reasonable as an element. 57 00:02:34,066 --> 00:02:36,300 So this must be a root of our polynomial 58 00:02:36,300 --> 00:02:38,533 and this must be in our field, we're done. 59 00:02:38,533 --> 00:02:39,366 60 00:02:39,366 --> 00:02:41,666 So we found a root. 61 00:02:41,666 --> 00:02:44,600 This could be 0, that's perfectly fine. 62 00:02:44,600 --> 00:02:48,000 So the base case, all linear 
polynomials have a root over a field, 63 00:02:48,000 --> 00:02:48,600 64 00:02:48,600 --> 00:02:49,900 that's done. 65 00:02:49,900 --> 00:02:54,066 Inductive hypothesis, well we're just going 
to assume that P k is true for some 66 00:02:54,066 --> 00:02:55,800 natural number k. 67 00:02:55,800 --> 00:02:58,600 So don't forget, quantify your variables, 68 00:02:58,600 --> 00:03:02,666 k is inside N, and it's for 
some and not for all. 69 00:03:02,666 --> 00:03:06,100 So we're assuming that P k is true for some, 
right? If you assume that P k is true for all 70 00:03:06,100 --> 00:03:08,766 natural numbers k, then you're done, 
there's nothing to prove, right? 71 00:03:08,766 --> 00:03:11,533 You've assumed that your 
statement is true all the time, 72 00:03:11,533 --> 00:03:14,066 but what we're doing is we're 
assuming this is true for some 73 00:03:14,066 --> 00:03:17,866 value k and we're going to try to prove that 
it's true for k plus 1. It’s that domino effect. 74 00:03:17,866 --> 00:03:18,600 75 00:03:18,600 --> 00:03:21,133 I'm going through this inductive 
proof, again, kind of slowly 76 00:03:21,133 --> 00:03:23,566 just to remind ourselves 
what induction is. We'll need 77 00:03:23,566 --> 00:03:26,400 all of these elements of 
this proof a little bit later. 78 00:03:26,400 --> 00:03:27,366 79 00:03:27,366 --> 00:03:31,200 So assume that P k is true, then 
how do we prove P k plus 1? 80 00:03:31,200 --> 00:03:33,933 Well what do we need to do? We need 
to take a degree k plus 1 polynomial 81 00:03:33,933 --> 00:03:36,933 and show that it has 
at most k plus 1 roots. 82 00:03:36,933 --> 00:03:40,533 Now we're going to do something a 
little bit sneaky but that's pretty clever. 83 00:03:40,533 --> 00:03:42,800 So take our degree k plus 1 polynomial. 84 00:03:42,800 --> 00:03:44,633 If it has no roots, 85 00:03:44,633 --> 00:03:48,033 so if there's no root of the 
polynomial, then you're done, right? 86 00:03:48,033 --> 00:03:50,866 I mean 0 is less than k plus 1 for sure. 87 00:03:50,866 --> 00:03:54,066 So you're done if you have no roots, so we 
might as well assume that we have a root. 88 00:03:54,066 --> 00:03:55,033 89 00:03:55,033 --> 00:03:57,266 So let's call it c, alright, 
so we have some root, 90 00:03:57,266 --> 00:03:59,633 say c, is an element of our field F. 91 00:03:59,633 --> 00:04:03,700 By the Factor Theorem, since we have a root, we
know that x minus c must be a factor of p of x, 92 00:04:03,700 --> 00:04:05,500 so we're going to write p of x as 93 00:04:05,500 --> 00:04:09,100 x minus c, times q of x 
for some polynomial q of x 94 00:04:09,100 --> 00:04:12,000 of degree k, right? We also know, 
again, because the degree 95 00:04:12,000 --> 00:04:13,266 96 00:04:13,266 --> 00:04:15,633 of the product is the 
sum of the degrees. 97 00:04:15,633 --> 00:04:17,500 x minus c is degree 1, 98 00:04:17,500 --> 00:04:21,233 p of x is degree k plus 1, so 
therefore q of x must have degree k. 99 00:04:21,233 --> 00:04:23,600 100 00:04:23,600 --> 00:04:27,633 By the inductive hypothesis what 
do we know? Well we know that 101 00:04:27,633 --> 00:04:30,700 q of x is a degree k polynomial, so we 
can apply the induction hypothesis. We've 102 00:04:30,700 --> 00:04:34,400 gotten down to a smaller case, that's the 
whole idea behind induction, right? 103 00:04:34,400 --> 00:04:36,900 Take some bigger case, and break it down. 104 00:04:36,900 --> 00:04:39,366 Sometimes you break it 
down into, you know… 105 00:04:39,366 --> 00:04:41,866 usually you break it down to 
degree 1 and degree k, or 106 00:04:41,866 --> 00:04:44,200 something that depends on 
1 so then it depends on k. 107 00:04:44,200 --> 00:04:47,066 Sometimes you break it down like in the 
Fundamental Theorem of Arithmetic, 108 00:04:47,066 --> 00:04:49,466 you broke it down into very smaller parts. 109 00:04:49,466 --> 00:04:53,533 You know so you had some n and you broke 
it down to two factors, that's possible as well. 110 00:04:53,533 --> 00:04:55,733 But the key is you break it down 
to a smaller case that you 111 00:04:55,733 --> 00:04:58,400 know something about because 
of your induction hypothesis. 112 00:04:58,400 --> 00:04:59,166 113 00:04:59,166 --> 00:05:02,466 q of x is degree k, therefore 
it has at most k roots. 114 00:05:02,466 --> 00:05:06,433 q of x has at most k roots, 
x minus c has 1 root, 115 00:05:06,433 --> 00:05:10,633 k plus 1 is k plus 1, p of x 
has at most k plus 1 roots. 116 00:05:10,633 --> 00:05:11,400 117 00:05:11,400 --> 00:05:14,000 Notice that you could have repetition, 118 00:05:14,000 --> 00:05:17,500 c might be a repeated root, 
that's perfectly reasonable. 119 00:05:17,500 --> 00:05:20,733 We've already talked about the 
case where p of x has no roots, 120 00:05:20,733 --> 00:05:22,866 right, so it is possible for a 
polynomial to have no roots, 121 00:05:22,866 --> 00:05:25,066 but that's fine, that's definitely less than n. 122 00:05:25,066 --> 00:05:26,233 123 00:05:26,233 --> 00:05:29,300 And we're done. So therefore, by the 
Principle of Mathematical Induction, 124 00:05:29,300 --> 00:05:31,000 P of n is true for all natural numbers n, 125 00:05:31,000 --> 00:05:34,000 so this last little concluding 
statement wraps it all up nicely. 126 00:05:34,000 --> 00:05:35,133 127 00:05:35,133 --> 00:05:36,966 That's the major ideas here.