\ie\cf
\newcommand{\eqdef}{\mathbin{\stackrel{\rm def}{=}}}  \newcommand{\R} % real numbers  \newcommand{\N}} % natural numbers  \newcommand{\Z} % integers  \newcommand{\F} % a field  \newcommand{\Q} % the rationals  \newcommand{\C}{\mathbb{C}} % the complexes  \newcommand{\poly}}  \newcommand{\polylog}}  \newcommand{\loglog}}}  \newcommand{\zo}{\{0,1\}}  \newcommand{\suchthat}  \newcommand{\pr}[1]{\Pr\left[#1\right]}  \newcommand{\deffont}{\em}  \newcommand{\getsr}{\mathbin{\stackrel{\mbox{\tiny R}}{\gets}}}  \newcommand{\Exp}{\mathop{\mathrm E}\displaylimits} % expectation  \newcommand{\Var}{\mathop{\mathrm Var}\displaylimits} % variance  \newcommand{\xor}{\oplus}  \newcommand{\GF}{\mathrm{GF}}  \newcommand{\eps}{\varepsilon}  \notag
\no
Back to MB3

Week 11 Notes

100%

Linear Equations

A linear equation is an equation where all of the variables are to the first power.

Single Variable Linear Equations

The simplest type of linear equation is one with a single variable. Here's an example: $$2x+5=4x+2$$How do you solve these?

Applying this procedure to the example above gives us $$2x-4x+5=2$$$$-2x=2-5$$$$-2x=-3$$$$x=1.5$$

This method of solving a linear equation is called isolation, as we are isolating the \(x\) variable on the left and putting everything else on the right. This method will be useful in the next section as well.

Multivariate Linear Equations

Now, suppose we have a linear equation with multiple variables$$4x+5y=10$$How do we solve this? Well, we can't, as there are multiple solutions. Whenever we have \(n\) equations and \(m\) variables, with \(m>n\), we can't solve the system of equations.

However, we can apply our isolation trick. Let's isolate \(x\) as per our method above. $$4x=10-5y$$$$x=2.5-1.25y$$

This allows us to calculate the corresponding \(x\) value for any \(y\) value.

Now suppose we have two equations: $$4x+5y=10$$$$6x+5y=60$$How do we solve here?

Solving systems with substitution

Let's isolate \(x\) in the first equation to get $$x=2.5-1.25y$$Now, we have a formula for \(x\) in terms of \(y\). We can replace \(x\) in the second equation with \(2.5-1.25y\).

$$6(2.5-1.25y)+5y=60$$$$15-7.5y+5y=60$$$$-2.5y=45$$$$y=-18$$Now we know the value for \(y\), so we can substitute it in to compute \(x\)$$4x+5(-18)=10$$$$4x=100$$$$x=25$$

This method of solving linear equations is called substitution. To review, here's how it works:

Let's do an example to show how it works

Consider the following system: $$2x+y+z=5$$$$x+3y+4z=12$$$$5x+10y+z=15$$All of them have the same number of variables, so we pick the first equation, and isolate \(y\) to get \(y=5-2x-z\). Now, we substitute the right side into the other two equations to get $$x+3(5-2x-z)+4z=12$$$$5x+10(5-2x-z)+z=15$$Simplifying, we get $$-5x+z=-3$$$$-15x-9z=-35$$Now, we isolate \(z\) in the first equation to get \(z=5x-3\), and substitute it into our remaining equation. $$-15x-9(5x-3)=-35$$$$-60x=-62$$Thus, \(x=\frac{31}{30}\). Now, we go back one step to the equation \(z=5x-3\) to get \(z=\frac{13}6\). Finally, we go back to the first isolation \(y=5-2x-z\) to get \(y=\frac52\).

The great part about substitution is that if the system has an answer, substitution will give it to you. The bad part is that it can take a very long time, especially for larger systems. Thus, we use a different technique to simplify systems a bit quicker.

Solving systems with Elimination

Let's revist the system we just solved: $$2x+y+z=5$$$$x+3y+4z=12$$$$5x+10y+z=15$$Our goal is to get rid of a variable to simplify the solving. Here's how we can do that.

Suppose in equation \(a\), the coefficient of variable \(x\) is \(c\), and in equation \(b\), the coefficient is \(d\). Then, multiply \(a\) by \(d\) and \(b\) by \(-c\) and add the two equations together. The \(x\) terms will cancel out.

Let's apply this to the first two equations. Multiplying the second equation by \(-2\) gives us \(-2x-6y-8z=-24\). Adding it to the first equation gives us \(-5y-7z=-19\).

Solve the system above by applying elimination to equations two and three to get rid of \(x\), and then use substitution to finish the system.

Elimination is in general a faster method for simplifying systems of equations, although choosing the equations that minimize the multiplication will help you solve equations much faster.

Occasionally, you may see some patterns that make solving even faster.

Consider the following system: $$2x+y+z=15$$$$x+2y+z=16$$$$x+y+2z=17$$If I add all \(3\) equations together, I get \(4(x+y+z)=48\), and thus \(x+y+z=12\). Subtracting this from each of the equations gives us \(x=3\), \(y=4\), \(z=5\).

Polynomials

Linear equations are nice and simple because they only involve variables to the first power. Polynomials, on the other hand, can have variables to any power. In these notes, we'll only deal with polynomials in a single variable. In other words, our polynomials will look like this:$$p(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_0$$

Polynomial Division

Like numbers, we can divide polynomials. Here's an example.

Suppose I wanted to divide \(x^3-2x^2-4\) by \(x-3\). We can essentially follow the same process as long division. First, multiply \(x-3\) by \(x^2\) to match the \(x^3\) term. \begin{array}{l} \phantom{x-3 ) }x^3\\ x-3\ \overline{)\ x^3 - 2x^2 + 0x - 4}\\ \phantom{x-3}\underline{- x^3 + 3x^2} \end{array} Now, we subtract the result of the multiplication to get \begin{array}{l} \phantom{x-3 ) } x^2 + x\\ x-3\ \overline{)\ x^3 - 2x^2 + 0x - 4}\\ \phantom{x-3 ) } \underline{-x^3 + 3x^2}\\ \phantom{x-3 ) + 0x^3} x^2 + 0x -4 \end{array}As indicated on top, we now multiply \(x-3\) by \(x\) to match the \(x^2\) term. \begin{array}{l} \phantom{x-3 ) } x^2 + x\\ x-3\ \overline{)\ x^3 - 2x^2 + 0x - 4}\\ \phantom{x-3 ) } \underline{-x^3 + 3x^2}\\ \phantom{x-3 ) + 0x^3} x^2 + 0x -4\\ \phantom{x-3 ) + 0} \underline{-x^2 + 3x\phantom{-44}}\\ \end{array}Now, we multiply \(x-3\) by \(3\) to cancel the \(3x\) term. \begin{array}{l} \phantom{x-3 ) } x^2 + x + 3\\ x-3\ \overline{)\ x^3 - 2x^2 + 0x - 4}\\ \phantom{x-3 ) } \underline{-x^3 + 3x^2}\\ \phantom{x-3 ) + 0x^3} x^2 + 0x -4\\ \phantom{x-3 ) + 0} \underline{-x^2 + 3x\phantom{-44}}\\ \phantom{x-3 ) + 0x^3 + x}3x-4\\ \phantom{x-3 ) + 0x^3 +}\underline{-3x+12}\\ \phantom{x-3 ) + 0x^3 + x + x^2}8 \end{array} So, the result of our division is \(x^3-2x^2-4\) divided by \(x-3\) is \(x^2+x+3\) with a remainder of \(8\).

