All Problems 442

Please Login to access more options.

Today

RSA public key encryption

This is found on page 164 of your text

1. Receiver
   1. Pick very large primes $p$ and $q$ and compute $n=pq$.
   2. Compute the least common multiple of $p-1$ and $q-1$; call it $m$.
   3. Pick $r$ relatively prime to $m$.
   4. Find $s$ such that $rs \text{ mod } m =1$.
   5. Publicly announce $n$ and $r$.
2. Sender
   1. Convert the message to strings of digits.
   2. Break up the message into uniform blocks of digits; call them $M_1$, $M_2$, $\ldots$, $M_k$.
   3. Calculate and send $R_i=M_i^r \text{ mod }n$.
3. Receiver
   1. For each received message $R_i$, calculate $R_i^s\text{ mod }n$.
   2. Convert the string of digits back to a string of characters.

Much of the development of modern abstract algebra began by studying how to solve algebraic equations, in particular polynomial equations of the form $a_0+a_1x+a_2x^2+a_3x^3+\cdots a_nx^n=0$. If the coefficients are integers, then what can we say about the solutions? What can we say about the solutions if the coefficients are instead rational numbers, real numbers, or complex numbers?

• The quadratic formula gives all solutions to $a_0+a_1x+a_2x^2=0$.
• In the 1500's, Girolamo Cardano (1501-1576) published a solution to the general cubic equation.
• Shortly afterwards, his student Lodovico Ferrari (1522-1565) published a solution to the general quartic equation.

At this point in mathematical history, the next obvious goal was to find the solution to the general quintic equation. This problem remained open into the 1800s, where finally Abel showed that obtaining a formula using radicals was in general impossible. Galois invented group theory to describe the symmetries of solutions to polynomial equations. Most of our modern view of algebra has its roots in the history of solving the general quintic.

A lot of new words have been created since the 1500s to describe different types of number systems. To start this semester, I'd like us to explore the properties of the rationals, and then from them develop the concepts of field, ring, integral domains, and more.

The rational numbers have two group structures. Under addition, the set of rational numbers $(\mathbb{Q},+)$ forms an Abelian group. Under multiplication, we almost have another Abelian group with one problem. The number 0 does not have a multiplicative inverse. We'll let $\mathbb{Q}^*$ denote the set of rational numbers, excluding zero, and then we see that $(\mathbb{Q}^*,\cdot)$ is another Abelian group. When we look at how addition and multiplication interact together, the properties of addition and multiplication satisfy the distributive laws $a(b+c)=ab+ac$ and $(b+c)a=ba+ca$.

Definition (Field)

A field is a set $F$ together with two binary operations $+$ and $\cdot$ that satisfies the following properties:

1. $(F,+)$ is an Abelian group. Let $F^*$ be the set $F$ with the additive identity removed.
2. $(F^*,\cdot)$ is an Abelian group.
3. The distributive laws hold, namely we have $a(b+c)=ab+ac$ and $(b+c)a=ba+ca$.

Problem 1 (Listing The Properties Of A Field)

Suppose that $F$ is a field. Since $(F,+)$ and $(F^*,\cdot)$ are Abelian group, this means there are several properties that the binary operations $+$ and $*$ must satisfy. Make a list of all these properties, which together with the distributive laws, should give you a list of 9 properties that characterize a field. Then state at least two other sets that you know satisfy these properties.

Problem 2 (Algebraic Properties Of Modular Arithmetic)

Consider the sets $\mathbb{Z}_n$ for each positive integer $n$, together with modular addition and multiplication.

1. Give three different integers $n$ so that $\mathbb{Z}_n$ is a field.
2. Give an integer $n$ where $\mathbb{Z}_n$ is not a field. List the properties of being a field that are not satisfied.
3. Find an integer $n$ and elements $a,b\in \mathbb{Z}_n$ with $a\neq b$ such that $ab=0$ but neither $a$ nor $b$ is zero.
4. For each integer $k\geq 2$, find an integer $n$ and element $a\in \mathbb{Z}_n$ so that $a^k=0$ but $a^{k-1}\neq 0$.
5. State all $n$ for which $\mathbb{Z}_n$ is a field.

Definition (Polynomial Rings Over A Field)

