305 -7. Extension fields revisited

April 3, 2009

1. Greatest common divisors.

Let’s conclude the discussion from last lecture.

If ${{mathbb F}}$ is a field and ${p(x),q(x)in{mathbb F}[x]}$ are nonzero, then we can find polynomials ${alpha(x),beta(x)in{mathbb F}[x]}$ such that ${alpha p+beta q}$ is a gcd of ${p}$ and ${q.}$

To see this, consider ${{mathcal A}={{rm deg}(a(x)):0ne a(x)in{mathbb F}[x]}$ and for some polynomials ${alpha,betain{mathbb F}[x],}$ we have ${a=alpha p+beta q}.}$

We see that ${{mathcal A}neemptyset,}$ because both ${p}$ and ${q}$ are nonzero linear combinations of ${p}$ and ${q,}$ so their degrees are in ${{mathcal A}.}$ Each element of ${{mathcal A}}$ is a natural number because ${{rm deg}(a)=-infty}$ only for ${a=0.}$ By the well-ordering principle, there is a least element of ${{mathcal A}.}$

Let ${n}$ be this least degree, and let ${g=alpha p+beta q}$ have degree ${n.}$

First, if ${sin{mathcal F}[x]}$ and ${s|p,q}$ then ${s|alpha p+beta q,}$ so ${s|g.}$

Second, by the division algorithm, we can write ${p=gm+r}$ for some polynomials ${m,rin{mathbb F}[x]}$ with ${{rm deg}(r)<{rm deg}(g).}$ Then ${r=p-gm=(1-alpha m)p+(-beta m)q}$ is a linear combination of ${p,q.}$ Since ${{rm deg}(r)<{rm deg}(g),}$ and ${n={rm deg}(g)}$ is the smallest number in ${{mathcal A},}$ it follows that ${{rm deg r}=-infty,}$ i.e., ${r=0.}$ This is to say that ${p=gm,}$ so ${g|p.}$ Similarly, ${g|q.}$

It follows that ${g}$ is a greatest common divisor of ${p,q.}$

Since any other greatest common divisor of ${p,q}$ is ${ig}$ for some unit ${i,}$ it follows that any gcd of ${p}$ and ${q}$ is a linear combination of ${p}$ and ${q.}$

Notice that this argument is very similar to the proof of the same result for ${{mathbb Z}.}$

305 -Rings, ideals, homomorphisms (3)

March 21, 2009

In order to understand the construction of the quotient ring from last lecture, it is convenient to examine some examples in details. We are interested in ideals ${I}$ of ${{mathbb F}[x],}$ where ${{mathbb F}}$ is a field. We write ${{mathbb F}[x]/I}$ for the quotient ring, i.e., the set of equivalence classes ${[a]_sim}$ of polynomials ${a}$ in ${F[x]}$ under the equivalence relation ${asim b}$ iff ${a-bin I.}$

• If ${I={0},}$ then for any ${a,}$ the equivalence class ${[a]_sim}$ is just the singleton ${{a}}$ and the homomorphism map ${h:{mathbb F}[x]rightarrow{mathbb F}[x]/I}$ given by ${h(a)=[a]_sim}$ is an isomorphism.

To understand general ideals better the following notions are useful; I restrict to commutative rings with identity although they make sense in other contexts as well:

Definition 1 Let ${R}$ be a commutative ring with identity. An ideal ${I}$ is principal iff it is the ideal generated by an element ${a}$ of ${R,}$ i.e., it is the set ${(a)}$ of all products ${ab}$ for ${bin R.}$

For example, ${{0}=(0)}$ is principal. In ${{mathbb Z}}$ every subring is an ideal and is principal, since all subrings of ${{mathbb Z}}$ are of the form ${n{mathbb Z}=(n)}$ for some integer ${n.}$

305 -Homework set 1

January 26, 2009

This set is due February 6 at the beginning of lecture. Consult the syllabus for details on the homework policy.

1. a. Complete the proof by induction that if $a,b$ are integers and $(a,b)=1$, then $(a^n,b)=1$ for all integers $nge1$.

b. This result allows us to give a nice proof of the following fact: Let $n$ be a natural number and let $m$ be a positive integer. If the $m$-th root of $n$, $root mof n$, is rational, then it is in fact an integer. (The book gives a proof of a weaker fact.)  Prove this result as follows: First verify that if $a/b=c/d$ and $b+dne0$, then $displaystyle frac ab=frac{a+c}{b+d}$. Show that any fraction $a/b$ with $a,b$ integers, can be reduced so $(a,b)=1$. Assume that $root mof n$ is rational, say $a/b$. Then also $root mof n=n/(root mof n)^{m-1}$. Express this last fraction as a rational number in terms of $n,b,a$. Use that $(a^k,b)=1$ for all $kge1$ and the general remarks mentioned above, to show that $root mof n$ is in fact an integer.

2. Show by induction that for all integers $kge 1$ there is a polynomial $q(x)$ with rational coefficients, of degree $k+1$ and leading coefficient $1/(k+1)$, such that for all integers $nge1$, we have $displaystyle sum_{i=1}^n i^k =q(n)$. There are many ways to prove this result. Here is one possible suggestion: Consider $displaystyle sum_{i=1}^n [(i+1)^{k+1}-i^{k+1}]$.

3. Euclidean algorithm. We can compute the gcd of two integers $m,n$, not both zero, as follows; this method comes from Euclid and is probably the earliest recorded algorithm. Fist, we may assume that $m, n$ are positive, since $(m,n)=(|m|,|n|)$, and also we may assume that $mge n$, so $m>0$. Now define a sequence $r_0,r_1,r_2,dots$ of natural numbers as follows:

• $r_0=m$, $r_1=n$.
• Given $r_i,r_{i+1}$, if $r_{i+1}=0$, then ${tt STOP}$.
• Otherwise, $r_{i+1}>0$, and we can use the division algorithm to find unique integers $q,r$ with $0le r such that $r_i=r_{i+1}q+r$. Set $r_{i+2}=r$.
• Let $A$ be the set of those $r_k$ that are strictly positive. This set has a least element, say $r_k$. By the way the algorithm is designed, this means that $r_{k+1}=0$.
•  Show that $r_k=(m,n)$, and that we can find from the algorithm, integers $x,y$ such that $r_k=mx+ny$.

(If the description above confuses you, it may be useful to see the example in the book.)

4. Assume that the application of the algorithm, starting with positive integers $m>n$, takes $k$ steps. [For example, if $m=35$ and $n=25$, the algorithm gives:

Step 1: $35=25.1+10$, so $r_0=35,r_1=25,r_2=10$.

Step 2: $25=10.2+5$, so $r_3=5$.

Step 3: $10=5.2$, so $r_4=0$, and $(35,25)=5$. Here, $k=3$]

Show that $nge F_{k+1}$, where the numbers $F_1,F_2,dots$ are the Fibonacci numbers, see Exercises 15-22 in Chapter 1 of the book.

5. Extra credit problem. With $m,n,k$ as in the previous exercise, let $t$ be the number of digits of $n$ (written in base 10). Show that $kle 5t.$