The example above should be quite familiar to you, as it is essentially the same process as long division for integers.

When we deal with polynomials, we define their degree as follows. The \(0\) polynomial has degree \(-1\), any non-zero constant has degree \(0\), and any other polynomial has degree equal to the power of its highest term. In other words, linear polynomials have degree \(1\), quadratics have degree \(2\), etc.

Notice that the degree of the remainder in the example above (\(8\)) is less than the divisor (\(x-3\)). This isn't a coincidence. The same way that the remainder of the division \(n/k\) is less than \(k\) (assuming \(k>0\)), the degree of the remainder when dividing by polynomials is less than the degree of the divisor.

More importantly, given polynomials \(p\) and \(d\), with \(q\) the quotient when \(p\) is divided by \(d\), and \(r\) the remainder polynomial, we have the following equation:$$p=q\cdot d+r$$In the example above, we have $$x^3-2x^2-4=(x^2+x+3)(x-3)+8$$This is called quotient form.

Polynomial Roots

Given a polynomial \(p(x)\), a root \(y\) of \(p\) is a number such that \(p(y)=0\). How many roots does \(p\) have? How can we find them?

Given a polynomial \(p(x)\), if \(y\) is a root of \(p\), then \(x-y\) is a factor of \(p\)


Let \(q(x)\) be the quotient and \(r(x)\) the remainder when \(p\) is divided by \(x-y\). If \(r=0\), then \(x-y\) is a factor of \(p\) as desired. If \(r\neq0\), then since the degree of \(r\) is less than the degree of \(x-y\), which is \(1\), \(r\) is a non-zero real number. So, $$p(y)=q(y)(x-y)+r$$$$0=q(y)(y-y)+r$$$$r=0$$Thus, \(x-y\) is a divisor of \(p\).
Given a non-zero polynomial \(p\) with degree \(n\geq0\), \(p\) has at most \(n\) roots.


