Hello everyone. Welcome to Week 11 part 1 of Carmen's Core Concepts, my name is Carmen Bruni, and in these videos we talk about the current week in Math 135.
This time I've decided to break it up into two parts, part $1$ and part $2$, and I've decided to make part $1$ a more theoretical part where we talk more about the proofs related to the theorems that we did this week, and in part $2$ we talk about the applications of the theorems. So in theory, the two parts are independent, however you should probably watch part 1 before you watch part 2 unless you feel very comfortable with the theory, then you can go ahead straight to part 2, either way is fine. With that being said, let's begin.
So here are the topics that I'm going to talk about this week. We're going to start with a couple of polynomial statements that I'm not going to prove but that are pretty important, and then as you can see here, we have - what is this, $6$ named theorems. Remainder Theorem, Factor Theorem, Roots Over a Field which arguably is just as important as some of these other theorems but doesn't have a name, Fundamental Theorem of Algebra, Complex Polynomials of Degree $n$ Have $n$ Roots, then the proof of that, the Rational Roots Theorem, and the Conjugate Roots Theorem.
So notice in the middle here, I've kind of glossed over this but Fundamental Theorem of Algebra is one of the more important statements in mathematics. Anything called the Fundamental Theorem of blah, that's probably a pretty important theorem and you should know it.
That's all I really have to say. Here we'll talk a little bit more about the Fundamental Theorem of Algebra in a minute. We won't talk about the proof. The proof is just a little bit beyond what we want to do in this course.
Let $f(x)$ and $g(x)$ be non-zero polynomials over a field $\mathbb{F}$ such that they are not additive inverses. Then
I want to talk about each of these a little bit individually.
Why do I need $f(x)$ and $g(x)$ to not be additive inverses? Well for the first one, then we would get the degree of the $0$ polynomial. In this course, we say that the $0$ polynomial is undefined. Some textbooks, and it's not unreasonable to do so, but it does require a little bit of understanding, define the degree of the 0 polynomial to be $-\infty$, and it’s so that statements like this actually hold for free, right? $-\infty$ should, morally speaking, be less than any integers, so that's perfectly fine, but we're not going to do that. We just say the degree of the 0 polynomial is undefined.
That being said, it's always good to double check some of these theorems. So why is this the first one "$\leq$" statement? Well the leading terms of $f(x)$ and $g(x)$ could cancel each other out, that's possible, so you actually might get the strictly less than case, okay? Usually though, as long as those two terms don't cancel each other out, this will be an equality, that's something you can check.
These aren’t hard to prove, but I'm not going to prove them here. We proved the last one in class, I mentioned the second one in class, and the first one is actually not too hard either. Just write out $f(x)$ and $g(x)$ in terms of polynomials, add them up, and then argue what the degree of the sum must be.
Let me talk a little about the last one. The second one is also fairly clear once you do it. You just multiply the leading two terms and that'll be the sum. You never get $0$ when you multiply the two terms because you're over a field, so you can't get cancellation so this is actually okay, but this does require that we have a field.
$f(x) \mid g(x)$ and $g(x) \mid f(x)$, or what I’d like to say about this one is I'd like to relate back to the integer case. So if I have $a \mid b$ and $b \mid a$, then what do we know? As integers, we think about this then we say, “Okay well we know that $a=b$,” that’s a possibility, and the case that a lot of us forget is that $a=-b$.
So realistically, $a=\pm b$, and it turns out that $\pm 1$ happen to be the only two elements that are invertible in the integers, and that actually matters a little bit. You'll see where that comes up in the proof, but I won't talk about that anymore.
What I'm trying to get at here is the analogy here, right? So we have these polynomials, we have this notation for integers, how do these two things relate? Well here we don't get just $\pm 1$, we get any invertible element in our field.
So something to think about here, right? When you see a new problem in an unfamiliar situation, reduce back to a situation that is familiar to you, and try to reason out what the correct statement and the correct proof should be there. It’s a good trick in mathematics. If the problem is too hard, get rid of it and solve an easier one. This works well for, you know, assignments and when you're doing work on napkins and stuff like that, but you know be careful on a test, right? Don't just change the problem, make it easier, and then solve the easier problem. It is a good tactic to get a feeling for what the problem saying.
So we're going to start with our one by one theorem crunching here, and then like I said in the next part, we'll talk about the applications. So what does the Remainder Theorem say? Well it gives us a way to divide polynomials when we have a very specific form; if we just care about the remainder.
Theorem (RT): Suppose that $f(x) \in \mathbb{F}[x]$ and that $c \in \mathbb{F}$. Then, the remainder when $f(x)$ is divided by $x-c$ is $f(c)$.
This will become important for us when we talk about the Factor Theorem. It turns out that we actually divide by these types of polynomials more than you might imagine.
That being said, see if you can give this proof a shot. It's not too bad, none of these are too, too bad. Some of them are a little bit more involved, but the proof technique part of it is not too bad.
How do we go through this? Well this is the Remainder Theorem, so we need to talk about a remainder, so we should actually just divide $f(x)$ this $x-c$ using the Division Algorithm for Polynomials.
$$f(x)=(x-c)q(x)+r(x)$$Then we need to argue whether the remainder is $f(c)$. Well if we're dividing by a linear polynomial, we know the remainder must be constant, and the question is, “Well what constant is it,” and that's what we can try to figure out.
So using the Division Algorithm gives us these polynomials $q(x)$ and $r(x)$. They turn out to be unique when we require that $r(x)=0$ or $\deg(r(x)) < \deg(x-c)$, and $\deg(x-c)$, we know that, that's $1$.
So what does that mean? Well that means that $\deg(r(x))=0$ or $r(x)=0$, but the only degree $0$ polynomials are constants, so therefore $r(x)=k$ for some $k \in \mathbb{F}$, and here $k$ can be $0$ which also encompasses the first remainder case.
So how do we determine what $k$ is? Well we have this relationship between $f(x)$, and $q(x)$, and $r(x)$, and $x-c$, so let's actually substitute a value in for $x$. And what value are we going to substitute in? We're going to substitute in the value $x=c$. That makes sense, $c$ is inside my field, this is perfectly reasonable.
$$f(c)=(c-c)q(c)+r(c)=r(c)=k \quad \blacksquare$$That's the Remainder Theorem, and it's particularly useful for us to talk about this in the context of the Factor Theorem.
How does this help us with the Factor Theorem? Well it says okay well, I know what the remainder is and I want to know that $x-c$ is a factor, well then I want a $0$ remainder. So therefore I would want $f(c)=0$, and if I get $f(c)=0$, then I know that $c$ is a root and all of this kind of ties together to the Factor Theorem.
Theorem (FT): Suppose that $f(x) \in \mathbb{F}[x]$ and $c \in \mathbb{F}$. Then the polynomial $x-c$ is a factor of $f(x)$ if and only if $f(c)=0$, that is, $c$ is a root of $f(x)$.
I've kind of already given you the proof, but if you don't see it yet, you should try it.
It's actually pretty quick. So when is $x-c$ a factor of $f(x)$? Well if I divide by $x-c$, if it’s a factor, then the remainder must be $0$. That's just by the Division Algorithm for Polynomials, right, the quotient and the remainder must be unique so if I divide by $x-c$ and it's a factor, then it must have a $0$ remainder.
And when does this have a $0$ remainder? Well the Remainder Theorem says that $r(x)=f(c)$, but $r(x)=0$, so therefore $f(c)=0$, and this goes in both directions, right?
So the remainder is always $f(c)$ and $f(c)=0$ if and only if $r(x)=0$ because they're equal to each other. $\; \blacksquare$
That's actually it, it's actually pretty quick. I've written it out pretty compactly and pretty quickly, but the idea I think is pretty clear. And this gives us the Factor Theorem. This is useful for finding roots which we'll see in the next video.
Roots over a field. So this is one of my favorite propositions, but it doesn’t have a name. Well it doesn’t have a name in this course, and it doesn't have a name in general.
Proposition: Prove that a polynomial over ant field $\mathbb{F}$ of degree $n \geq 0$ has at most $n$ roots.
It turns out that you can approach this in two ways, you can try to approach this by contradiction or you can try to approach this by induction. The reason why I avoid using contradiction is because what's going to happen is you end up with what I like to call a “dot dot dot argument”, where what you're doing is you do some work and you say, “Well just repeat this work you know because $n$ is a finite number you have to only repeat this finitely many times.”
When you want to write a proof like that to actually write it out formally, you probably are going to need to use induction. So that's what we're going to use here, instead of using a “dot dot dot argument”, we're going to actually just formally prove this by induction. This is a formal proofs class so we should probably try to be as formal as we can.
Let $P(n)$ be the statement that all polynomials over $\mathbb{F}$ of degree $n$ have at most $n$ roots. We prove this by induction on $n$. So what does induction need? You need a base case, inductive hypothesis, and inductive conclusion.
So notice here that I've outlined what $P(n)$ actually is and I find that for a lot of students learning induction for the first time, this is a very useful trick. Actually write down what you're trying to prove. Make sure you understand where the $n$ falls, so here the $n$ falls in two spots, $\deg(n)$ and $n$ roots, and once you have that, really understand what the statement is, you can try to go through the proof
I really encourage students to not just try to blindly go through a proof. Really try to understand what you're trying to prove and then try to prove it. That sounds obvious, but a lot of students will try to go through a question without knowing what the question’s asking. Make sure you understand the statement of the question. If you don't understand the statement, it's very difficult to actually go through a proof.
Well the base case, what does the base case say? All polynomials of degree $1$ have at most $1$ root.
So when $n=1$, let's take our linear polynomial, it’s degree $1$, $ax+b$ inside our polynomial ring over $\mathbb{F}$, with $a\neq 0$ We know that $a \neq 0$ because it has degree $1$.
Then if I solve for this, if I find a root of this, I can see that $x=-a^{-1}b$ is a root. Notice that this makes sense because $a$ is a non-zero element, which is invertible in a field, and I’m multiplying by $-1$ and by $b$, which both are in my field. This is perfectly reasonable as an element. So this must be a root of our polynomial and this must be in our field, we're done.
So we found a root. This could be 0, that's perfectly fine. So the base case, all linear polynomials have a root over a field, that's done.
Assume that $P(k)$ is true for some $k \in \mathbb{N}$.
So don't forget, quantify your variables, $k \in \mathbb{N}$, and it's for some and not for all. So we're assuming that $P(k)$ is true for some, right? If you assume that $P(k)$ is true for all $k \in \mathbb{N}$, then you're done, there's nothing to prove. You've assumed that your statement is true all the time, but what we're doing is we're assuming this is true for some value $k$ and we're going to try to prove that it's true for $k+1$.
It’s that domino effect. I'm going through this inductive proof, again, kind of slowly just to remind ourselves what induction is. We'll need all of these elements of this proof a little bit later.
So assume that $P(k)$ is true, then how do we prove $P(k+1)$? Well what do we need to do? We need to take a degree $k+1$ polynomial and show that it has at most $k+1$ roots.
Now we're going to do something a little bit sneaky but that's pretty clever. So take our degree $k+1$ polynomial. If it has no roots, so if there's no root of the polynomial, then you're done, right? I mean $0$ is less than $k+1$ for sure. So you're done if you have no roots.
We might as well assume that we have a root. So let's call it $c$, alright, so we have some root, say $c,\in \mathbb{F}$. By the Factor Theorem, since we have a root, we know that $x-c$ must be a factor of $p(x)$, so we're going to write $p(x)=(x-c)q(x)$ for some polynomial $q(x)$ of degree $k$.
We also know, again, because the degree of the product is the sum of the degrees. $\deg(x-c)=1$, $\deg(p(x))=k+1$, so therefore $\deg(q(x))=k$.
By the inductive hypothesis what do we know? Well we know that $q(x)$ is a degree $k$ polynomial, so we can apply the induction hypothesis. We've gotten down to a smaller case, that's the whole idea behind induction, right? Take some bigger case, and break it down. Usually you break it down to degree $1$ and degree $k$, or something that depends on $1$ so then it depends on $k$. Sometimes you break it down like in the Fundamental Theorem of Arithmetic, you broke it down into very smaller parts. You know so you had some $n$ and you broke it down to two factors, that's possible as well.
But the key is you break it down to a smaller case that you know something about because of your induction hypothesis. $\deg(q(x))=k$, therefore has at most $k$ roots. $q(x)$ has at most $k$ roots, $(x-c)$ has $1$ root, $k+(1)=k+1$, $p(x)$ has at most $k+1$ roots.
Notice that you could have repetition, $c$ might be a repeated root, that's perfectly reasonable. We've already talked about the case where $p(x)$ has no roots, right, so it is possible for a polynomial to have no roots, but that's fine, that's definitely less than $n$.
And we're done. So therefore, by the Principle of Mathematical Induction, P of n is true for all natural numbers $n. \quad \blacksquare$
So this last little concluding statement wraps it all up nicely. Those are the major ideas here.
Now with this being said we're going to talk about another theorem in a minute, that's basically this proof, almost identically, but it's a different setting. So it's not just over any field in the next setting, but it'll be over the complex numbers. But to get there, we need a hammer and the hammer that we're going to talk about is the Fundamental Theorem of Algebra.
Theorem (FTA): Every non-constant complex polynomial has a complex root.
That's a very, very simple-to-write statement, but it's not so easy to prove. So if you remember where we've been going with this polynomial section, we argued that okay well we have, you know, all these polynomials in different rings over integral polynomials, rational polynomials, real polynomials, but still there are polynomials that don't have roots. For example $x^2+1$. And we said, “Oh well let's go down this complex number route and talk about complex numbers and say okay, well complex numbers help us to solve polynomials like $x^2+1$,” and you could probably try to reason to yourself that okay well maybe all these real polynomials they must have complex roots.
That's true, but maybe one thing that's not entirely clear, and really this isn't clear at all, but why do all complex polynomials also have to have complex roots? Neither of those two statements are very obvious actually, but it turns out that they're true. Every non-constant polynomial has a complex root of some sort, okay? So I can always factor complex polynomials.
That's weird, right, we added this element $i$ to the real numbers and linear combinations of it, and we somehow argue that hey well by doing this, we can actually factor every polynomial we encounter over this new field $\mathbb{C}$. We call $\mathbb{C} algebraically closed sometimes. Not important, but it's good to know a little bit of words. Knowledge is power, right, somebody told me that once upon a time.
We're not going to prove this, the proof is hard. I find that the easiest proof for me to understand is in complex analysis, but that takes a little bit to get to. So once you have the right tools it's not too hard to prove this, but we don't have anywhere near the correct amount of tools to prove this. I have seen a proof of this that's elementary, but it's tough to understand, it really is, without the correct tools.
There's also a proof in Galois Theory which, as a course, I recommend completely. It's a wonderful course. Galois Theory is one of my favorite undergraduate courses and if you get a chance to take it, you absolutely should. You talk about things like this, the Fundamental Theorem of Algebra, you discuss things like why degree $2$, $3$, and $4$ polynomials they all have nice formulas that can be used like the quadratic formula and Cardano’s formula, those all exists for degree $2$, $3$, and $4$ polynomials, but degree $5$ and higher, you can't find some nice polynomial using addition, subtraction, square roots, etc.
It's great, it's mind-blowing, it's a beautiful subject you should take it if you get a chance. If not it's a shame, but let's plug away. I've already talked about this theorem more than I want to. I love this theorem, I think it's pretty cool, but that’s okay let's actually try to use it to prove something.
I guess before I do that, the polynomial $x^2+1$ over $\mathbb{R}$ shows that this doesn't happen over all fields, okay? So $x^2+1$ factors over $\mathbb{C}$, it has complex roots, but $x^2+1$ doesn't have real roots, okay, that's what I want to try to say here. So something very special with the complex numbers. So it's quite magical. The more you think about it, the more you think, “Wow why is this true?”
Let's use the Fundamental Theorem of Algebra to prove this statement:
Theorem (CPN): A complex polynomial $f(z)$ of degree $n \geq 1$ can be written as
$$f(z)=c(z-c_1)(z-c_2)...(z-c_n)$$for some $c\in \mathbb{C}$ where $c_1,c_2,...,c_n \in \mathbb{C}$ are the (not necessarily distinct) roots of $f(z)$
So for example, I mean just kind of visualize it. I didn't actually write down the roots here, but the polynomial $2z^7+z^5+iz+7$, can be written as
$$2(z-z_1)(z-z_2)...(z-z_7)$$What this theorem doesn't tell you, and what’s actually quite difficult, is what are these roots? Factoring is a hard, hard problem. We've already seen this with integers, it's not much different with polynomials, it's still pretty challenging.
So let's talk about this theorem, let's talk about actually trying to prove this. Complex Polynomials of Degree n Have n Roots. How do we prove this? Well it turns out that the proof is going to be very similar to the proof of there being only $n$ roots of a polynomial of degree $n$ over a field $\mathbb{F}$.
So how do we prove this statement? We're going to prove this by mathematical induction again.
When $n=1$, it's similar to before. We have $az+b$, we're going to factor out the $a$, we're going to use a little bit of negation magic, and we're going to write this as $a(z-\displaystyle\frac{-b}{a})$. This is valid because $a \neq 0$, hence is invertible in $\mathbb{C}$. And that's good, so this satisfies the form that we have.
Assume all polynomials over $\mathbb{C}$ of degree $k$ can be written in the given form for some $k \in \mathbb{N}$.
The inductive conclusion well how is this going to work? And the idea is that we do need to use the Fundamental Theorem of Algebra because what does it tell us? Well Fundamental Theorem of Algebra gives us a factor, right? We know that we must have a root by the Fundamental Theorem of Algebra.
The Factor Theorem tells us that we must have a factor. So we know that $(z-c_{k+1})$, let's say, is a factor of our polynomial. So I can write:
$$f(z)=(z-c_{k+1})g(z) \quad \text{where}\,\deg(g(z))=k$$Just like before now I have a degree $k$ polynomial, so by the inductive hypothesis, I can write it out as
$$g(z)=c(z-c_1)...(z-c_k) \quad \text{for}\,c_1,...c_k \in \mathbb{C}$$I combine it together, I get
$$f(z)=c\prod_{i=1}^{k+1}(z-c_i)$$Therefore, by the Principle of Mathematical Induction, the statement is true for all $n \in \mathbb{N}. \quad \blacksquare$
This proof is almost identical to that proof before. The thing that’s changed is that I don’t have a $0$ root case. I always have a root by the Fundamental Theorem of Algebra. That's the difference between this proof and the proof from three slides ago. So something to think about there.
Okay, really cool, really neat. I like that you can reuse that proof from before, I think it's pretty cool. But it does help us out here.
So great, so we know that there is a factorization of complex polynomials. How to find that factorization, you need to use things like the Rational Roots Theorem, and the Factor Theorem, and the Remainder Theorem, all these sorts of theorems, and the Conjugate Roots Theorem. But in particular, we're going to head to those last two: the Rational Root Theorem and the Conjugate Roots Theorem. They'll help us to factor polynomials.
Theorem (RRT): If $f(x)=a_n x^n+...+a_1x+a_0 \in \mathbb{Z}[x]$ and $r=\displaystyle\frac{s}{t} \in \mathbb{Q}$ is a root of $f(x)$ over $\mathbb{Q}$ in lowest terms, then $s \mid a_0$ and $t \mid a_n$
So if we have a polynomial of degree $n$ that's integral, so with integer coefficients, and we have a rational root, $\displaystyle r=\frac{s}{t}$ in lowest terms, then the numerator of that rational root must divide the constant term, that's what this is saying, $s$ divides the constant term, and the denominator of that rational root must divide the leading coefficient.
I won't do an example of this theorem here, that will be in part 2 so if you want to check that out, here I'm just going to do the proof. Again, try this proof. This is a proof that you should be able to do, it's not too bad. The only trick while doing this proof is once you do step 1, actually get an integer object.
When I said step 1, what I really meant was well when you plug in the rational root, clearly that's something that you should do. You have a root you know if you plug it in you get $0$, that sounds like a reasonable first step in this problem
$$0=a_n\left(\frac{s}{t}\right)^n+a_{n-1}\left(\frac{s}{t}\right)^{n-1}...+a_1\left(\frac{s}{t}\right)+a_0$$Now you think well okay I have these rational numbers, the sum of these rational numbers is an integer, it's $0$. How do I deal with that? And the correct way is to actually get rid of the fraction part. How do we do that? Well we multiply by the denominator, which is $t^n$.
$$0=a_n s^n+a_{n-1}s^{n-1}t+...+a_1st^{n-1}+a_0t^n$$So what do I do at this point? Well now I know I look at this and I have $s \mid a$, and I want to show that $s \mid a_0$. All of these terms depend on $s$.
By the way somebody in class said, “Well you should use DIC,” and I said, “Well you can, but DIC is really only for two terms, so you’d have to use some sort of like DIC plus an induction type thing.” I don't really want to do that so I'm just going to write it out as a factor like this.
By the way, I'm using a “dot dot dot” argument here, which is kind of contradicting what I said earlier. If you really want to be like super, super formal with this, you can write this as a summation. The reason why I don't is because I think that this is a little bit easier to understand and cope with, but if you want, write it as a summation, the proof will pan through.
So I'm going to rewrite this by factoring out the s and bringing all of the first $n-1$ terms to the other side.
$$a_0t^n=-s(a_ns^{n-1}+a_{n-1}s^{n-2}t+...+a_1t^{n-1})$$Therefore $s \mid a_0t^n$. We're almost done, we want to show $s \mid a_0$, we got this $t^n$ here that's bothering us, and the trick now to solving this is to recall oh well $\displaystyle\frac{s}{t}$ was a root in lowest terms, and because it’s a root in lowest terms, $\gcd(s,t)=1$.
So therefore $\gcd(s,t^n)=1$ by, let's say, GCDPF that's perfectly reasonable. If $s$ and $t$ don't share a prime factor, then surely $s$ and $t^n$ don’t share a prime factor, so they must be co-prime.
And if $s$ and $t^n$ are co-prime, then we can use Coprimeness and Divisibility and say hey well $s \nmid t^n$, but $s \mid a_0t^n$, so therefore $s \mid a_0$.
I only proved the first part. Why? Well the proof is similar for $t \mid a^n$. Take the last $n-1$ terms, factor out a $t$, bring it to the other side, it's the same argument. So here “similarly” actually is valid as a proof technique. If you need to see it, write it out. If you want some practice, you should write out that proof. That's a very easy proof to write out the other direction, but I won't do it here.
So the Rational Roots Theorem gives us one way to help to factor, and the last theorem that we're going to talk about, I believe unless I'm mistaken, is the Conjugate Roots Theorem, and that will also help us try to factor polynomials. It's a really, really cute theorem, it's actually not hard to prove either so I do encourage you to try it.
Theorem (CJRT): If $c \in \mathbb{C}$ is a root of a polynomial $p(x) \in \mathbb{R}[x]$ (over $\mathbb{C}$) then $\bar{c}$ is a root of $p(x)$.
It's kind of neat, and the proof really isn't that hard. You really should make sure that you can do this proof. It turns out all you have to do to prove this is actually write $p(x)$ a polynomial $a_nx^n+...+a_1x+a_0$, plug in $c$, and then take the conjugates of both sides.
So here we go, that's exactly what I'm doing here. So write $p(x)=a_nx^n+...+a_1x+a_0$ with $p(c)=0$, then let's look at $p(\bar{c})$.
Well if I take $p(\bar{c})$, I'm going to just plug in $\bar{c}$ into $x$ for every possible $x$.
$$\begin{align*} p(\bar{c})&=a_n (\bar{c})^n +...+a_1 \bar{c}+a_0\\\ &=\overline{a_n (c)^n} +...+\overline{a_1 c}+\overline{a_0} &&\text{Since coefficients are real and PCJ}\\\\ &=\overline{a_n (c)^n +...+a_1 c+a_0} &&\text{By PCJ}\\\\ &=\overline{p(c)}\\\\ &=0 \quad \blacksquare \end{align*}$$So $\bar{c}$ is also a root of a real polynomial when $c$ is a root. This is not true if your polynomial is not real, right? If your polynomial has complex coefficients, this proof breaks down. I can't just take the bar of each coefficient, that doesn't work. But when it is real, you can do that.
So it's pretty cool. I think it's a really neat theorem, and you can use this, for example, if you can find a complex root, a strictly complex root, then you actually know $2$ roots, and when you know $2$ roots, then you can multiply, you know, their factors together and divide out and get some new polynomial that’s degree $2$ less. By doing that, you can reduce your computation and you reduce your search space and so on and so forth. So these give you ways to factor these polynomials.
I think that's all I want to talk about in this video. I'm just trying to scroll and I don't think I have anything else to talk about. So again this was the theoretical video. If you want to see applications of this, check out part 2 of Week 11. Hopefully this gave you an idea of what we did this week. Hopefully this helps you to try to factor polynomials, gives you some ideas, and hopefully it helps clear up some of the proofs that you might have been struggling with this week. Okay that's all I have to say, thank you very much and all the best.