Let $F$ be a field. We denote by $F[x]$ the set of all polynomial in the variable $x$ with coefficients in $F$ together with polynomial addition and multiplication (if needed, see page 294 in your text for a formal description of something you are very familiar with). The set $F[x]$ is called the polynomial ring over $F$ (in the indeterminate $x$). We can write each element $p(x)\in F[x]$ in the form $$p(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_2x^2+a_1x+a_0$$ for some $n$ where $a_i\in F$ for each $i$ and $a_n\neq 0$ if $n\geq 1$.

Problem 3 (Algebraic Properties Of Polynomial Rings Over A Field)

Let $F$ be a field (think the rationals $\mathbb{Q}$). Which of the properties of being a field does $F[x]$ not satisfy? Give an example of each property (of the 9 total) that is not satisfied.

The previous problem shows that polynomial rings over a field are not a field. Algebra's beginnings lie in finding solutions to polynomial equation of the form $p(x)=0$. The number $\sqrt{2}$ is a solution to the equation $x^2-2=0$, and so is the root of some polynomial. We say that $\sqrt{2}$ is an algebraic number. The number $\pi$ is not the root of any polynomial (a very nontrivial thing to prove), and such numbers we call transcendental. They transcend algebra. One of our goals this semester will be to understand the set of algebraic numbers.

Definition (Algebraic Number)

We say that a number $x$ is algebraic if it is a root of a polynomial with rational coefficients. In symbols, we say that $x$ is algebraic if $x$ satisfies $p(x)=0$ for some $p(x)\in \mathbb{Q}[x]$.

Problem 4 (Algebraic Numbers)

Let $\mathbb{Z}[x]$ be the set of all polynomials with coefficients in $\mathbb{Z}$, together with the usual properties of polynomial addition and multiplication. Show that $x$ is an algebraic number if and only if $x$ satisfies $q(x)=0$ for some $q(x)\in \mathbb{Z}[x]$.

Let's now compare the field properties to operations with matrices and vectors. In the problems below, you'll be asked to list the properties of a field that are not satisfied. There are 9 properties to consider in each case, as there are 4 from each Abelian group and one more from the distributive laws. You should be prepared to prove each property that is satisfied (or at least state why you know it is satisfied).

Problem 5 (Algebraic Properties Of Square Matrices)

Let $\text{M}_2(\mathbb{Q})$ bet the set of 2 by 2 matrices with entries in $\mathbb{Q}$, together with the usual properties of matrix addition and matrix multiplication. Recall that $\text{GL}(2,\mathbb{Q})$ is the set of invertible 2 by 2 matrices with entries in $\mathbb{Q}$.

1. Which of the properties of being a field does $\text{M}_2(\mathbb{Q})$ not satisfy? Give an example of each property that is not satisfied.
2. Which of the properties of being a field does $\text{GL}(2,\mathbb{Q})$ not satisfy? Give an example of each property that is not satisfied.

Problem 6 (Algebraic Properties Of 3 D Vectors And The Cross Product)

Consider the set $\mathbb{R}^3$, together with the two binary operations of vector addition and the cross product. Which of the properties of being a field does $\mathbb{R}^3$ not satisfy? Give an example of each property that is not satisfied.

For fun, please see the wikipedia page on magmas. People have given lots of names to algebraic structures that satisfy various properties.

Definition (Ring)

A ring $R$ is an Abelian group $(R,+)$ together with an additional associative binary operation (multiplication) that satisfies the left and right distributive laws, namely $a(b+c)=ab+ac$ and $(b+c)a=ba+ca$.

Definition (Commutative Ring)

A commutative ring is a ring in which $ab=ba$ (multiplication commutes).

Definition (Unity And Unit)

A unity in a ring is a nonzero element that is an identity under multiplication. A nonzero element of a ring does not need to have a multiplicative inverse. When it does, we say that element is a unit of the ring.

Problem 7 (Recognizing Rings)

Which of the following are rings? Which rings have a unity? Which are commutative?

1. For each $n$, the set $\mathbb{Z}_n$ together with modular addition and multiplication.
2. The set $2\mathbb{Z}$ together with regular addition and multiplication.
3. The set $\mathbb{Q}[x]$ of all polynomials in the variable $x$ with coefficients in $\mathbb{Q}$ together with polynomial addition and multiplication.
4. Let $M_2(\mathbb{Z})$ bet the set of 2 by 2 matrices with entries in $\mathbb{Z}$, together with the usual properties of matrix addition and matrix multiplication.
5. Consider the set $\mathbb{R}^3$, together with the two binary operations of vector addition and the cross product.
6. The set of all real valued functions $f:\mathbb{R}\to\mathbb{R}$, together with function addition $(f+g)(x)=f(x)+g(x)$ and function multiplication $(fg)(x)=f(x)g(x)$.

Problem 8 (Rules Of Multiplication)

Let $R$ be a ring. Prove each of the following:

1. $a0=0a=0$
2. $a(-b)=(-a)b=-ab$
3. $(-a)(-b)=ab$
4. $a(b-c)=ab-ac$.
5. If $R$ has a unity, then $(-1)a = -a$.
6. If $R$ has a unity, then $(-1)(-1)=1$.

Definition (Subring)

A subset $S$ of a ring $R$ is a subring of $R$ if $S$ is itself a ring with the operations of $R$.

Problem 9 (Subring Test)

Let $R$ be ring. Prove that a nonempty subset $S$ of a ring $R$ is a subring of $R$ if $S$ is closed under subtraction and multiplication - that is, if $a-b$ and $ab$ are in $S$ whenever $a$ and $b$ are in $S$.

Problem 10 (Examples Of Rings Different Than The Integers)

For each item below, give an example of a ring $R$ and elements in the ring that satisfy the requested property.

1. $ab=0$ but neither $a$ nor $b$ equals $0$.
2. $ab=ac$ and $a\neq 0$ but $b\neq c$.
3. $ab=0$ but $ba\neq 0$.
4. $a^2=a$ but $a$ is neither 0 or 1.

Definition (Zero Divisor)

A zero-divisor is a nonzero element $a$ of a commutative ring $R$ such that there is a nonzero element $b\in R$ with $ab=0$.

Definition (Integral Domain)

An integral domain is a commutative ring with unity and no zero-divisors.

Problem 11 (Integral Domains Have The Cancellation Law)

Let $R$ be a commutative ring with unity. Prove that the following two statements are equivalent:

1. The ring $R$ is an integral domain.
2. For every $a,b,c\in R$ with $a\neq 0$, the equality $ab=ac$ implies $b=c$.

Definition (Gaussian Integers)

The set $\mathbb{Z}[i]=\{a+bi\mid a,b\in\mathbb{Z}\}$ is called the Gaussian integers.

Problem 12 (The Gaussian Integers Is An Integral Domain)

Use the subring test to show that the Gaussian Integers is a subring of the complex numbers $\mathbb{C}$. Then show that the Gaussian integers is an integral domain.

Problem 13 (Gaussian Integers Under Modular Arithmetic)

Consider the commutative rings $\mathbb{Z}_p[i]=\{a+bi \mid a,b\in \mathbb{Z}_p \}$ for $p\in\{2,3,5\}$. In this problem we'll analyze the multiplicative structure and determine which ring are integral domains, and which are fields.

1. Construct a multiplication table for $\mathbb{Z}_2[i]$. Is this ring an integral domain? Is it a field?
2. Construct a multiplication table for $\mathbb{Z}_3[i]$. Is this ring an integral domain? Is it a field?
3. Is $\mathbb{Z}_5[i]$ an integral domain? We'll soon show that any finite integral domain is a field.
4. Optional: Make a conjecture for which $p$ the ring $\mathbb{Z}_p[i]=\{a+bi \mid a,b\in \mathbb{Z}_p \}$ is an integral domain.

Problem 14 (What Properties Do Subrings Inherit)

Suppose $R$ is a ring, and $S$ is a subring of $R$.

1. If $R$ is an integral domain, what properties of being an integral domain does $S$ inherit?
2. If $R$ is a field, what properties of being a field does $S$ inherit?
3. Challenge: Find an example of a ring $R$ and a subring $S$ so that both $R$ and $S$ have a unity, but the unity of $S$ is not the same as the unity of $R$.

Problem 15 (Some Subrings Of The Complex Numbers)

Let $k$ be an integer. The sets $\mathbb{Z}[\sqrt{k}] = \{a+b\sqrt{k}\mid a,b\in \mathbb{Z}\} $ and $\mathbb{Q}[\sqrt{k}] = \{a+b\sqrt{k}\mid a,b\in \mathbb{Q}\} $ are clearly nonempty subsets of the field $\mathbb{C}$.

1. Prove that both of these subsets are subrings of the complex numbers.
2. Prove that $\mathbb{Z}[\sqrt{k}]$ is an integral domain.
3. Prove that $\mathbb{Q}[\sqrt{k}]$ is a field.

Let's show that any time we start with an integral domain, then the ring of polynomials with coefficients in that integral domain will still be an integral domain. In other words, let's show that any time you multiply two polynomials and obtain the zero polynomial, then one of the polynomials must have been zero to start with.

Problem 16 (A Polynomial Ring Over An Integral Domain Is An Integral Domain)

If $D$ is an integral domain, show that $D[x]$, the set of all polynomials with coefficients in $D$, is an integral domain.

Problem 17 (Properties Needed For A Factor Group To Be A Factor Ring)

Suppose $R$ is a ring and $A$ is a subring of $R$. Because $A$ is a subgroup of $R$, we know that $R/A$ is an Abelian group, as factor groups of Abelian groups are Abelian. Recall that $$R/A = \{r+A \mid r\in R \},$$ the collection of cosets of $A$.

1. What would it take for $R/A$ to be a ring? What properties must we satisfy? Write out the needed properties.
2. Suppose that $R/A$ is a ring. What additional facts about the cosets must hold to guarantee that $R/A$ is an integral domain?
3. If $R/A$ is an integral domain, what would we need to guarantee that $R/A$ is a field?

Just as we defined a group homomorphism to be a map from one group another that preserved the group operation, we'll define a ring homomorphism to preserve both ring structures.

Definition (Ring Homomorphism And Isomorphism)

A ring homomorphism $\phi$ from a ring $R$ to a ring $S$ is a mapping from $R$ to $S$ that preserves the two ring operations. In other words $\phi(a+b)=\phi(a)+\phi(b)$ and $\phi(ab)=\phi(a)\phi(b)$. A bijective ring homomorphism is called a ring isomorphism.

We've been working with a ring homomorphism since we started studying group theory. This ring homomorphism is precisely the map from $\mathbb{Z}$ to $\mathbb{Z}_n$ obtained through modular arithmetic. The next exercise has you show this. In essence, a ring homomorphism is just a generalization of this map. The kernel of a group homomorphism is the collection of group elements that map to zero. The same holds true for the kernel of a ring homomorphism.

Definition (Kernel Of A Ring Homomorphism)

Let $\phi:R\to S$ be a ring homomorphism. The kernel of $\phi$ is the set $$\ker \phi = \{r\in R\mid \phi(r)=0\}.$$

When studying groups, we invented the word normal subgroup to parallel the properties of a kernel. A subgroup of a group is normal precisely when it is the kernel of a group homomorphism. We then used these properties to create factor groups. We now do the exact same thing with rings. We'll first look at some properties of the kernel, and then we'll turn our attention to factor rings.

Problem 18 (Kernels Are Closed Under Multiplication By Arbitrary Elements)

Let $\phi:R\to S$ be ring homomorphism with kernel $K$. Show the following:

1. The kernel $K$ is a subring of $R$.
2. If $r\in R$ and $k\in K$, then we have $rk\in K$ and $kr\in K$.

The two properties above are precisely the key for characterizing when we can create a factor ring. We use the word ideal to describe these subrings. The next problem shows that you can create a factor ring, provided you have an ideal.

Definition (Ideal)

A subring $A$ of $R$ is called an ideal if $ra\in A$ and $ar\in A$ whenever $a\in A$ and $r\in R$.

Problem 19 (Ideals Give Us Factor Rings)

Let $R$ be a ring and let $A$ be a subring of $R$. Show the following are equivalent.

• The set of cosets $\{ r+A\mid r\in R\}$ is a ring under the operations $(s+A)+(t+A) = (s+t)+A$ and $(s+A)(t+A) = st+A$.
• The subring $A$ is an ideal of $R$.

Definition (Factor Ring)

Let $R$ be a ring and let $A$ be an ideal of $R$. The set of cosets $\{ r+A\mid r\in R\}$ together with the binary operations $(s+A)+(t+A) = (s+t)+A$ and $(s+A)(t+A) = st+A$ is called the factor ring of $R$ by $A$, or just the factor ring $R/A$.

We'll return to factor rings more next time. They happen to be a key tool in our future study, and we'll spend plenty of time becoming comfortable with them. For the rest of today, the next few problems have you practice with some of the definitions we've been building up over the last week, as well as adding in the characteristic of a field and the ideal generated by something.

Problem 20 (Finite Integral Domains Are Fields)

Suppose that $R$ is a finite integral domain. Prove that $R$ is a field.

Problem 21 (Adjoining The Square Root Of A Positive Integer To $\mathbb{Z}_p$)

Show that $\mathbb{Z}_7[\sqrt{3}] = \{a+b\sqrt{3}\mid a,b\in \mathbb{Z}_7\} $ is a field. Given a prime $p$ and positive integer $k$, determine conditions that are both necessary and sufficient for the ring $\mathbb{Z}_p[\sqrt{k}] = \{a+b\sqrt{k}\mid a,b\in \mathbb{Z}_p\}$ to be a field.

Definition (Characteristic Of A Ring)

The characteristic of a ring $R$, written $\text{char } R$, is the smallest positive integer $n$ such that $n\cdot a = a+a+\cdots+a=0$ for all $a\in R$. If no such integer exists, then we say $R$ has characteristic zero.

Problem 22 (Characteristics And Rings With Unity)

Suppose that $R$ is a ring with unity.

1. Show that the characteristic of $R$ is equal to the least positive integer $n$ such that $n\cdot 1=0$, provided the characteristic is not zero.
2. Show that the characteristic of an integral domain is either zero or prime.

Problem 22.5 (Text Exercise 12.15)

Let $a,b$ be elements of a ring and let $m,n\in \mathbb{Z}$. Show that $(m\cdot n)(a\cdot b)=(m\cdot a)(n\cdot b)$.

Definition (Ideal)

A subring $A$ of $R$ is called an ideal if $ra\in A$ and $ar\in A$ whenever $a\in A$ and $r\in R$.

Problem 19 (Ideals Give Us Factor Rings)

Let $R$ be a ring and let $A$ be a subring of $R$. Show the following are equivalent.

• The set of cosets $\{ r+A\mid r\in R\}$ is a ring under the operations $(s+A)+(t+A) = (s+t)+A$ and $(s+A)(t+A) = st+A$.
• The subring $A$ is an ideal of $R$.

Definition (Principle Ideal Generated by $a$, or $\left<a\right>$)

Let $R$ be a commutative ring with unity and let $a\in R$. The set $\left<a\right> = \{ra| \ r\in R\}$ is an ideal of $R$ called the principle ideal generated by $a$.

Definition (Ideal Generated By $a_1, \ldots, a_n$, or $\left<a_1,a_2,\ldots,a_n\right>$)

Let $R$ be a commutative ring with unity, and let $a_1, \ldots, a_n \in R$. The set $I=\left<a_1,a_2,\ldots,a_n\right> = \{r_1a_1+\cdots +r_na_n|r_i\in R \}$ is called the ideal generated by $a_1, \ldots, a_n$. Any other ideal that contains $a_1, \ldots, a_n$ must contain $I$.

The definitions above claim that the sets given are actually ideals. Anytime a definition makes a claim, you must prove that claim is true. The following problem has you do this.

Problem 23 (The Ideal Generated By A Subset Is An Ideal)

Let $R$ be a ring and $S=\{a_1, a_2, \ldots a_n\}$ be subset of $R$ consisting of $n$ elements (where $n$ is some positive integer. Prove that the ideal generated by $S$ is actually an ideal of $R$.

Problem 23.5 Alternate Definition of Ideal Generated by a subset:)

Suppose that $R$ is a ring and $S$ is a subset of $R$. Let $M$ be the intersection of all ideals in $R$ that contain $S$.

1. Prove that $M$ is an ideal of $R$ that contains $S$.
2. Prove that any ideal of $R$ that contains $S$ must also contain $M$.
3. If $S$ is finite and $R$ is commutative, prove that $M = \left<S\right>$.

The next few examples are designed to help us get a better handle on factor rings. Recall that $\left<a\right>$ we call the principle ideal generated by $a$.

Problem 24 (A Matrix Factor Ring)

Consider the set of two by two matrices $R=M_2(\mathbb{Z})$ with integer coefficients. Let $A$ the set of matrices whose coefficients are multiples of 3.

1. Show that $A$ is an ideal of $R$.
2. Find three different elements of $R$ that are in the coset $\begin{bmatrix}5&-2\\7&9\end{bmatrix}+A$.
3. How many distinct elements are in this factor ring? Justify your answer.
4. Challenge: This factor ring is isomorphic to another matrix ring we have already seen. What is this ring? You don't need to prove your answer.

Problem 25 (A Factor Ring Of The Gaussian Integers)

Let $R=\mathbb{Z}[i]$, $a=3-i$, and let $A=\left<a\right>$. We would like to examine the factor ring $R/A$, determine how many elements are in this factor ring, and find a simple ring to which $\mathbb{Z}[i]/\left<3-i\right>$ is isomorphic.

1. Why do we know $3+A=i+A$? Use this to explain why $10+A=0+A$.
2. Explain why every element of $R/A$ must be of the form $k+A$ where $k\in \{0,1,2,\ldots 9\}$, so there are at most 10 elements.
3. Suppose the integer $k$ is an element of $A = \left<a\right> = \{ra\mid r\in R\}$. In other words, suppose that there exists an element $r\in R$ such that $k+0i = ra = (c+di)(3-i)$. Use this to show that $k$ must be a multiple of 10.
4. State a much simpler ring to which $R/A$ is isomorphic, you don't need to prove your answer.

After completing these exercises (or if you get stuck), I strongly recommend that you take a few minutes and read the examples on pages 263-266. They summarize many of the key ideas we need to focus on with factor rings.

Problem 26 (Factor Rings Of $\mathbb{Z}$ And $\mathbb{Z}[x]$)

Answer the following questions as they pertain to the integral domains $\mathbb{Z}$ and $\mathbb{Z}[x]$. You are welcome to rapidly make claims about factor rings, without proof, as we have seen many of these as factor groups in the past.

1. We know that the ideals of $\mathbb{Z}$ are of the form $n\mathbb{Z} = \left< n\right>$, the set of multiples of $n$.
   • For which $n$ is the factor ring $\mathbb{Z}/\left<n\right>$ an integral domain?
   • For which $n$ is the factor ring $\mathbb{Z}/\left<n\right>$ a field?
2. Now consider the ring of polynomials $\mathbb{Z}[x]$. The ideal $\left<n\right>$ is now the set of polynomials whose coefficients are multiples of $n$. It should not be a surprise that $\mathbb{Z}[x]/\left<n\right> \approx \mathbb{Z}_n[x]$.
   • For which $n$ is the factor ring $\mathbb{Z}[x]/\left<n\right>$ an integral domain?
   • Show that the factor ring $\mathbb{Z}[x]/\left<n\right>$ is never a field, regardless of which $n$ you pick.
3. We can look at other ideals of $\mathbb{Z}[x]$.
   • Show that $\mathbb{Z}[x]/\left<x\right>$ is an integral domain, but not a field.
   • Show that $\mathbb{Z}[x]/\left<3,x\right>$ is a field.

As seen in the previous exercise, sometimes when we create a factor ring, we obtain an integral domain, and sometimes we obtain a field. We would like some words to describe ideals for which the corresponding factor ring is an integral domain, or a field. It would be nice to have a characterization that we could check in the ideal itself, without having to actually look at the factor ring.

Problem 27 ($R/A$ Is An Integral Domain Iff $A$ is prime)

Let $R$ be a commutative ring with unity, and let $A$ be a proper ideal of $R$. Prove that the following are equivalent.

• $R/A$ is an integral domain.
• If $a,b\in R$ and $ab\in A$ then $a\in A$ or $b\in A$. (We say that $A$ is a prime ideal).

Why do we call an ideal a prime ideal if the second condition above is satisfied? Recall in the integers that if $p$ is a prime, then if $ab$ is a multiple of $p$, then either $a$ or $b$ must be a multiple of $p$. So $ab\in \left<p\right>$ forces either $a\in \left<p\right>$ or $b\in \left<p\right>$. This condition forces the number to be prime. We extend the notation of prime numbers to prime ideals. Any time a product is divisible by a prime, then one of the two factors must be divisible by the prime. We'll extend this to say that any time a product is in a prime ideal, one of the factors must be in the prime ideal.

We now have a simple way to check if $R/A$ is an integral domain. We just have to make sure that if $ab\in A$, then either $a\in A$ or $b\in A$. To obtain a field, we need even more.

Problem 28 (Characterizing When Factor Rings Are Fields)

Suppose $R$ is a commutative ring with unity and $A$ is an ideal. Prove that the following are equivalent.

• $R/A$ is a field.
• For every $b\in R$ with $b\notin A$, the set $B=\{bc+a\mid c\in R, a\in A\}$ contains the unity $1$ from $R$.

Problem 29 (Obtaining A New Ideal By Adding One Element)

Let $A$ be an ideal of the commutative ring $R$ with unity. We'd like to increase the size of $A$ by adding in a single element $b$. Show the following:

1. Pick $b\in R$. The set $B=\{bc+a\mid c\in R,a\in A\}$ is an ideal of $R$ that contains both the element $b$ and subset $A$.
2. We know $1\in A$ if and only if $A=R$.

The set $B$ described above is the smallest ideal of $R$ that contains $b$ and every element in $A$, so we call it the ideal generated by $b$ and $A$.

Given a proper ideal $A_1$, we can use the idea above to create an ideal $A_2$ that properly contains $A_1$ (add one element not in $A_1$). If this ideal is not the entire ring, we could then continue this process, possibly indefinitely, to obtain a sequence of ideals that properly contain the previous. Such a sequence $A_1\subset A_2\subset A_3\subset \cdots \subset A_n\subset \cdots$ is called an ascending chain of ideals. Once one of these ideals contains the number 1, the sequence terminates. Emmy Noether used this idea to create what we now call Noetherian domains, an integral domain in which any ascending chain of ideals must be finite in length (so the process must stop, no matter what ideal $A$ you start with). We'll come back to Noetherian domains later. See page 275 for more information about Emmy Noether.

Problem 30 (An Ascending Chain Of Ideals In The Integers)

Let $R=\mathbb{Z}$. Consider the ideal $A_1=\left<56\right>.$

1. Find an ascending chain of ideals consisting of three ideals $A_1\subsetneq A_2\subsetneq A_3$ with $A_3=R$.
2. What is the largest $n$ such that $A_1\subsetneq A_2\subsetneq A_3\subsetneq \cdots\subsetneq A_n=R$ is an ascending chain of ideals? How many such chains are there of this length?
3. If $n\in \mathbb{Z}$, describe a process we could use to find a longest possible ascending chain of ideals with $\left<n\right>\subsetneq A_2\subsetneq \cdots\subsetneq A_n=\mathbb{Z}$.

The two facts from the problem Obtaining A New Ideal By Adding One Element will help us characterize the properties of an ideal $A$ that will result in $R/A$ being a field. Remember, the following:

• We need to make sure that if $b\notin A$, then there exists $c\in R$ such that $bc\in 1+A$, or equivalently $1\in bc+A$.
• So given any element $b\notin A$, if we can show that the ideal $B=\{bc+a\mid c\in R, a\in A\}$ must contain 1, which means $B=R$, then we'd win.
• This is basically the same as showing that given any ideal $B$ trapped between $A$ and $R$, so $A\subset B\subset R$, then if $B$ is not equal to $A$, it must equal $R$. We call an ideal such as $A$ a maximal ideal.

The next problem has you carefully show that $R/A$ is a field if and only if $A$ is a maximal ideal.

Problem 31 ($R/A$ Is A Field Iff $A$ Is Maximal)

Let $R$ be a commutative ring with unity, and let $A$ be a proper ideal of $R$. Prove that the following are equivalent.

• $R/A$ is a field.
• Whenever $B$ is an ideal of $R$ and $A\subseteq B\subseteq R$, then either $B=A$ or $B=R$. (We say that $A$ is a maximal ideal.)

The previous problems give us the following definitions of prime and maximal ideals. Basically, these are now characteristics of an ideal that we can check to determine if $R/A$ is an integral domain or a field, without having to ever consider elements of the factor ring.

Definition (Prime Ideal And Maximal Ideal)

• A prime ideal $A$ of a commutative ring $R$ is a proper ideal of $R$ such that $a,b\in R$ and $ab\in A$ imply $a\in A$ or $b\in A$.
• A maximal ideal $A$ of a commutative ring $R$ is a proper ideal of $R$ such that, whenever $B$ is an ideal of $R$ and $A\subseteq B\subseteq R$, then $B=A$ or $B=R$.

Let's look at another example of some interesting things that can happen in a ring.

Definition (Idempotent And Nilpotent)

Let $R$ be a ring.

• We say that $a$ is an idempotent of $R$ if $a^2=a$.
• We say that $a$ is nilpotent if $a^n=0$ for some integer $n$.

Problem 32 (Finding Idempotent And Nilpotent Elements In A Matrix Ring)

Complete the following:

1. In the ring $M_2(\mathbb{Z})$, the matrices $\begin{bmatrix}0&0\\0&0\end{bmatrix}$, $\begin{bmatrix}1&0\\0&1\end{bmatrix}$, $\begin{bmatrix}1&0\\0&0\end{bmatrix}$, $\begin{bmatrix}0&0\\0&1\end{bmatrix}$, are idempotents. Find two others.
2. Show that $\begin{bmatrix}0&t\\0&0\end{bmatrix}$ is nilpotent in $M_2(\mathbb{Z})$ and that $\begin{bmatrix}0&t&0\\0&0&t\\0&0&0\end{bmatrix}$ is nilpotent in $M_3(\mathbb{Z})$, where $t\in\mathbb{Z}$.
3. Let $X=\begin{bmatrix}0&t&0&0&0\\0&0&t&0&0\\0&0&0&t&0\\0&0&0&0&t\\0&0&0&0&0\end{bmatrix}$. Compute $X^k$ for each positive integer $k$. What patterns do you see? Is $X$ a nilpotent element of $M_5(\mathbb{Z})$?

The matrices above are central to finding the Jordan form of a matrix, and then using the Jordan form to compute the matrix exponential. Come see me out of class if you would like more information on this topic.

Problem 33 (Some Polynomial Factor Rings Of $\mathbb{Z}[x]$)

Let $R=\mathbb{Z}[x]$. Consider the three ideals $A=\left<x^2\right>$, $B=\left<x^2- 1\right>$, $C=\left<x^2+1\right>$.

1. Show that $R/A=\{a+bx+A\mid a,b\in\mathbb{Z}\}$.
2. Show that $R/A$ is not an integral domain.
3. Is $R/B$ an integral domain? Prove your answer.
4. Is $R/C$ an integral domain? Prove your answer.

Problem 34 (Why Are Zero Divisors Such A Problem)

Consider the polynomial $p(x)=x^2-5x+6 = (x-2)(x-3)$. We can view this as a polynomial in $\mathbb{Z}_n[x]$ for any given $n$.

1. Find all solutions to the equation $x^2-5x+6=0$ as a polynomial in $\mathbb{Z}_5[x]$.
2. Show that the equation $x^2-5x+6=0$ as a polynomial in $\mathbb{Z}_6[x]$ has 4 solutions. Then show that $x^2-5x+6$ can be factored as both $(x+4)(x+3)$ and $(x)(x+1)$. As a suggestion, since there are only 6 numbers in $\mathbb{Z}_6$, you can quickly determine which is a zero by just plugging it into the equation and then seeing if you get 0 mod 6.
3. Find all solutions to $x^2-5x+6=0$ as a polynomial in $\mathbb{Z}_8[x]$. Then factor this polynomial using only coefficients in $\mathbb{Z}_8$. Again, there are only 8 numbers to test to see if they are zeros. Just plug them all in. You might want to use Excel or write a computer program to make this fast.
4. Find all solutions to $x^2-5x+6=0$ as a polynomial in $\mathbb{Z}_{14}[x]$. Factor this polynomial using only coefficients in $\mathbb{Z}_{14}$. Then factor it in a different way.
5. Find all solutions to $x^2-5x+6=0$ as a polynomial in $\mathbb{Z}_{30}[x]$. (You should get more than 4 answers.) One way to factor the polynomial is of course $(x-2)(x-3)=(x+28)(x+27)$. Find one other way.

Problem 35 (When Is A Polynomial Factor Ring An Integral Domain)

Let $R=\mathbb{Z}[x]$. Suppose that $A=\left<p(x)\right>$ is a principle ideal generated by a single polynomial.

1. Find a polynomial $p(x)$ of degree 2 such that $R/A$ is not an integral domain. Then find one of degree 3 and degree 4.
2. Find a polynomial $p(x)$ of degree 3 such that $R/A$ is an integral domain.
3. If you know that $R/A$ is not an integral domain, what do you know about $p(x)$?
4. State a simple condition on $p(x)$ that is equivalent to $R/A$ being an integral domain.

The next two problems are designed as review problems, to help you practice with the definitions. We may not prove all of these in class. They should be very similar to problems we completed last semester.

Problem 36 (The Ideal Test)

Suppose that $A$ is a nonempty subset $A$ of a ring $R$. Prove that $A$ is an ideal of $R$ if

1. $a-b\in A$ whenever $a,b\in A$, and
2. $ra$ and $ar$ are in $A$ whenever $a\in A$ and $r\in R$.

In other words, prove that an ideal is a nonempty subset that is closed under subtraction and multiplication by an arbitrary ring element.

Problem 37 (Properties Of Ring Homomorphisms)

Let $\phi:R\to S$ be a ring homomorphism. Prove the following properties.

1. For any $r\in R$ and any positive integer $n$, $\phi(n\cdot r) = n\phi(r)$ and $\phi(r^n) = (\phi(r))^n$.
2. If $A$ is a subring of $R$, then $\phi (A) = \{\phi(a)|a\in A\}$ is a subring of $S$.
3. If $A$ is an ideal, then $\phi(A)$ is an ideal of $\phi(R)$.
4. If $B$ is an ideal of $S$, then $\phi^{-1}(B) = \{r\in R|\phi(r)\in B\}$ is an ideal of $R$.
5. If $R$ is commutative, then $\phi(R)$ is commutative.
6. If $R$ has a unity 1, if $S\neq \{0\}$, and if $\phi$ is onto, then $\phi(1)$ is the unity of $S$.
7. We know $\phi$ is an isomorphism if and only if $\phi$ is onto and $\ker\phi = \{r\in R|\phi(r)=0\} = \{0\}$.
8. If $\phi$ is an isomorphism from $R$ onto $S$, then $\phi^{-1}$ is an isomorphism from $S$ onto $R$.

Theorem (First Isomorphism Theorem For Rings)

Let $\phi$ be a ring homomorphism from $R$ to $S$. The mapping from $R/\ker\phi$ to $\phi(R)$, given by $r+\ker\phi \to \phi(r)$ is an isomorphism. In symbols, we have $R/\ker\phi\cong \phi(R).$

Problem 38 (First Isomorphism Theorem For Rings Proof)

Prove the first isomorphism theorem for rings. You'll need to first prove that the map defined in the statement of the theorem is well-defined, then you can use the properties of ring homomorphisms to show that the map is an isomorphism.

Problem 39 (Some Polynomial Factor Rings)

Complete the following:

1. Use the first isomorphism theorem to prove that $\mathbb{Z}[x]/\left<x^2+1\right>$ is isomorphic to $\mathbb{Z}[i]$. From this we know that $\mathbb{Z}[x]/\left<x^2+1\right>$ is an integral domain and not a field.
2. Is $\mathbb{Q}[x]/\left<x^2+1\right>$ an integral domain? a field?
3. Is $\mathbb{R}[x]/\left<x^2+1\right>$ an integral domain? a field?
4. Is $\mathbb{C}[x]/\left<x^2+1\right>$ an integral domain? a field?

The next few definitions are things you already know, I am just including them here for completeness. Make sure you read the definition of the degree of a polynomial.

Definition (Polynomial Ring With Coefficients In R)

Let $R$ be commutative ring. The set of formal symbols $$R[x] = \{a_nx^n+\cdots+a_1x+a_0|a_i\in R, n\in Z^+\}$$ is called the ring of polynomials over $R$ in the indeterminate $x$. Two elements are considered equal if and only if the have the same coefficients. Addition is defined component wise, and multiplication is defined using regular polynomial distribution.

Definition (Degree Of A Polynomial)

If $f(x) = a_nx^n+\cdots+a_1x+a_0$ with $a_n\neq 0$ then we say the degree of $f(x)$ is $n$. The polynomial $f(x)=0$ has no degree (it is not degree zero).

Let's now prove that given any polynomials $f(x)$ and $g(x)$, we can always perform long division and write $f(x)=q(x)g(x)+r(x)$ where the degree of $r$ is less than the degree of $g$, or $r=0$. To figure out a proof, just pretend like you are going to do long division. What would your first step be? You should be able to reduce the degree of $f(x)$, and then use induction on the degree of $f(x)$.

Theorem (Division Algorithm For Polynomials)

Let $F$ be a field and let $f(x)$ and $g(x)\in F[x]$ with $g(x)\neq 0$. Then there exist unique polynomials $q(x)$ and $r(x)$ such that $f(x)=g(x)q(x)+r(x)$ and either $r(x)=0$ or $\deg r(x) < \deg g(x)$.

Problem 40 (Division Algorithm For Polynomials Proof)

Prove Theorem Division Algorithm For Polynomials.

A lot of our work has been focused on determining when a ring must be a field. If it's a finite ring, there's a really easy way to immediately throw out the possibility that the ring is a field, by just counting elements. If the order of the ring is not a power of a prime, then it can't be a field. The next problem has you show this.

Problem 41 (The Order Of A Finite Field)

Suppose that $F$ is a finite field of characteristic $p$. Show that the order of $F$ must be $p^n$ for some integer $n$.

Suppose we know that $D$ is an integral domain. If $D$ is finite, we've already shown it must be a field. However, if $D$ is not finite, can we somehow obtain a field from $D$? As an example, we already know that we can obtain the rationals $\mathbb{Q}$ from $\mathbb{Z}$ by defining division, in that we say $a/b=c/d$ if and only $ad=bc$ where $b\neq 0$ and $d\neq 0$. We'll show that this approach allows us to take any integral domain and from it create a field (called the field of quotients).

To obtain this field of fractions, let's first review what an equivalence relation is, as we use equivalence relations to define division.

Definition (Equivalence Relation)

Let $S$ be set. Let $\cong$ be a relation on $S$, meaning $\cong$ is a collection $\mathscr{C}$ of ordered pairs of $S$. We way that $A\cong B$ if and only if the ordered pair $(A,B)$ is an element of $\mathscr{C}$. We say that $\cong$ is an equivalence relation if and only if

1. (Reflexive) For every $A\in S$, we know that $A\cong A$ (so the ordered pair $(A,A)$ is always in $\mathscr{C}$).
2. (Symmetric) If $A\cong B$, then $B\cong A.$
3. (Transitive) If $A\cong B$ and $B\cong C$, then $A\cong C$.

Problem 42 (The Rational Are Obtained From The Integers From An Equivalence Relation)

Consider the set of ordered pairs $S=\{(a,b)\mid a,b\in\mathbb{Z},b\neq0\}$. Define a relation on $S$ by saying that $(a,b)\cong(c,d)$ if and only if $ad=bc$. We'll generally write $(a/b)=(c/d)$ to mean that $(a,b)\cong(c,d)$.

1. Prove that the relation above is an equivalence relation.
2. If we replace $\mathbb{Z}$ with any integral domain $D$, prove that we still obtain an equivalence relation on $S$. (If your work on part 1 didn't refer to the integers specifically, then this part should automatically follow.)

Problem 43 (The Field Of Quotients Of An Integral Domain)

Consider again the set of ordered pairs $S=\{(a,b)\mid a,b\in\mathbb{Z},b\neq0\}$, together with the equivalence relation $(a,b)\cong(c,d)$ if and only if $ad=bc$. Let $F$ be the set of equivalence classes of $S$ under the relation $\cong$. We can write an element in $F$ as $ [a/b] $ where the brackets remind us that there are infinitely many ways to represent elements in $F$ (for example we know $ [2/4]=[3/6] $ because $2\cdot 6=3\cdot 4$). On the set $F$, define the operations $$ [a/b]+[c/d]=[(ad+bc)/(bd)]\quad \text{and}\quad [a/b]\cdot[c/d]=[ac/bd]. $$

1. Prove $+$ and $\cdot$ are binary operations on $F$. This will require you show that if $ [a/b] \cong [a'/b']$ and $ [c/d] \cong [c'/d']$ then we must have $ [(ad+bc)/(bd)] \cong [(a'd'+b'c')/(b'd')] $, and a similar fact for multiplication.
2. Prove that $(F,+,\cdot)$ is a field.
3. If we replace $\mathbb{Z}$ with any integral domain $D$, prove that $(F,+,\cdot)$ is a field.

Problem 44 (Not Every Subring Is An Ideal)

Give an example of a ring $R$ and a subring $S$ so that $S$ is not an ideal of $R$. Make sure you prove that $S$ is a subring, but not an ideal.

Problem 45 (A Homomorphism From Z To A Ring With Unity)

Let $R$ be a ring with unity 1. After you have finished the first step below, you should be able to give answers to the remaining parts by referring to the first part and using the properties of ring homomorphisms.

1. Show that the mapping $\phi:\mathbb{Z}\to R$ given by $\phi(n)=n\cdot 1$ is a ring homomorphism.
2. Show that if $R$ has characteristic $n>0$, then $R$ contains a subring isomorphic to $Z_n$.
3. Show that if $R$ has characteristic $n=0$, then $R$ contains a subring that is isomorphic to $Z$.
4. Show that for any positive integer $m$, the mapping of $\phi:\mathbb{Z}\to \mathbb{Z}_m$ given by $x\to x$ mod $m$ is a ring homomorphism.

Problem 46 (Every Field Contains A Subfield Isomorphic To $\mathbb{Z}_p$ or $\mathbb{Q}$)

Suppose that $F$ is a field.

1. If $F$ has prime characteristic $p$, show that $F$ contains a subfield isomorphic to $Z_p$.
2. If $F$ has characteristic 0, show that $F$ contains a subfield isomorphic to $\mathbb{Q}$.

Problem 47 (The Remainder Theorem)

Let $F$ be a field, $a\in F$, and $f(x)\in F[x]$. Prove that $f(a)$ is the remainder in division of $f(x)$ by $x-a$.

Problem 48 (The Factor Theorem)

Let $F$ be a field, $a\in F$, and $f(x)\in F[x]$. Prove that $a$ is a zero of $f(x)$ if and only if $x-a$ is a factor of $f(x)$.

Problem 49 (Polynomials of degree $n$ have at most $n$ zeros)

Show that a polynomial of degree $n$ over a field has at most $n$ zeros, counting multiplicity.

Problem 50 (We have $I=\left<g(x)\right>$ if and only if $g(x)$ is a polynomial of minimal degree in $I$)

Let $F$ be field and $I$ a nonzero ideal in $F[x]$, and $g(x)$ an element of $F[x]$. Show that $I=\langle g(x)\rangle$ if and only if $g(x)$ is a nonzero polynomial of minimal degree in $I$.

In the previous problem, we showed that any ideal in $F[x]$ is generated by a single polynomial. That's pretty remarkable, in that no matter what polynomials we use to generate an ideal, we can always find a single polynomial that generates the whole ideal. This property turns out to be extremely useful, and as such we'll give any ring with this property a special name.

Definition (Principal Ideal Domain PID)

A principal ideal domain (PID) is an integral domain in which every ideal has the form $\left<a\right> = \{ra|r\in R\}$ for some $a$ in $R$.

We know that $F[x]$ is a principle ideal domain provided $F$ is a field. Are there other principle ideal domains?

Problem 51 (Polynomial Rings Over PIDs need not be PIDs)

Show that $\mathbb{Z}$ is a principle ideal domain. Then show that $\mathbb{Z}[x]$ is not a principle ideal domain.

Problem 52 (The Degree Of A Product Of Polynomials)

Suppose that $D$ is an integral domain, and suppose that $f(x),g(x)\in D[x]$.

1. Prove that $\deg(f(x)\cdot g(x)) = \deg(f(x))+\deg(g(x))$.
2. Then give an example of a commutative ring $R$ and two polynomials so that $\deg(f(x)\cdot g(x)) < \deg(f(x))+\deg(g(x))$.

We'd like to know when we obtain polynomials $p(x)\in F[x]$ such that $F[x]/\left<p(x)\right>$ is a field. We already know this means that $I=\left<p(x)\right>$ must be a maximal ideal in $F[x]$. We've also seen that if we can factor $p(x)$ as the product of two polynomials (that don't have multiplicative inverses), then $I$ is not maximal. Let's make a definition to make this precise.

Definition (Irreducible Polynomial Reducible Polynomial)

Let $D$ be an integral domain. A polynomial $f(x)$ from $D[x]$ that is neither the zero polynomial nor a unit in $D[x]$ is said to be irreducible over $D$ if, whenever $f(x)$ is expressed as a product $f(x)=g(x)h(x)$, with $g(x)$ and $h(x)$ from $D[x]$, then $g(x)$ or $h(x)$ is a unit in $D[x]$. A nonzero, nonunit element of $D[x]$ that is not irreducible over $D$ is called reducible over $D$.

In general, it's a hard problem to determine when a polynomial is reducible or irreducible. However, there are a few cases where it's easy.

Problem 53 (Reducibility Test For Degrees 2 And 3)

Let $F$ be a field. If $f(x)\in F[x]$ and deg $f$ is 2 or 3, then prove that $f(x)$ is reducible over $F$ if and only if $f(x)$ has a zero in $F$.

Before we look at any other reducibility tests, let's prove a key theorem, namely that $p(x)$ is irreducible if and only if $\left<p(x)\right>$ is maximal. We really want to know when we can guarantee that $F[x]/\left<p(x)\right>$ is a field.

Problem 54 (We Know $\left<p(x) \right>$ Is Maximal Iff $p(x)$ Is Irreducible)

Let $F$ be a field and let $p(x)\in F[x]$. Prove that $\left<p(x) \right>$ is a maximal ideal if and only if $p(x)$ is irreducible over $F$.

This next definition just gets rid of a complication from some polynomials, by removing from the polynomial any common factors.

Definition (Content Of A Polynomial Primitive Polynomial)

The content of a polynomial in $\mathbb{Z}[x]$ is the greatest common divisor of the coefficients. A primitive polynomial has content 1.

Problem 54.5 (The Product Of Primitives Is Primitive)

Prove that the product of two primitive polynomials is primitive.

As you work through the problems in the next few weeks, you'll want to pay close attention to the assumptions. In some problems we assume that we are working in a field. In some problems, we assume that we are working in an integral domain. The next problem shows that if you can show something is reducible over the field $\mathbb{Q}$, then it is reducible over $\mathbb{Z}$.

Problem 55 (Reducibility Over Q Implies Reducibility Over Z)

Let $f(x)\in \mathbb{Z}[x]$. Prove that if $f(x)$ is reducible over $\mathbb{Q}$, then $f(x)$ is reducible over $\mathbb{Z}$.

The contrapositive to the previous problem is extremely powerful, namely if a polynomial with integer coefficients is not reducible over $\mathbb{Z}$, then it is not reducible over $\mathbb{Q}$. For this reason, we'll now study irreducibility tests over $\mathbb{Z}$.

Problem 56 (Mod P Irreducibility Test)

Let $p$ be a prime and suppose that $f(x)\in \mathbb{Z}[x]$. Let $\bar f (x)$ be the polynomial in $\mathbb{Z}_p[x]$ obtained by reducing the coefficients of $f(x)$ modulo $p$. Prove that if if $\bar f (x)$ is irreducible over $\mathbb{Z}_p$ and $\text{deg }\bar f(x) = \text{deg }f(x)$, then $f(x)$ is irreducible over $\mathbb{Q}$.

Problem 57 (Eisenstein's Criterion)

Let $f(x)=a_nx^n + \cdots +a_1x +a_0$. Prove that if there is a prime $p$ such that $p$ divides every coefficient but $a_n$ and $p^2$ does not divide $a_0$, then $f(x)$ is irreducible over $\mathbb{Q}$.

Problem 58 (Rational Root Test)

Suppose that $$f(x) = a_nx^n+\cdots +a_1x+a_0\in \mathbb{Z}[x],$$ with $a_n\neq 0$. Prove that if $r$ and $s$ are relatively prime and $f(r/s)=0$, then we must have $r\mid a_0$ and $s\mid a_n$.

Problem 59 (Irreducibles Behave Like Prime Numbers)

Let $F$ be a field and suppose that $p(x)\in F[x]$ is irreducible over $F$. Suppose also that $p(x)$ divides the product $a_1(x)a_2(x)\cdots a_n(x)$ where $a_i(x)\in F[x]$ for each $i$. Prove that $p(x)$ must divide $a_k(x)$ for some $k$.

Theorem (Unique Factorization In ZX)

Every polynomial that is not the zero polynomial or a unit in $Z[x]$ can be written in the form $b_1b_2\cdots b_sp_1(x)p_2(x)\cdots p_m(x)$, where the $b_i$'s are irreducible polynomials of degree 0, and the $p_i(x)$'s are irreducible polynomials of positive degree. Furthermore, if we completely factor in 2 ways, $$b_1b_2\cdots b_sp_1(x)p_2(x)\cdots p_m(x)=c_1c_2\cdots c_tq_1(x)q_2(x)\cdots q_n(x),$$ then $s=t$, $m=n$, and after renumbering the $c$'s and $q(x)$'s, we have $b_i=\pm c_i$ and $p_j(x)=\pm q_j(x)$ for all $i$ and $j$.

Problem 60 (Unique Factorization Existence Proof)

Prove that every polynomial that is not the zero polynomial or a unit in $Z[x]$ can be written in the form $b_1b_2\cdots b_sp_1(x)p_2(x)\cdots p_m(x)$, where the $b_i$'s are irreducible polynomials of degree 0, and the $p_i(x)$'s are irreducible polynomials of positive degree.

Problem 61 (Unique Factorization Uniqueness Proof)

Suppose that we have factored a polynomial in $\mathbb{Z}[x]$ in two way, namely $$b_1b_2\cdots b_sp_1(x)p_2(x)\cdots p_m(x)=c_1c_2\cdots c_tq_1(x)q_2(x)\cdots q_n(x).$$ Prove that $s=t$, $m=n$, and after renumbering the $c$'s and $q(x)$'s, we have $b_i=\pm c_i$ and $p_j(x)=\pm q_j(x)$ for all $i$ and $j$.

Definition (Associates Irreducibles Primes)

Let $D$ be an integral domain. All elements below are elements of $D$.

• We say that two elements $a$ and $b$ are associates if $a=ub$ for some unit $u$.
• If $a$ is nonzero and not a unit, then we say $a$ is an irreducible if whenever $a=bc$, then either $b$ or $c$ is a unit.
• If $a$ is nonzero and not a unit, then we say $a$ is a prime if $a\mid bc$ implies $a\mid b$ or $a\mid c$.

Problem 62 (Prime Implies Irreducible)

In an integral domain, prove that if an element $a$ is prime, then $a$ must be irreducible.

Problem 63(Irreducible Polynomials Have A Zero In Some Extension Field)

Let $F$ be a field and suppose that $p(x)$ is an irreducible polynomial over $F$.

1. Prove that $E=F[x]/\left<p(x)\right>$ is an extension field of $F$. (Note: An extension field of $F$ is a field $E$ such that $E$ contains a subfield isomorphic to $F$.)
2. Show that the element $x+\left<p(x)\right>\in E$ is a zero of $p(x)$ in $E$.

Problem 64 (Ascending Chains of Ideals In a PID Are Finite)

Suppose that $R$ is a ring, and that $A_1\subseteq A_2\subseteq A_3\subseteq \cdots$ is nested sequence of ideals of $R$.

1. Prove that the union $\ds \bigcup_{n=1}^{\infty} A_n$ is an ideal of $R$.
2. If $R$ is a principle ideal domain, prove that there exists an integer $k$ so that $A_k=A_n$ for every $n\geq k$. In other words, prove that every ascending chain of ideals in a principle ideal domain contain finitely many different ideals.
3. Challenge: Give an example of a ring $R$ and an infinite ascending chain of ideals so that no two ideals are equal.

You can present in class even if you don't get the third part.

Problem 65 (Every Element is a Product of Irreducibles in a PID)

Suppose that $D$ is a principle ideal domain with $a\in D$ where $a\neq 0$ is not a unit. Prove that $a$ can be written as the product of irreducibles.

Problem 66 (Every Polynomial Has A Root In Some Extension Field)

Let $F$ be a field and $f(x)\in F[x]$ be nonzero and not a unit. Prove that there exists an extension field $E$ in which $f(x)$ has a zero.

Definition.The Derivative Of A Polynomial Over a Ring

Let $R$ be a ring and $f(x)\in R[x]$. If $f(x)=0$, then we define the derivative of $f(x)$ to be zero. Otherwise, we define the derivative of $f(x) = a_nx^n+\cdots +a_1x+a_0$ where $a_n\neq 0$ to be $$f'(x) = n\cdot a_nx^{n-1}+(n-1)a_{n-1}x^{n-2}+\cdots + 2a_2 x + a_1.$$

Problem 67 (The Sum and Product Rule for Derivatives)

Suppose that $F$ is a field and that $f(x),g(x)\in F[x]$.

1. Prove the sum rule, namely that $(f+g)'(x)=f'(x)+g'(x)$.
2. Prove the product rule, namely that $(fg)'(x)=f'(x)g(x)+f(x)g'(x)$.
3. What properties of the field $F$ were needed to complete your proofs? State a stronger theorem that requires less assumptions.

Problem 68 (Multiple Zeros and The Derivative Proof)

Suppose that $F$ is field and $f(x)\in F[x]$. Prove that $f(x)$ has a zero of multiplicity greater than one in some extension field $E$ if and only if $f$ and $f'$ have a common factor in $F[x]$.

Defintion.Field extensions generated by subsets and Simple Extensions

Suppose that $E$ is a field extension of $F$ and $S\subset E$.

1. We'll use the notation $F(S)$ to represent the smallest subfield of $E$ that contains both $F$ and $S$.
2. If $S=\{a\}$ then we call $F(a)$ a simple extension.

Problem 69 (Showing The Existence of a Field Extension Generated by a subset)

Suppose that $E$ is an extension field of the field $F$. Let $S$ be a subset of $E$.

1. Prove that there is a subfield of $E$ that contains both $F$ and $S$.
2. Prove that the intersection of all subfields of $E$ that contain both $F$ and $S$ is a subfield of $E$.

Problem 70 (Factoring By An Irreducible Gives A Simple Extension)

Let $F$ be a field and $p(x)\in F[x]$ be irreducible over $F$. If $a$ is a zero of $p(x)$ in some extension $E$ of $F$, then $F(a)$ is isomorphic to $F[x]/\left<p(x)\right>$. Furthermore, if $\deg p(x) = n$, then every member of $F(a)$ can be uniquely expressed in the form $c_{n-1}a^{n-1} + c_{n-2}a^{n-2} + \cdots + c_{1}a + c_{0}$ where $c_i\in F$. (In other words, the set $\left\{1, a, a^2, \ldots, a^{n-1}\right\}$ is a basis for $F(a)$ over $F$).

Problem 71 (Simple Extensions For The Same Polynomial Are Isomorphic)

Let $F$ be a field and let $p(x)\in F[x]$ be irreducible over $F$. If $a$ is a zero of $p(x)$ in some extension $E$ of $F$ and $b$ is a zero of $p(x)$ in some extension $E'$ of $F$, then the fields $F(a)$ and $F(b)$ are isomorphic.

In our proof that every nonzero, nonunit, in a PID can be written as a product of irreducibles, there was a part of our proof that all of you took for granted. The following problem has you complete the details.

Problem 72 (Ideals Generated By A Reducible Are Properly Contained By Non Unit Factors)

Prove that if $d$ is reducible and $d=ab$ where $a$ and $b$ are non units, then $\left<d\right>$ is a proper subset of $\left<a\right>$.

Problem 74 (Existence Of A Splitting Field)

Let $F$ be a field and $f(x)\in F[x]$ have positive degree. We have already shown that there exists an extension field $E$ of $F$ in which $f(x)$ has a zero $a$, in other words we can write $f(x) = (x-a)g(x)$ where $a,g(x)\in E[x]$ (by the Factor Theorem). Prove that there exists an extension field $E'$ of $F$ in which $f(x)$ can be written as a product of linear factors, i.e. we can write $f(x) = (x-a_1)(x-a_2)\cdots (x-a_n)g$ where $a_1,a_2,\ldots, a_n,g\in E'$ and also $g$ is a unit.

Definition.Splitting Field of $f(x)$ over $F$

Look this on up in the text

Problem 73 (Unique Factorization In A PID)

Suppose that $D$ is a principal ideal domain. Suppose that $f=p_1p_2\cdots p_m = q_1q_2\cdots q_n,$ where each $p_i$ and $q_i$ is irreducible over $D$. Prove that $n=m$ and after rearranging, for each $i$ we have $p_i=u_iq_i$ for some unit $i$. In other words, prove that $D$ uniquely factors as a product of irreducibles.

We have now shown that in every principle ideal domain, every nonzero nonunit can be written as a product of irreducibles (we'll call this a factorization), and that any two factorization are essentially the same (after rearrangement and multiplying by units). Any integral domain that satisfies this property is called a unique factorization domain.

Definition (Unique Factorization Domain)

Let $D$ be an integral domain. We say that $D$ is a unique factorization domain if the following two properties hold.

1. If $d\in D$ is not a unit, and not zero, then we can write $d$ as a product of irreducibles over $D$.
2. If we have written $d$ as a product of irreducibles over $D$ in two ways, say $d=p_1p_2\cdots p_n$ and $d=q_1q_2\cdots q_m$, then $n=m$ and after rearranging we have for each $i$ that $p_i=u_iq_i$ for some unit $u_i$.

The next problem should follow immediately from a fact that we have already shown.

Problem 75 (Polynomial Rings Over A Field Are Unique Factorization Domains)

Prove that $F[x]$ is a unique factorization domain if $F$ is a field.

What was the key that made this all work? What is the key to proving that $F[x]$ is a principle ideal domain? The key is the Division Algorithm, which is also called the Euclidean Algorithm. If an integral domain has something similar to the division algorithm, then we'll call it a Euclidean domain.

Definition.Euclidean Domain

Please look this one up the book.

Take a look at the proof we used to show that $F[x]$ is a PID whenever $F$ is a field. The key to this proof was the division algorithm. You should be able to generalize this proof to show that any Euclidean domain is a principle ideal domain.

Problem 76 (Euclidean Domains Are PIDs)

Prove that a Euclidean domain is a principle ideal domain. Prove also that a Euclidean domain is a unique factorization domain.

Problem 77 (Both Z And FX Are Euclidean Domains)

Prove that $Z$ is a Euclidean domain with function $d(a)=|a|$. Prove that $F[x]$ is a Euclidean domain for a field $F$ with $d(f(x))=\deg f(x)$.

Problem 78 (The Gaussian Integers Is A Euclidean Domain)

Prove that $Z[i]$ is a Euclidean domain, using the function $d(a+bi)=a^2+b^2$.

Problem 79 (In A Euclidean Domain All Units Have The Same Measure)

Suppose $D$ is a Euclidean domain with measure $d$. Let $u$ be a unit. Prove that that $d(u)=d(1)$, in other words prove that all units must have the exact same measure.

Problem 80 (In A Euclidean Domain Associates Have The Same Measure)

Suppose $D$ is a Euclidean domain with measure $d$. Suppose that $a$ and $b$ are nonzero associates, in other words assume that $a=ub$ for some unit $u$. Prove that $d(a)=d(b)$.

Problem 81 (Describing the Extension Field $\mathbb{Q}(\pi)$ of $\mathbb{Q}$)

Consider the field $\mathbb{Q}$ and the element $\pi$. It is known that the element $\pi$ is not the zero of any polynomial in $\mathbb{Q}[x]$. However, we also know that $\pi\in \mathbb{R}$, which is an extension field of $\mathbb{Q}$. This means we can talk about $\mathbb{Q}(\pi)$, the smallest subfield of $\mathbb{R}$ that contains both $\mathbb{Q}$ and $\pi$. Describe the elements of $\mathbb{Q}$ in a constructive way. In other words, give a way to obtain all elements of $\mathbb{Q}(\pi)$ by giving a way to describe any element of this field.

The derivative of a polynomial can help us understand the next two problems.

Problem 82 (Irreducibles Over A Field Of Characteristic Zero Have No Repeated Zeros)

Let $F$ be a field of characteristic zero and $f(x)\in F[x]$ be irreducible over $F$. Suppose that $E$ is a splitting field for $f(x)$, so that we can write $f(x) = c(x-a_1)(x-a_2)\cdots(x-a_n)$ for $c\in F$ and $a_1, \ldots, a_n\in E$. Show that $a_i\neq a_j$ if $i\neq j$, in other words show that $f$ has no zero of multiplicity greater than one.

Problem 83 (Irreducibles Over A Field Of Characteristic $p$ May Have Repeated Zeros)

Let $F$ be a field of characteristic $p$ and $f(x)\in F[x]$ be irreducible over $F$. Suppose that $E$ is a splitting field for $f(x)$, so that we can write $f(x) = c(x-a_1)(x-a_2)\cdots(x-a_n)$ for $c\in F$ and $a_1, \ldots, a_n\in E$.

1. Show that $f(x)$ might have a zero with multiplicity greater than one (give an example of such a polynomial).
2. If $f(x)$ has a multiple zero, then what can we say about the coefficients of $f(x)$?

Problem 84

Prove that the dimension of a vector space is well defined. In other words, prove that if $A =\{a_1,\ldots,a_n\}$ and $B=\{b_1,\ldots,b_m\}$ are two bases for a vector space $V$ over $F$, then we must have $m=n$.

Problem 85

Let $E$ be an extension field of $F$. Let $a,b\in E$. Prove that $F(a)(b)=F(a,b)$.

Definition.Degree Of A Field Extension

We defined $ [E:F] $ to be the dimension of $E$ as a vector space over $F$. When we see $ [E:F]=n $, we'll say, "The degree of $E$ over $F$ is $n$." We say that $E$ is a finite field extension of $F$ if $ [E:F] $ is finite.

Problem 86

Suppose that $K$ is a finite field extension of the field $E$, and $E$ is a finite field extension of the field $F$. Prove that $ [K:F] = [K:E] [E:F] $.

Definition.Splitting Field

Let $E$ be an extension field of $F$ and $f(x)\in F[x]$. We say that $F[x]$ splits in $E$ if $f(x)$ can be factored as a product of linear factors in $E[x]$. A splitting field for $f(x)$ over $F$ is a field extension $E$ of $F$ in which $f(x)$ splits in $E$ but $f(x)$ does not split in any other proper subfield of $E$.

Problem 87

Suppose $f(x)\in F[x]$ where $F$ is a field. Let $E$ and $E'$ be two splitting fields for $f(x)$ over $F$. Prove that $E$ and $E'$ are isomorphic.

Defintion.Perfect Field

We say that $F$ is a perfect field if every irreducible polynomial $p(x)$ over $F$ has no zeros of multiplicity greater than one.

Problem 88

Show that a field $F$ is perfect if and only if either (1) we know $F$ has characteristic zero or (2) we know $F$ has characteristic $p$ and $F=F^p$, where $F^p=\{a^p\mid a\in F\}$. In other words, a field is perfect if an only if it has characteristic zero or every element has a $p$th root where $p$ is the characteristic of $F$.

Problem.Finite Fields Are Perfect 89

Suppose that $F$ is a finite field with characteristic $p$. Prove that $F$ is a perfect field.

Problem. 90

Let $p(x)$ be irreducible over a field $F$, and let $E$ be a splitting field for $p(x)$. Suppose that $a$ is zero of $p(x)$ of multiplicity $k$. Prove that if $b$ is a zero of $p(x)$, then $b$ must have multiplicity $k$ as well. In other words, we can write $$p(x) = (x-a_1)^k(x-a_2)^k\cdots (x-a_j)^k$$ where $a_1,\ldots,a_j$ are the zeros of $p(x)$ and $k$ is the common multiplicity.

Problem.A Polynomial Ring over a UFD is a UFD 91

If $D$ is a unique factorization domain, prove that $D[x]$ is a unique factorization domain.

Definition.Algebraic and Transcendental Extensions

Let $E$ be an extension field of the field $F$. Let $a\in E$.

• We say that $a$ is algebraic over $F$ if $a$ is the zero of some nonzero polynomial in $F[x]$. Otherwise we say $a$ is transcendental over $F$.
• An extension $E$ is called an algebraic extension of $F$ if every element of $E$ is algebraic over $F$. Otherwise we say $E$ is a transcendental extension of $F$.

Problem 92

Suppose that $E$ is a field extension of $F$, and let $a\in E$.

1. If $a$ is algebraic over $F$, prove that $F(a)\approx F[x]/\left<p(x)\right>$ where $p(x)$ is a polynomial in $F[x]$ of minimal degree such that $p(a)=0$.
2. If $a$ is transcendental over $F$, prove that $F(a)\approx F(x)$, where $F(x)$ is the field of fraction of the integral domain $F[x]$.

You may assume in your work that the map $\phi:F(x)\to F(a)$ defined by $\phi(f(x))=f(a)$ is a ring homomorphism.

Problem 93

Suppose that $a$ is algebraic over a field $F$. Prove that there exists a unique monic polynomial $p(x)\in F[x]$ of minimal degree such that $p(a)=0$, and prove that $p(x)$ is irreducible over $F$.

We call the polynomial $p(x)$ above the minimal polynomial for $a$ over $F$. The degree of an algebraic element $a$ over $F$ is the degree of the minimal polynomial for $a$ over $F$.

Problem 94

Suppose that $a$ is algebraic over $F$ and the minimal polynomial for $a$ over $F$ is $p(x)$. Suppose that $f(x)\in F[x]$ has the property that $f(a)=0$. Prove that $f(x)=p(x)q(x)$ for some $q(x)\in F[x]$, in other words prove that the minimal polynomial for $a$ over $F$ divides every polynomial in $F[x]$ that has $a$ as a zero.

Problem.Finite Extensions Are Algebraic 95

Suppose that $E$ is a field extension of $F$ and that $ [E:F]=n$ is finite. Prove that $E$ is an algebraic extension of $F$.

Problem.Not Every Algebraic Extension is Finite 96

Construct an example of an algebraic extension $E$ over a field $F$ that is not a finite extension, and prove your claims. See exercise 3 on page 378 if you need a jump start (it gives you an example and lets you prove the claims).

Problem 97

Show that $\mathbb{Q}(\sqrt2,\sqrt3) = \mathbb{Q}(\sqrt2+\sqrt3)$. In particular, explain how to obtain the minimal polynomial for $(\sqrt2+\sqrt3)$ over $\mathbb{Q}$.

Problem.Every Finite Extension Is A Simple Extension When The Characteristic Is Zero 98

Suppose that $F$ a field of characteristic 0, and let $a$ and $b$ be algebraic over $F$. Prove that there exists $c\in F(a,b)$ such that $F(a,b)=F(c)$.

Problem 99

Suppose that $ [E:\mathbb{Q}]=2$. Prove that there exists an integer $d$ such that $\mathbb{Q}(\sqrt{d})=E$ and $d$ is not divisible by the square of any prime.

Problem 100

Find the degree and a basis for $E=Q(\sqrt 2, \sqrt[3]{2},\sqrt[4]{2})$ over $\mathbb{Q}$. Then find an element $c\in E$ so that $Q(c) = E$. What is the minimal polynomial for the $c$ you chose?

Problem.An Algebraic Extension of An Algebraic Extension Is Algebraic 101

Suppose that $K$ is an algebraic extension of $E$, and suppose that $E$ is an algebraic extension of $F$. Prove that $K$ is an algebraic extension of $F$.

Problem.102

Suppose that $K$ is an extension field of $F$. Let $E$ be the set of all elements of $K$ that are algebraic over $F$ which means we must have $F\subseteq E\subseteq K$. Prove that $E$ is a field. In other words, we are showing that the set of elements that are algebraic over $F$ is a field extension of $F$.

Definition.Algebraically Closed

We say a field $F$ is algebraically if the field has no proper algebraic extensions.

Problem 103

Prove that a field is algebraically closed if and only if every polynomial $f(x)\in F[x]$ splits in $F$. In other words, a field is algebraically closed if and only if it contains the zeros of every polynomial in $F[x]$.

Problem 104

Prove that $\mathbb{C}$ is algebraically closed.

Problem.Existence Of A Field Of Order $p^n$ 105

Pick a prime $p$ and a positive integer $n$ and consider the polynomial $f(x)= x^{p^n}-x\in \mathbb{Z}_p[x]$. Prove that the splitting field for $f(x)$ over $\mathbb{Z}_p$ is precisely the set of zeros of $f(x)$, which means $E$ has $p^n$ elements. Here are some hints.

• Show that $f(x)$ has no multiple zeros by looking at $f'$.
• Show that the set of zeros of $f(x)$ is closed under addition, subtraction, multiplication, and division by nonzero elements.

Problem.Uniqueness Of A Field Of Order $p^n$

Suppose that $K$ is a field of order $p^n$. Prove that $K$ is isomorphic to the splitting field for $f(x) = x^{p^n}-x$ over $\mathbb{Z}_p$.

We have now shown that any finite field must have order $p^n$ and must be isomorphic to the splitting field for $f(x) = x^{p^n}-x$ over $\mathbb{Z}_p$. This field is called the Galois Field of order $p^n$ and written $GF(p^n)$.

Problem.The Multiplicative Group Of Finite Field Is Cyclic 106

Suppose that $F = GF(p^n)$. Prove that the multiplicative group $F^*$ is cyclic.

Problem.A Finite Extension Of A Finite Field Is Simple 107

Suppose $F$ is a finite field and suppose that $E$ is a finite extension of $F$. Prove that $E=F(a)$ for some $a\in E$.

If $F$ is a perfect field, then is it true that any finite extension is always a simple extension? We know this is true if $F$ has characteristic zero, or if $F$ is finite with characteristic $p$. What if $F$ is an infinite perfect field with characteristic $p$? If you are interested in reading more on this topic, do a google search on separable extensions.

Problem 108

Let $F$ be a field. Prove that there exists an algebraic extension $E$ of $F$ that is algebraically closed.

For more problems, see AllProblems