Clearly, for any \(y\neq0\), if \(p(x)=y\), then \(p\) has no roots. So, degree \(0\) polynomials have \(0\) roots.

And for any degree \(n\) polynomial \(p\), if \(y\) is a root of \(p\), then \(p(x)=q(x)\cdot(x-y)\). \(q(x)\) has degree at most \(n-1\), so it has at most \(n-1\) roots. So, \(p\) has all of \(q\)'s roots and \(y\), so it has at most \(n\) roots.

The above two results tell us that if \(p\) is a degree \(n\geq0\) polynomial with roots \(x_1,\ldots,x_n\), then there exists a real number \(a\neq0\) such that $$p(x)=a\cdot\prod\limits_{i=1}^n(x-x_i)$$We call this the factorization of \(p\).

Quadratic Polynomials

Quadratic Polynomials are polynomials of degree \(2\). In other words, they are of the form \(ax^2+bx+c\). We can find the roots as follows.

We want to find the roots of \(ax^2+bx+c\) where \(a\neq0\). Thus, we have the equation $$ax^2+bx+c=0$$Dividing both sides by \(a\) and subtracting \(\frac ca+\left(\frac b{2a}\right)^2\) from both sides gives us $$x^2+\frac bax+\left(\frac b{2a}\right)^2=\left(\frac b{2a}\right)^2-\frac ca$$Notice that \(\left(x+\frac b{2a}\right)^2=x^2+\frac ba+\left(\frac b{2a}\right)^2\), so $$\left(x+\frac b{2a}\right)^2=\left(\frac b{2a}\right)^2-\frac ca$$Square rooting both sides gives us $$x+\frac b{2a}=\pm\sqrt{\left(\frac b{2a}\right)^2-\frac ca}$$Multiplying both sides by \(2a\) and subtracting \(b\) from both sides gives us $$x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}$$This formula is known as the quadratic formula.
Check that our theorems above are correct by showing that $$ax^2+bx+c=a\left(x+\frac{b+\sqrt{b^2-4ac}}{2a}\right)\left(x+\frac{b-\sqrt{b^2-4ac}}{2a}\right)$$

We call the value \(b^2-4ac\) the discriminant of the quadratic polynomial. If it is positive, the polynomial has \(2\) real roots. If it is zero, it has \(1\) real root. Otherwise, it has \(0\) real roots. A classic application of the discriminant is the following theorem.

For any sequences \(a_1,\ldots,a_n\) and \(b_1,\ldots,b_n\),$$\left(\sum\limits_{i=1}^na_i^2\right)\left(\sum\limits_{i=1}^nb_i^2\right)\geq\left(\sum\limits_{i=1}^na_ib_i\right)^2$$Equality holds only if there exists some \(t\) such that for all \(i\), \(b_i=a_i\cdot t\)


Consider the polynomial $$p(x)=\sum\limits_{i=1}^n(a_ix-b_i)^2$$Clearly, this polynomial is a non-negative quadratic, so it has at most one root. In other words, its discriminant is non-positive. Expanding the polynomial gives us $$p(x)=x^2\cdot\sum\limits_{i=1}^na_i^2-2x\sum\limits_{i=1}^na_ib_i+\sum\limits_{i=1}^nb_i^2$$So, the discriminant is $$4\left(\sum\limits_{i=1}^na_ib_i\right)^2-4\left(\sum\limits_{i=1}^na_i^2\right)\left(\sum\limits_{i=1}^nb_i^2\right)\leq0$$Dividing by \(4\) gives us the desired inequality. If this inequality is an equality, that implies that the discriminant is \(0\), and thus \(p\) has a single root \(t\). Thus, for each \(i\), \(a_it-b_i=0\), since \(p(t)\geq(a_it-b_i)^2\). This completes the proof.
Given real numbers \(x,y,z\) such that \(x^2+y^2+z^2=1\), what is the maximum value of \(x+2y+3z\)?


By Cauchy Schwarz, $$(x+2y+3z)^2\leq(1^2+2^2+3^2)(x^2+y^2+z^3)=14$$Equality holds when \(\frac x1=\frac y2=\frac z3\). So, letting $$x=\frac1{\sqrt14},\;y=\frac2{\sqrt14},\;z=\frac3{\sqrt14}$$we get \(x+2y+3z=\sqrt{14}\), which is the maximum value.

The quadratic formula gives us a way of finding the factorization of any quadratic. Similarly, there are formulas for finding the factorization of cubics (degree 3) and quartics (degree 4) called Cardano's Formulas, but these formulas are tedious, and not worth remembering.

You may be wondering whether there is a formula for quintic (degree 5) polynomials and above. The answer is no, if we are only allowed to use simple formulas, and the proof of this fact is one you'll learn in an Algebra class in a few years.

Vieta's Formulas

As noted in the previous section, finding roots of quadratic polynomials is already hard, but the higher the degree is, the harder it gets. So are there ways of interacting with roots without directly calculating them? The answer is yes!

Elementary Symmetric Polynomials

Given a polynomial \(p\) with degree \(n\) and \(n\) roots \(x_1,\ldots,x_n\), the elementary symmetric polynomials are the following polynomials:$$S_1=x_1+x_2+\ldots+x_n$$$$S_2=x_1x_2+x_1x_3+\ldots+x_2x_3+\ldots+x_{n-1}x_n$$$$\vdots$$$$S_n=x_1x_2\ldots x_n$$In other words, the \(i\)th elementary symmetric polynomial is the polynomial that sums all the possible products of \(i\) of the \(n\) roots.

Any symmetric polynomial \(q(x_1,\ldots,x_n)\) (symmetric meaning that the order of inputs doesn't matter) can be written in terms of elementary symmetric polynomials. Here are some examples for \(n=2\):$$x_1^2+x_2^2=(x_1+x_2)^2-2x_1x_2=S_1^2-2S_2$$$$x_1^3+x_2^3=S_1^3-3S_1S_2$$

Why are these polynomials useful?

Given \(p(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_0\) with roots \(x_1,\ldots,x_n\), $$(-1)^n\frac{a_0}{a_n}=S_1$$$$(-1)^{n-1}\frac{a_1}{a_n}=S_2$$And in general, $$(-1)^{n-k}\frac{a_k}{a_n}=S_{k+1}$$

In other words, just by looking at a polynomial, you know the values of all of the elementary symmetric polynomials on the roots!

Given a quadratic \(ax^2+bx+c\), the roots \(r_1,r_2\) satisfy \(r_1+r_2=-\frac ba\) and \(r_1r_2=\frac ca\) by Vieta's formulas
Given the quadratic \(ax^2+bx+c\) has roots \(r_1,r_2\), compute \(r_1^3+r_2^3\) in terms of \(a,b,c\).

Vieta's formulas imply another very useful theorem.

Given any polynomial \(a_nx^n+\ldots+a_0\) where \(a_0,\ldots,a_n\) are all integers, if \(\frac pq\) (in reduced form) is a root of this polynomial, then \(p\) is a divisor of \(a_0\) and \(q\) a divisor of \(a_n\).
Show using RRT that \(x^2+x+1\) has no rational roots.

Diophantine Equations

Often, we are interested in polynomial equations, but want to only find integer solutions to them. We call these equations Diophantine Equations. In general, these equations are extremely challenging to solve. However, there are some special types of Diophantine equations which are more easily solvable.

A good example of such a Diophantine equation is known as Simon's Favorite Factoring Trick, which is the following simple observation:$$(x+i)(y+j)=xy+jx+iy+ij$$In particular, \(xy+x+y+1=(x+1)(y+1)\) and \(xy-x-y+1=(x-1)(y-1)\). We can use this observation to factor equations of the form \(Axy+Bx+Cy=D\).

Find all positive integers \(m,n\) with \(n\) odd such that $$\frac1m+\frac4n=\frac1{12}$$


Multiplying by \(12mn\) gives us \(mn-48m-12n=0\). Since \(48\cdot12=576\), we have $$\begin{aligned}mn-48m-12n+576&=576\\(m-12)(n-48)&=576\end{aligned}$$Since \(n\) is odd, so is \(n-48\). The positive odd factors of \(576\) are \(1,3,9\), leading to the solutions $$(m,n)=(588,49),\;(204,51),\;(76,57)$$

Another useful Diophantine equation is Pell's Equation, which is of the form \(x^2-dy^2=1\) for some positive integer \(d\) which is not a perfect square. Then, the following theorem holds.

There exist positive integers \(x_0,y_0\) such that \(x_0^2-dy_0^2=1\). And if these are the smallest positive integers which are solutions to Pell's Equation, then every positive solution to Pell's Equation is of the form \(x_n,y_n\), with $$\left(x_0+y_0\sqrt d\right)^n=x_n+y_n\sqrt d$$
It's easy to see that \((x_0,y_0)=(3,2)\) is the smallest positive solution to \(x^2-2y^2=1\). Thus,$$x_n+y_n\sqrt d=\left(3+2\sqrt2\right)^n$$Verify for yourself that$$x_n-y_n\sqrt d=\left(3-2\sqrt2\right)^n$$So, $$(x_n,y_n)=\left(\frac{\left(3+2\sqrt2\right)^n+\left(3-2\sqrt2\right)^n}2,\frac{\left(3+2\sqrt2\right)^n-\left(3-2\sqrt2\right)^n}2\right)$$These are all of the positive integer solutions to Pell's Equation

Challenge: Polynomial Rings

In the previous section, we noted the similarity between long division in the integers and in the set of polynomials. And, we also defined what it means to compute the remainder when one polynomial is divided by the other. Using these ideas, we can define mods for polynomials.

But before that, a bit of notation. \(\mathbb N\) is the set of natural numbers, \(\mathbb Z\) is the set of integers, \(\mathbb Q\) the set of rational numbers, and \(\mathbb R\) the set of real numbers.

Given a set \(S\), the notation \(S[x]\) refers to the set of polynomials where the coefficients belong to \(S\) and the variable is \(x\).

Defining mods

In Week 8, we consider the integers \(\mathbb Z\) mod some natural number \(n\). When we want to write the integers modulo \(n\), we write \(\mathbb Z/(n)\). Essentially, we are dividing the integers into \(n\) pieces, hence the notation.

We'll use similar notation for polynomials. Given some modulus \(r(x)\), we say that \(p(x)\equiv q(x)\bmod r(x)\) if \(p(x)-q(x)\) is a multiple of \(r(x)\), or equivalently, if \(p(x)\) and \(q(x)\) have the same remainder when divided by \(r(x)\).

We'll write this set as \(\mathbb R[x]/(r(x))\), which means the set of polynomials with real coefficients, modulo \(r(x)\).

Can you come up with a definition for prime polynomials? What behavior do these polynomials have that makes them "prime"?

In Week 8, we introduced Bezout's Lemma, which told us that given \(a,b\) with \(\gcd(a,b)=1\), there exists a number \(c\) such that \(ac\equiv1\bmod b\). In other words, \(c\equiv\frac1a\) in \(\mathbb Z/(b)\). Can you come up with a variant of Bezout's Lemma for polynomials? What does it tell you?

Building interesting mod sets

Let's think about the natural numbers for a moment. The polynomial \(x+1\) is an element of the set \(\mathbb N[x]\), but it has no roots in the natural numbers. In fact, it's only root is in the integers, notably \(-1\). Because of this, we expand the space of natural numbers to include the integers.

Similarly, the polynomial \(qx+p\) is an element of the set \(\mathbb Z[x]\), but unless \(q\) is a divisor of \(p\), it has no roots in the integers. For example \(2x-1\) has no roots in the integers. So, we are motivated to expand the space of integers to the rational numbers.

In both of these examples, we found polynomials that didn't have roots, and then added new numbers to ensure that the polynomials have roots. But why are we allowed to do this?

It's all thanks to mods! Let me show you why.

Let's take our example from earlier. \(2x-1\) is a integer polynomial, but it has no roots in the integers. How do we create a root? Simple. Consider the space \(\mathbb Z[x]/(2x-1)\). In this space, we have all of our integers, but \(x\) is defined so that \(2x-1\equiv0\). In other words, \(x\equiv\frac12\)!

So, \(\mathbb Z[x]/(2x-1)\) is the space we get when we take the integers, and add \(\frac12\) (and all of its integer multiples). We can do the same thing with \(3x-1,\;5x-1\), etc, to add all of the fractions to \(\mathbb Z\). Doing this for all the possible denominators creates the rational numbers.

That's cool! But we can actually go even further. In \(\mathbb R[i]\), there are several polynomials without real roots. For example, \(i^2+1\).

So let's apply our technique again! Let's consider the space \(\mathbb R[i]/(i^2+1)\). This space has all of the real numbers, but it also has a number \(i\), with the property that \(i^2+1\equiv0\), or in other words, \(i^2\equiv-1\).

Ring a bell yet? These are the complex numbers! In fact, this is how they are defined. The complex numbers are just a mod set.

Now you may be wondering, can we go even further? Can we find more polynomials with no roots in the complex numbers, and add them in to make an even bigger space? The answer is no.

The complex numbers are special because they have a property called algebraic closure. In other words, every polynomial has a root. So, our fun little game ends with the complex numbers.

Top