http://www.math.csusb.edu/notes/cgi/contents.cgi

http://www.math.niu.edu/~beachy/aaol/contents.html#index

1. Def: A set A along with at least one binary operation written (A,*) where * is the binary operation is called an Algebraic Structure. Examples of algebraic structures (N,+), (N,x), (W,+), (W,x), (Z,+), (Z,x), (Z,+,x), (Q,+), (Q,x), (Q^*,x) and some properties of the structures: Commutative law for +, for x, Associative law for +, for x, the Identity property for + (0 in (W,+), (Z,+), (Q,+)) and for x (1 in (N,x), (W,x), (Z,x), (Q,x) and (Q^*,x)): the Inverse property in (Z,+) and (Q,+) every element has an additive inverse, in (Q^*,x) every element has a multiplicative inverse. Although (N,x) and (W,+) are both algebraic structures with associative, commutative binary operations and both satisfy the identity property these two structures are different algebraically: In (Z,+,x) the operation x distributes over the operation +

· Definitions. A binary operation on a set A is a function from AXA to A. If * is a binary operation on A we write *((a,b)) = a*b. If (A,*) is an algebraic structure then * is said to be associative provided the following statement is true (TFSIT): For all a,b,c ÎA, (a*b)*c = a*(b*c). In this case we write a*b*c unambiguously. If (A,*) is an algebraic structure then * is said to be commutative provided TFSIT): For all a,b ÎA, a*b = b*a. If (A,*) is an algebraic structure then (A,*) has an identity with respect to * provided TFSIT: There exists an element eÎA so that for all aÎA, a*e = a and e*a = a.

Creating binary operations with specific properties on A = {a,b} and on A = {a,b,c}.

HW:

q Is the operation of subtraction on the set of all integers (a) commutative? (b) associative? In each case explain your answer.

q Show that division by non-zero elements is right distributive, but not left distributive over addition in the set of rational numbers.

q For the set of integers, define the operation * as follows: a*b = a + b – ab where and b are any integers and + and - are the usual addition and subtraction and ab is the usual product of integers. Find the identity element in the set relative to this operation. Let n be an arbitrary integer and find the inverse of n relative to the operation *.

http://www.math.csusb.edu/notes/cgi/contents.cgi

http://www.math.niu.edu/~beachy/aaol/contents.html#index

2. Define left and right distributivity. Prove that various algebraic structures have or do not have an identity. In (Z,+), 0 is an identity and 3 + x = 0 is solvable. The solution is called the (additive) inverse of 3 and we know it by the name -3.

Definitions. Let (A,*) be an algebraic structure with identity e. An element aÎA has an inverse (or -*inverse) in A (with respect to *) provided TFSIT: There exists an element xÎA so that a*x = e and x*a=e. We denote the inverse of a by the symbol a ^–1. We say the structure (A,*) with identity satisfies THE INVERSE PROPERTY provided every element of A has an inverse. Let (A,*) be an algebraic structure and let SÍA. The set S is closed (with respect to * ) provided TFSIT: If s, tÎS then s*tÎS.

EXAMPLES. The additive inverse of 3 in (Z,+ ) is 3 ^–1 which we denote by –3. The multiplicative inverse of 3 in (Q,x) is 3 ^–1 which we denote by 1/3 and which is also called the reciprocal of 3. The algebraic structure (Q*,x) has identity 1 and satisfies THE INVERSE PROPERTY. The set of odd numbers is not closed in (Z,+). The set of odd numbers is closed in (Z,x). Let S={nÎZ|GCD(n,100)=20}. S is not closed in (Z,+) and S is not closed in (Z,x).

The abstract case of the 8x8 table defined algebraic structure.

HW:

q Let subtraction be defined by a-b=c means c is an element of the set and a = b+c. Determine whether each set below is closed with respect to subtraction.

a) the set of all integers

b) the set of positive integers

c) the set of all integers which are divisible by three

d) In each case explain your answer.

q For the set of rational numbers, we define two binary operations $ and # (in terms of ordinary arithmetic operations) as follows: a $ b = 2ab and a#b = a + 2b for any two rational numbers a and b.

a) Is $ commutative? If so, explain your answer and if not, give a counter example.

b) Is # commutative? If so, explain your answer and if not, give a counter example.

c) Prove or disprove that $ is associative.

d) Prove or disprove that # is associative.

e) Prove or disprove that $ is left distributive over #.

f) Prove or disprove that # is left distributive over $.

http://www.math.csusb.edu/notes/cgi/contents.cgi

http://www.math.niu.edu/~beachy/aaol/contents.html#index

3. Laboratory One with Mrs. Buracker. Topics included Place Value, Order of Operations, Integers, One step equations and operations on whole numbers using various games, manipulatives and models accessible to middle school students.

4. Discuss form of proof. Example. Define # on Q by (p/q)#(s/t) = ps/t where each of p/q and s/t are in reduced form and ps/t is expressed in reduced form. Can you solve (a/b)#X = (c/d) for all choices of a/b and c/d in reduced form? Suppose X = p/q is a solution. Then (ap)/q = c/d. This is easily solvable for p/q as the reduced form of c/(ad) for all choices of a/b except for a = 0. So the answer is yes it is solvable as long as a is unequal to 0. For homework see if you can solve X#(a/b) = (c/d) for all choices of a/b and c/d in reduced form.

· Definitions. A matrix is a rectangular array of objects. Each object’s position in the array is uniquely determined by its row (®) location and its column (¯) location. If a matrix has m rows and n columns we say it is an m by n matrix. Let A be such a matrix then we denote A by [a_ij] where i = 1,2,3,…,m and j = 1,2,3,…,n and a_ij denotes the entry in position (i,j) where i and j denote, respectively, the row and column locations. Let S denote an algebraic structure (S,*). An m by n matrix where each a_ijÎS is called an m by n matrix over S. The set of all m by n matrices over S is denoted by M_m,n(S). Let A = [a_ij] and B = [b_ij] be elements of M_m,n(S). We extend * a binary operation of S to a binary operation on M_m,n(S) by the following.

AB = C = [c_ij] where c_ij = a_ij * b_ij for i = 1,2,3,…,m and j = 1,2,3,…,n. This is called the pointwise extension of *. (M_m,n(S), ) is an algebraic structure and shares some of the properties of (S,*). Two matrices A and B in M_m,n(S) are equal provided TFSIT a_ij = b_ij for all i = 1,2,3,…,m and j = 1,2,3,…,n. Matrices and systems of equations motivate the following definition. Let A be an m by n matrix over Q and let B be an m by t matrix over Q. The product matrix AB = C =[c_ij] where c_ij = a_i1 * b_1j + a_i2 * b_2j + a_i3 * b_3j + … + a_im * b_mj for i = 1,2,3, …, m and j = 1,2,3,…,t. This multiplication takes the m elements in A from row i (®) and multiplies each by the corresponding m elements in B from column j (¯) and adds these products together to get c_i,j producing the m by t matrix C.

HW:

q Given the matrices find (a) A+B, (b) AB, (c) BA, (d) 5A, (e) A-B, (f) B-A.

q Given the matrices find (a) X(YZ), (b) (XY)Z, (c) X(Y+Z), (d) XY + XZ, (e) (X+Y)Z, (f) XZ + YZ

q Find a nonzero divisor of zero in M the set of all 2x2 matrices with integer entries.

q Let E be the set of all English words and let S be the set of all “letter strings” [finite lists of letters, possibly repeated] of our alphabet. Notice that E is a subset of S. In each instance below a process * that makes sense on each of these two sets is described. [The Greek letters a and b represent arbitrary elements of these sets.] Answer each of the following questions for each exercise:

1. Give two more examples to show how * works.

2. Is * a binary operation on S? on E? Justify each answer with a reason or counterexample.

3. If * is a binary operation on the set, say whether * is associative and/or commutative, supporting your answers with reasons or counterexamples.

a) a*b is formed by putting a and b next to each other, forming a single string. For example, moon*glow = moonglow.

[This is like the password process used by CompuServe and other electronic services.]

b) a*b is the word or string that in alphabetical order comes first. For example, trip*trap = trap.

[This is a basic part of any word-sorting algorithm.]

c) a*b is the string of letters, including repeated letters, that are common to a and b, arranged in alphabetical order. For example, beaker*knee = eek.

d) a*b is the number of letters in the longer word or string, or if they have the same number of letters, it’s that number. For example, movie*theater = 7.

http://www.math.csusb.edu/notes/cgi/contents.cgi

http://www.math.niu.edu/~beachy/aaol/contents.html#index

5. Retraction #1 from day 2.

· Definitions. A group is an algebraic structure (G, ¨) in which the following properties hold.

(1) ¨ is associative. [For all x, y, z in G, x¨ (y¨z) = (x¨y) ¨z.]

(2) There is an identity in G. [There exists an element e in G so that for all x in G, e¨x=x and x¨e=x.]

(3) (G, ¨) satisfies the inverse property. [ For every x in G there exists an element in G such that ¨x=e and x¨=e. The element is called the inverse of x.]

Examples: (Z,+) is a group.

(N,+) is not a group because property (2) fails to hold.

(Q,+) is a group.

(W,+) is not a group because property (3) fails to hold.

(M_m,n(Z),+) is a group.

(M_2,2(Z),x) is not a group because property (3) does not hold.

(Q*,x) is a group.

(Q,x) is not a group because the element 0 does not have an inverse element.

· Theorems

1. For any elements a, x and y in a group G, if a¨x = a¨y then x = y.

2. For any elements a, x and y in a group G, if x¨a = y¨a then x = y.

3. For any elements a and b in a group G, the equation a¨x = b has one and only one solution (for x) in G.

4. For any elements a and b in a group G, the equation x¨a = b has one and only one solution (for x) in G.

The proof of Theorem 1. is motivated by scratch paper work. [Assume x = y and try to rewrite each of x and y using the group properties and try to introduce a factor of a to the left of each of x and y.]

A proof of Theorem 1. Let a, x and y be elements of G. Assume a¨x = a¨y. Since G is a group and a is an element of G, by property (3) there is an inverse for a in G, namely . Also since ¨is a binary operation it follows that ¨(a¨x)= ¨(a¨y). The associative law guarantees that (¨a)¨x =(¨a)¨y so e¨x=e¨y by property (3). Finally, x=e¨x=e¨y=y by property (2).

The proof of Theorem 3. is motivated by scratch paper. [Assume there is an element x in G so that a¨x = b. Solve for x using Theorem 1 by rewriting b with a factor of a on the left. a¨x=b=e¨b=(a¨)¨b and Theorem 1 gives x =¨b.]

A proof of Theorem 2. Let a and b be elements of G. Since G is a group, the element a has inverse and the element ¨b is an element of G. Now, a¨(¨b) = (a¨)¨b by the associative law and (a¨)¨b = e¨b = b by properties (3) and (2) respectively. Therefore the element x = ¨b is a solution to the equation a¨x=b for any a and b in G. Suppose y were any other solution to the equation. Then a¨x = b = a¨y so a¨x = a¨y and Theorem 1. implies x = y. So, there is only one solution to the equation and it is ¨b

HW:

q Prove Theorems 2,4

q The converse of theorem 1 is: For any elements a,x and y in a group G, if x = y then a¨x = a¨y.

a) Does this require proof as a result in group theory? Why or why not? (Hint: consider the definition of a binary operation and use this in your discussion.)

b) Euclid stated this same idea by saying “If equals are multiplied by equals, the results are equal.” Discuss the appropriateness of saying “multiply both sides of an equation by the same thing” or “multiply one equation by another” in the context of Group theory.

q Discuss what each of theorems 1-4 says about elements of (a) the integers and (b) the rational numbers in the context of the kinds of equations with (a) integer and (b) rational number coefficients that are guaranteed to have unique solutions for x.

http://www.math.csusb.edu/notes/cgi/contents.cgi

http://www.math.niu.edu/~beachy/aaol/contents.html#index

6. Show how to prove the uniqueness of an object. Rework the material from Theorems 2 and 4.

· Theorems

5. In any group G, there is only one identity.

6. In any group G, for each element x in G, there is only one inverse element

A proof of Theorem 5. Let e and f be identities in a group G. By the identity property we know that e¨g=g¨e=g for all elements g in G. In particular, since f is in G we have that e¨f = f. Similarly, since f is an identity in G, f¨g=g¨f=g for all elements g in G. So e¨f = e. Therefore we have e = e¨f = f. So the identity of G is unique.

A proof of Theorem 6. Let x be an element in G. We know is an element of G and x¨=e. Thus the element is a solution to the equation x¨y = e and by Theorem 3, there is only one solution to this equation and so is the only inverse for the element x.

More examples of Groups.

S₃ as the group of symmetries of an equilateral triangle using mappings to represent the symmetries.

Z₃, Z₆ and Z₇ with addition

Renaming the elements of Z₃

The symmetries of a rectangle

S₄ as a collection of mappings and an example of a permutation group

· Definition. A permutation of {1,2,3,4} is a mapping (function) with domain {1,2,3,4} and range {1,2,3,4} so it is a one-to-one mapping (recall from M107)

HW:

q Given the permutations find (a) ab, (b) ba, (c) a ^-1, (d) (ab)g, (e) a(bg), (f) the solution to ax = b, (g) the solution to bx = g.

q Write out each element of S₃. Label the identity as r₁ and each of the other elements as r₂, r₂, r₃, r₄, r₅, r₆. Fill out the complete “Multiplication Table” for S₃ using your elements as labeled.

q Consider the Subset A₃ of S₃ as follows: . Show that A₃ is closed for the operation of multiplication and that each element in A₃ has a multiplicative inverse in A₃.

http://www.math.csusb.edu/notes/cgi/contents.cgi

http://www.math.niu.edu/~beachy/aaol/contents.html#index

7. Definition. A Cayley table is a table that defines a binary operation on a set.

EXAMPLES. The tables for (Z₆,+) and Z₇,+) were Cayley tables for the respective groups.

The Cayley tables for (Z₆,´) and Z₇, ´) do not define groups.

NOTATION:

Let (G,à)be a group and let x and y be elements of G. Denote xày by xy.

Denote by x ^–1 .

· Definitions. Let (G, à) be a group and let x be an element of G. x⁰ is defined to be e, so x⁰ = e.

x¹ is defined to be x so x¹ = x. For any natural number k>1, x^k is defined to be xàxà … àx where there are k terms so x^k = xxx …x with k factors. x ^-k is defined to be x ^-1x ^-1x ^-1 … x ^-1 where there are k factors so x ^–k = (x ^-1) ^k.

HW:

q Factor 3 in two different ways in Z₆. Can 5 be factored into factors in Z₆ other than by using 1 as a factor?

q Find two equations of the form ax = b, with a and b in Z₆ and with b ¹ 1, which cannot be solved in Z₆.

q Let the following table define a binary operation on the set {2,4,6,8}

*	2	4	6	8
2	4	8	2	6
4	8	6	4	2
6	2	4	6	8
8	6	2	8	4

Answer each exercise below in reference to *

a) Determine 4*8

b) Which element, if any, is the identity?

c) Which element, if any, is the inverse of 8?

· Theorems.

7. In any group G, the identity is its own inverse.

8. For any elements x and y in a group G, (xy) ^–1 = y ^–1x ^–1.

9. For any element x in a group G, (x ^–1) ^–1 = x .

A proof of Theorem 8. The steps in this proof are motivated by the work done on scratch paper where we make an assumption and follow it out, hoping to discover something that is known to be true and from which we can backtrack to find our proof.

Let x and y be elements of a group G. Then xy and (xy) ^–1 are also both group elements and (xy)(xy) ^–1 = e by the property of inverse elements. So, using the associative law and the property of inverse elements x(y(xy) ^–1) = xx ^–1 and from Theorem 1 and the identity property it follows that y(xy) ^–1 = x ^–1 = ex ^–1. Again, using the associative property and the property of inverses y(xy) ^–1 = y(y ^–1x ^–1) and from Theorem 1 again (xy) ^–1 = y ^–1x ^–1 .

HW:

q Fill in the table below so that you create a binary operation on the set {a,b,c,d} with the following three properties:

i. c is the identity element,

ii. b is the inverse of d, and

iii. the operation is commutative.

*	a	b	c	d
a
b
c
d

q Prove Theorems 7,9 and 10

QUIZ1 TAKE HOME DUE IN ONE WEEK.

http://www.math.csusb.edu/notes/cgi/contents.cgi

http://www.math.niu.edu/~beachy/aaol/contents.html#index

8. The Principle of Mathematical Induction (PMI).

Let S be a subset of the natural numbers N. The set S = N if and only if TFSAT (1) 1 is in S and (2) if k is in S then k+1 is in S.

Let n be a natural number variable and let P(n) be an open sentence in n. Let S = {xÎN|P(x) is true}. S is called the truth set for P(n). The statement “for all n in N, P(n) is true” is true provided S = N and you may use the PMI to prove statements of this type. The statement “there exists an element n in N , P(n) is true” is true provided S¹F.

· Theorems

10. Let a and b be elements of an arbitrary group G, and let m be a natural number. Then, for any natural number n,

a) eⁿ = e where e is the identity of G.

b) For any a and b in G, (ab)ⁿ = aⁿbⁿ if and only if ab=ba.

c) a^m+n = a^m aⁿ.

d) (a^m)ⁿ = a^mn = (aⁿ)^m.

A proof of the (PMI)

® If S = N then obviously 1 is in S and if k is in S and 1 is in S then k+1 is in S by closure of addition in N=S.

¬ If 1 is in S then by property (2) 1+1=2 is in S. Let n be in N and larger than 1. Then

n=1+1+…+1 with n summands. Using the associative law, n=(1+ …+1)+1 with n-1 summands grouped. Continuing the process to n=((1+…+1)+1)+1 with n-2 summands grouped until you get n=(…(((1+1)+1)+1)…+1)+1. Now working from the inside out, 1+1=2 is in S and so 2+1=3 is in S until you get (n-1)+1=n is in S. Therefore S=N.

Proofs of parts of Theorem 10.

(a) Let S = {xÎN| e^x = e}. It is necessary to prove that S=N. By definition of exponents, g¹ = g for any g in G. In particular, e is in G and so e¹ = e. Therefore 1 is in S. Suppose k is in S. This means e^k = e. Calculate e^k+1 using the definition. e^k+1 = ee …e with k+1 factors. By the associative law parentheses may be inserted at any point along this product. Since e^k = e and e^k = ee…e with k factors the association e^k+1 = (ee…e)e = e^ke = ee = e places k+1 in S. Therefore, by the PMI S = N.

(c) Let aÎG, mÎN and S = {xÎN| a^m+x = a^m a^x}. It is necessary to prove that S = N. By the definition of exponents a^m+1 = aa…a with m+1 factors. Using the associative law a^m+1=(aa…a)a=a^ma=a^ma¹. So 1ÎS. Suppose kÎS, so a^m+k = a^ma^k. Now, a^m+(k+1)=a^(m+k)+1=(a^ma^k)a=a^m(a^ka)=a^ma^k+1 and so k+1ÎS. Therefore, by the PMI S=N.

HW:

No New homework. Reprove Theorem 9 from last time, prove theorem 10 part (d) and work on the take home exam.

http://www.math.csusb.edu/notes/cgi/contents.cgi

http://www.math.niu.edu/~beachy/aaol/contents.html#index

9. The well ordering principle states that every non empty subset of the whole numbers must have a smallest element. Let S be a nonempty subset of N, the set of natural numbers. By the well ordering principle, S has smallest element.

· Definitions. Let (G,*) be a group. If the set G has a finite number of elements then we say that G is a finite group and we write the order of G is |G| where |G| is the number of elements in the set G. So, the notation |G| = n means the set G has n elements in it. If the set G is infinite then we say G is an infinite group and we write |G| = ¥ to denote that the order of G is infinite. Let g be an element of the group G with identity e and let S = {kÎN| g^k = e}. If the set S is empty we say that the element g has infinite order and write this as |g| = ¥. If the set S is nonempty then by the well ordering principle S has a least element we will denote by n. In this case we say that the element g has order n and write this as |g|=n. Let (G,*). A subset H of the group G is called a subgroup of G provided (H,*) is a group.

Examples: Find the orders of the elements in Z₆ and in the group of order eight given by the following table.

*	a	b	c	d	e	f	g	h
a	a	b	c	d	e	f	g	h
b	b	c	d	a	f	g	h	e
c	c	d	a	b	g	h	e	f
d	d	a	b	c	h	e	f	g
e	e	h	g	f	a	d	c	b
f	f	e	h	f	b	a	d	c
g	g	f	e	h	c	b	a	d
h	h	g	f	e	d	c	b	a

Find subgroups in the group given by the table above.

· Theorem

11. If H is any subgroup of a group G, then the identity element of G is in H and is the identity element of H.

A proof of Theorem 11.

Let e be the identity of the group G, then eg = ge = g for all gÎG.

Let e’ be the identity of the subgroup H, then e’h = he’ = h for all hÎH.

Let h be any element of H. Since H is a subset of G the h is also an element of G.

h = eh = e’h and by Theorem 2 it follows that e = e’. Therefore, eÎH and is the identity for H.

HW:

q Prove that the set of even integers is a subgroup of the additive group of the integers.

q Find all subgroups of the symmetric group S₃.

q Find the order of each element in each group S₃ and Z₇ under addition.

http://www.math.csusb.edu/notes/cgi/contents.cgi

http://www.math.niu.edu/~beachy/aaol/contents.html#index

10. Review the homework on subgroups.

· Theorem

12. A subset H of a Group G is a subgroup if and only if:

a) H is not the empty set.

b) For every pair of elements a and b in H, the product ab ^–1 is an element of H.

A proof of Theorem 12.

(Þ) Suppose H is a subgroup of G. By Theorem 11 the identity e of G is in H and so H is non-empty. Let h and k be elements of the subgroup H. The element k^-1 is in H since H is a subgroup of G and so the element hk ^–1 is in H by closure. Therefore conditions a) and b) hold.

(Ü) Suppose a) H is non empty and b) if h and k are in H then hk^-1 is in H. Even though closure may not hold, the associative law holds for any three elements from H as it is inherited from G. Since H is non empty there is at least one element in H, call it x. Now, the pair of elements x and x, each in H and property b) ensure that xx ^–1 = e is in H. So H contains an identity. Let h be in H. The pair e and h, each in H and property b) ensure that eh ^–1 = h ^–1 is in H. Therefore, every element of H has an inverse. Let h and k be in H. Since k is in H, k ^–1 is in H and the pair h and k ^–1, each in H, and property b) ensure that

h(k ^–1)^–1 = hk is in H and so closure holds. Therefore H is a group with the same binary operation as in G and so H is a subgroup of G.

· Definitions: Let (G,*) be a group and let A and B be subsets of G. The set AB = {abÎG|aÎA and bÎB} is called the product of set A with set B. This product defines a binary operation on the power set of G and the operation is not commutative if and only if the operation of G is not commutative. Let A and B be sets. A mapping f from A to B is said to be a one to one correspondence from A to B provided TFSAT. (1) The range of f is the set B. (2) If (a,b) and (c,b) are in f then c = a [i.e. Each element of B is associated by f with exactly one element of A.]. Let A be a set and let C be a collection of subsets of A. [C is a subset of the power set of A.] C is called a partition of A provided TFSAT. (1) If a is an element of A then there exists H, a subset of A, such that HÎC and aÎH. (2) if H and K are elements of C then HÇK=F.

HW:

q If H and K are subgroups of G, prove that HÇK is also a subgroup of G.

http://www.math.csusb.edu/notes/cgi/contents.cgi

http://www.math.niu.edu/~beachy/aaol/contents.html#index

11. Laboratory Two with Mrs. Buracker. Topics included Modular Mathematics and modular designs, developing properties, modeling arithmetic properties using algeblocks and multiplying polynomials.

12.

· Definitions. Let G be a group with subgroup H and let g be an element of G. The set Hg={hgÎG|hÎH} is called a right coset of H in G. The set gH = {ghÎG|hÎH} is called a left coset of H in G. Let x and y be elements of G. We say x is congruent to y modulo H provided x and y are in the same coset of H in G.

· Theorems

13. If H is a subgroup of the group G and if a and b are elements of G, the following conditions are equivalent.

a) aÎ Hb b) Ha = Hb. c) ab ^-1ÎH

14. If H is a subgroup of G, the right cosets of H in G form a partition of G.

15. (LaGrange) If H is a subgroup of a finite group G, then the order of H is a divisor of the order of G.

A proof of Theorem 13. a)=>b) Suppose aÎHb. This means there is an element h in H so that a = hb. Let xÎHa. This means x = h’a for some h’ in H. So, x = h’a = h’(hb) = (h’h)bÎHb so HaÍHb. Similarly HbÍHa so Ha=Hb.

b)=>c) Suppose Ha=Hb. a = eaÎHa = Hb so a = hb for some h in H. Solving for h gives ab ^–1 = hÎH.

c)=>a) suppose ab ^–1 ÎH. Then ab ^–1 = h and solving for a gives a = hbÎHb.

A proof of Theorem 14. Let C ={SÍG| S=Hg for some gÎG}. Let aÎG. Since aÎHa=SÎ C there is S in C so that aÎS. Let Ha and Hb be elements of C. Suppose HaÇHb¹F and let xÎHaÇHb. There exist elements h and h’ in H so that x = ha = h’b. Solving ha = h’b for h’ gives (ha)b ^–1 = h’ or h(ab ^–1) = h’. Now solving for (ab ^–1) gives ab ^–1 = h ^–1h’ÎH. By theorem 14 it follows that Ha = Hb. So, if HaÇHb¹F the Ha = Hb. By the contrapositive, if Ha = SÎ C and Hb = TÎC and S¹T then SÇT=F Therefore the set C is a partition of G.

A proof of Theorem 15. Let G be a finite group with n elements and list the elements of G as e, g₁, g₂, …, g_n-1 . Let H be a subgroup of G having k elements and list the elements of H as e, h₁ , h₂, …, h_k-1. For any x in G, the coset Hx has k elements x, h₁x, h₂x, …, h_k-1x . These elements are all distinct because of right cancellation in G. Since the cosets of H in G form a partition of G, every element of G is in some coset of H in G and it follows that there is some number of cosets of H in G, say t of them, so that G = Hx₁ÈHx₂È Hx₃È…ÈHx_t where x₁, x₂, …, x_t are elements of G. Since the cosets of H in G form a partition of G the cosets in the union are all disjoint and each coset has k elements, |G| = |Hx₁|+|Hx₂|+…+|Hx_t| = k+k+…+k with t summands and so |G| = tk = t|H|.

HW:

q Prove theorems 13 and 14 for left cosets.

q Let G be the additive group Z₂₄. Let H be the subgroup H = { 0,6,12,18}. Determine whether each of the following statements is true or false.

a) 7º11 mod H b) 10º 5 mod H c) 13º19 mod H d) 3º15 mod H

q Let G and H be as above. For each of the following congruences, find three distinct values of x for which the congruence is true.

a) 7ºx mod H b) xº17 mod H c) xº12 mod H d) 10ºx mod H

q Consider the following information concerning groups W, X, Y, and Z.

Group W contains 22 elements.

Group X contains 23 elements.

Group Y contains 24 elemetns.

Group Z contains 25 elements.

Use LaGrange’s theorem to answer the following questions.

a) Which group has the most different sizes of possible subgroups, and which has the fewest?

b) What sizes of subgroups are possible in group W ? in Group Z ?

q Suppose G is a 50 element group.

a) What are the possible sizes for subgroups of G?

b) For each possible size, assume there is a subgroup of that size, and specify how many distinct cosets that subgroup has.

c) Answer a) and b) if the group has 55 elements.

13. No Class due to Assessment.

14. No class due to snow cancellation.

http://www.math.csusb.edu/notes/cgi/contents.cgi

http://www.math.niu.edu/~beachy/aaol/contents.html#index

15. Start Rings

· Definitions: A group (G,*) in which * is a commutative binary operation is called an Abelian group. A ring is an algebraic structure with two binary operations usually designated by + and ´ such that TFSAT (1) (R,+) is an Abelian group, (2) ´ is an associative binary operation, and (3) for all a,c,bÎR, a´(b + c) = a´b + a´c and (a+b)´c=a´c + b´c. A ring R that has a multiplicative identity is called a ring with unity and the multiplicative identity is called the unity and is usually denoted by 1. A ring R in which the operation ´ is commutative is called a commutative ring.

· Examples: Rings (Z,+,´), (Q,+, ´), (Â,+,´) (2Z,+, ´) are all rings. (W,+, ´) and the odd integers with + and ´ are both not rings. M_2x2(Z) with matrix addition and multiplication is a ring. [verify the associative and distributive laws over Z and demonstrate that M_2x2(R) where R is any ring is also a ring.] (Z₆,+, ´) and (Z₇,+, ´) and (Z_n,+, ´) are all rings with unity. 2Z has no unity. M_2x2(Z) is not commutative but has a unity. M_2x2(2Z) is non-commutative with no unity. M_2x2(Z₂) is a finite ring (16 elements) that is non-commutative and has a unity. If R and S are rings then (R´S,Å,Ä) is a ring where Å and Ä are defined componentwise.

· Theorems.

1. For any a,x,y in a ring R, if a+x = a+ y then x = y and if x+a = y+a then x = y.

2. There is only one additive identity in any ring. Each element of a ring has a unique additive inverse.

3. For any a, b in a ring R, the equation a + x = b has one and only one solution in R.

4. In any ring, ^- (x+y) = ^- x + ^- y.

A proof of Theorem 4. Let x and y be elements of R. By Theorem 8 from the group theory if a and b are elements of a group G then (ab) ^–1 = b^-1a ^–1. Since R is a ring, (R,+) is a group and so by the group theory theorem ^–(x+y) = ^-y + ^-x . Also, since R is a ring the group (R,+) is abelian and so it follows that

^–(x + y) = ^-y + ^-x = ^-x + ^-y.

HW:

q Find all solutions to the following equations in Z₇. (a) x – 3 = 6, (b) 5x = 4, (c) x² + 2x + 6 = 0, (d) x³ = 6, (e) 3x + 2 = 6.

q Solve the following equations in the ring of 2x2 matrices over the set of integers and check your solution.

q b)

q

q Explain why theorems 1-3 hold in the context of what you know about groups and the definition of a ring.

http://www.math.csusb.edu/notes/cgi/contents.cgi

http://www.math.niu.edu/~beachy/aaol/contents.html#index

16. Laboratory Three with Mrs. Buracker. Topics included Mod Math Designs, Modeling solving equations (SOL A.1), Properties of real numbers (SOL A.3), Modeling the Distributive Property (SOL A.3), Polynomials (SOL A.11), Matrices (SOL A.4) and a Lab assessment.

17.

· Definition: Let F be a commutative ring with unity 1. F is a field provided TFSIT. (F*,´) is an abelian group where F* = F\{0}. Let a,b ÎR a ring. The element a is called a left divisor of b provided TFSIT. There exists an element cÎR, c ¹ 0, such that ac=b. The element a is called a right divisor of b provided TFSIT. There exists an element dÎR, d ¹ 0, such that da=b. The element a is called a divisor of zero provided a is either a left or a right divisor of zero. Let D be a commutative ring with unity 1¹0. D is called an integral domain provided TFSIT. D has no non-zero divisors of zero.

· Examples: (Q,+,´) is a field. (Q,+,´) is an integral domain. (Z₇,+,´)is a field. (Z₇,+,´)is an integral domain. (Z,+,´) is an integral domain and it is not a field.

· Theorems

5. There is only one multiplicative identity in any field. Each non-zero element of a field has a unique multiplicative inverse.

6. For any nonzero a in a field F and any elements x and y in F, if ax = ay then x = y and if xa = ya then x = y.

7. For any nonzero a in a field F and any element b in F, the equation ax = b has one and only one solution in F.

8. In any field, if x and y are non-zero then (xy) ^–1 = x ^–1 y ^–1.

9. For any element a in a ring R, a0=0.

10. For any element in a ring R, 0a = 0.

11. In any field F, 0 ¹ 1.

12. In any field F, 0 has no multiplicative inverse.

A Proof of Theorem 9. Let a be an element of any ring R. a0 = a(0+0) since 0+0 = 0 by the identity property of 0. Now, a(0+0) = a0 + a0 by the distributive law. It follows that a0 = a0 + a0. Again by the identity property of 0, a0 = a0 + 0 so a0 + 0 = a0 + a0. By the left cancellation law in (R,+), 0 = a0.

A Proof of Theorem 11. Let F be a field then F has a unity 1. By definition (F*,´) forms a group. Thus F* is non-empty and the identity of the group F* is 1. So, 1 is in F* and 0 isn’t. Therefore 1¹0.

A Proof of Theorem12. Proof by contradiction. Suppose 0 has a multiplicative inverse x. By the property of a multiplicative inverse x0 = 1. This is a contradiction of Theorem 9, which is known to be true. Therefore, the supposition that 0 has a multiplicative inverse is leads to a contradiction and so it must be the case that 0 DOES NOT have a multiplicative inverse.

HW:

q Use arithmetic mod 6 to show that theorem 7 DOES NOT HOLD in every ring.

q Show that 3 and 4 have no multiplicative inverses in the set Z₆.

q Explain why theorems 5-7 hold in the context of what you know about groups and the definition of a ring.

q Prove Theorems 10, 15, 16 and 17.

q From arithmetic mod 7, find three examples to illustrate each of theorems 13, 14 and 17.

q Use arithmetic mod 6 to show that theorem 15 DOES NOT HOLD in every ring.

http://www.math.csusb.edu/notes/cgi/contents.cgi

http://www.math.niu.edu/~beachy/aaol/contents.html#index

18. More on rings.

· Notation. Let R be a ring and let n be a natural number greater than 1. For any element a of R, [n]a denotes a+a+…+a where there are n summands. (This is the additive notation for exponentiation as discussed in group theory where the operation was written as multiplication.) Since (R,+) is a group this notation can be extended to all elements n of the integers. For any non-zero element a of a ring R and any natural number n greater that 1 aⁿ denotes a product with n factors of a (just as in the group theory section). If R contains a unity 1 then we can extend this to a⁰ = 1, provided a ¹0. If F is a field and a ¹0 then (F*,´) is a group and so the notation extends to all integers.

· Theorems

13. For any elements a,b in a ring R, ^- ab = ^- (ab).

14. For any elements a,b in a ring R, ^- a ^– b = ab.

15. For any nonzero a in a field F and any elements b and c in F, the equation ax + b = c has one an only one solution in F.

16. For all a,b,c,d,e,f in a field F, if ae + ^- (bd) ¹ 0 then the system of equations given by ax + by = c AND dx + ey = f has one and only one solution .

17. For any a, c in a field F and for any nonzero b,d in F, (ab ^–1)(cd ^–1) = (ac)(bd)^–1.

18. Let a and b be elements of an arbitrary ring R, and let m be a natural number. Then, for any natural number n,

a) [n]0 = 0 (0ÎR is the zero of R) and 1ⁿ = 1 (the latter assuming R has a unity 1).

b) For any a and b in R, [n](a + b) = [n]a + [n]b and (ab)ⁿ = aⁿbⁿ (the latter if an only if ab=ba).

c) [m + n]a = [m]a + [n]a and a^m+n = a^mbⁿ.

d) [nm](a) = [n]([m]a) = [m]([n]a) and (a^m)ⁿ = a^mn = (aⁿ)^m.

A proof of Theorem 13. Let a and b be elements of the ring R. Since (R,+) is a group and R is a ring the elements ab and ^–(ab) are in R and ab + ^–(ab) = 0. Calculate ab + ^-ab. ab+^-ab =(a + ^-a)b = 0b = 0 by the distributive law, the property of additive inverses and Theorem 10. So ab + ^–(ab) = ab + ^-ab and by left cancellation in (R,+) it follows that ^–(ab) = ^-ab .

A proof of Theorem 17. Let a,b,c,d be elements of a field F and suppose b and d are non-zero. (ac)b^-1 = (ab^-1)c by the commutative law for multiplication and by the associative law for multiplication.

((ac)b^-1)d^-1 = ((ab^-1)c)d^-1 by the binary operation property. Finally, (ac)(b^-1d^-1) = (ab^-1)(cd^-1) by the associative and commutative laws for multiplication in F and by Theorem 8 from ring theory

(ac)(bd)^-1=(ab^-1)(bd^-1).

HW:

q Assume that all of the coefficients in the following are from Z₇ and all operations are modulo 7. Perform the indicated operations and rewrite your answers leaving no minus signs in them.

q (2x – 3)²

q (x – 2)(x + 5)

q Assume that R is the ring Z₆ with operations modulo 6. Compute each of the following for the element a = 3ÎR.

q a) 3a b) 10a c) a³ d) a⁷ e) (-5)a f) (-10)a

q Assume that R is the ring Z₆ with operations modulo 6. Compute each of the following for the element a = 3ÎR.

q a) 3a b) 10a c) a³ d) a⁷ e) (-5)a f) (-10)a g) a^-2 h) a^-5

q Assume that R is the ring of 2x2 matrices over Q with the usual matrix operations. Compute each of the following for the element .

q a) 3a b) 10a c) a³ d) a⁴ e) (-3)a f) (-10)a g) a^-2 h) a^-3

http://www.math.csusb.edu/notes/cgi/contents.cgi

http://www.math.niu.edu/~beachy/aaol/contents.html#index

19.

· Definitions: Let R be a ring and x be a symbol. The symbol x is called a commuting indeterminate over R provided TFSAT. For any a ÎR and any natural number n, (1) axⁿ is a new symbol and axⁿ is the same as xⁿa, (2) x¹ is denoted by x, (3) xⁿ denotes x … x with n terms for n>1, (4) ax⁰ is denoted by a and 0xⁿ is denoted by 0 and if R has a unity 1 then 1xⁿ is denoted by xⁿ and x⁰ is denoted by 1. Let R be a ring and let x be a commuting indeterminate over R. Let n be a whole number and let a₀, a_{1, …,} a_n be elements of R. The symbol a(x) which denotes a₀ + a₁x + a₂x² + …+ a_nxⁿ is called a polynomial in x over R. The element a_i is called the coefficient of xⁱ . Let R be a ring with commuting indeterminate x. The symbol R[x] will denote the set of all polynomials in x over R. Let a(x) = a₀ +a₁x + … + a_nxⁿ and b(x) = b₀ + b₁x + … + b_k x^k and assume k<n. Rewrite b(x) = b₀ + b₁x +…+ b_kx^k + b_k+1x^k+1 + … + b_nxⁿ where b_k+1=b_k+2=…= b_n=0. The sum a(x)+b(x) is defined by (a₀+b₀)+(a₁+b₁)x+…+(a_n+b_n)xⁿ and the product a(x)b(x) is defined by (a₀b₀)+(a₀b₁+a₁b₀)x+(a₀b₂+a₁b₁+a₂b₀)x²+…+(a₀b_m+k+a₁b_m+k-1+…+a_m+kb₀)x^m+k where each of a(x) and b(x) are extended to x^m+k with additional coefficients equal to zero in both cases.

· Theorems

19. Let F be any field, then F is an integral domain.

20. Let R be any ring, then R[x] is a ring.

A proof of Theorem 19. Let F be a field and let aÎF with a¹0. Suppose there is an element cÎF such that ac = 0. Since F is a field and a¹0, the element a ^-1ÎF and a ^–1(ac) = a ^–10 because multiplication in F is a binary operation. It follows that (a ^–1a)c = 0 from the associative law for multiplication and from Theorem 9. Finally, (1)c = c = 0 by the inverse and unity properties in F. This means F has no non-zero divisors of zero for if it did, then for some a¹0 there is a c¹0 so that ac = 0 and it was just shown that no such non-zero c exists.

HW:

q Prove that the polynomials over each of the rings, the integers, the rational numbers and the real numbers form an integral domain.

q Find the sum and product of each of the polynomials in the given polynomial ring.

f(x) = 2x² + 3x + 4, g(x) = 3x² + 2x + 3 in Z₆[x].

f(x) = 2x³+ 4x² + 3x + 2, g(x) = 3x⁴ + 2x + 4 in Z₇[x].

http://www.math.csusb.edu/notes/cgi/contents.cgi

http://www.math.niu.edu/~beachy/aaol/contents.html#index

20.

· Definitions: Let R be a ring and R[x] be the ring of polynomials in x over R. Let f(x)ÎR[x], f(x)¹0. Let S = { kÎW| a_k¹0, a_k a coefficient of f(x)}. S¹F. Let n = max{S}. The number n is called the degree of f(x) and is denoted by Deg(f(x)). If f(x) = 0 we say f(x) has no degree. (Some authors say Deg(0) = -¥ where -¥<0.)

· Theorems.

21. Let R be any ring with nonzero zero divisors, then R[x] also has nonzero zero divisors.

22. If R is an integral domain then R[x] is an integral domain.

23. Let R be an integral domain. If p(x) and q(x) are any polynomials in R[x] then

a) Either p(x) + q(x) = 0 or Deg( p(x)+q(x)) £ Max( Deg(p(x),Deg(q(x))

b) Either p(x)q(x) = 0 or Deg(p(x)q(x)) = Deg(p(x)) + Deg(q(x))

24. Let R be an integral domain. If p(x) and q(x) are any polynomials in R[x] with degree greater than or equal to one then Deg(p(x)) < Deg(p(x)q(x)) and Deg(q(x) < Deg(p(x)q(x)).

A proof of Theorem 21. Let a, b ÎR with a¹0, b¹0 and ab = 0. The f(x) = a and g(x) = b are nonzero elements of R[x]. Now, f(x)g(x) = ab = 0 . Therefore R[x] has nonzero divisors of zero.

A proof of Theorem 22. Suppose R is an integral Domain. The polynomial f(x) = 1 in R[x] is a unity in R[x] so R is a ring with unity. Let a(x) = a₀+a₁x¹+...+a_nxⁿ and b(x) = b₀+b₁x¹+...+b_kx^k be in R[x]. Let p(x)=a(x)b(x) have coefficients p_i. Now, p_i=a₀b_i+a₁b_i-1+...+a_ib₀=a_ib₀+a_i-1b₀+...+a₀b_i=b₀a_i+...+b_ia₀ first by the associative law and the commutative law of addition and then by the commutative property of R. The last expression is the coefficient of xⁱ in b(x)a(x). Therefore, R[x] is commutative. Finally, suppose a(x) and b(x) as above have degrees n and k respectively. Then a_n¹0 and b_k¹0 and the coefficient of x^n+k in a(x)b(x) is a_nb_n¹0 therefore R[x] has no nonzero divisors of zero.

Examples and a discussion of the division algorithm.

HW:

q Find q(x) and r(x) as described in the division algorithm so that f(x) = q(x) g(x) + r(x) with r(x) either equal to zero or else Deg(r(x)) < Deg(g(x)) in the given polynomial ring.

a) f(x) = x⁶ + 3x⁵ + 4x² – 3x + 2 and g(x) = x² + 2x – 3 in Z₇[x].

b) f(x) = x⁶ + 3x⁵ + 4x² – 3x + 2 and g(x) = 3x² + 2x – 3 in Z₇[x].

http://www.math.csusb.edu/notes/cgi/contents.cgi

http://www.math.niu.edu/~beachy/aaol/contents.html#index

21. Finishing polynomial rings.

· Definitions. Let f(x) and g(x) be polynomials in R[x] where R is a ring. The polynomial g(x) is said to be a factor of f(x) provided there exists an element h(x) in R[x] such that f(x) = g(x)h(x).

· Theorems

25. The Division Algorithm. Let F be a field. For any f(x) in F[x] and for any nonzero g(x) in F[x], there exist elements q(x) and r(x) in F[x] such that f(x) = q(x)g(x) + r(x) where either r(x) is identically zero or else 0£Deg(r(x))<Deg(g(x)). Furthermore, q(x) and r(x) are unique with respect to these properties.

A proof of Theorem 25. Let f(x) and g(x) be in F[x] where F is a field and g(x)¹0. Write g(x)=g₀+g₁x+…+g_nxⁿ with g_n¹0 and so Deg(g(x))=n.

Let S={p(x)Îf[x]| p(x) = f(x) –g(x)h(x) for some h(x)ÎF[x]}. Note that S¹F. There are two possible cases. Case 1. 0ÎS. In this case there is an h(x)ÎF[x}] such that

0 = f(x) – g(x)h(x) and setting r(x) = 0 and q(x) = h(x) gives the result. Case 2. Suppose 0ÏS. Let S = {kÎW| there is a p(x)ÎS with Deg(p(x))=k}. Note S¹F. By the well ordering principle, S has a smallest element, say m. Let r(x)ÎS so that Deg(r(x))=m and write r(x)=r₀+r₁x+…r_mx^m with r_m¹0. Note that r(x)=f(x)-g(x)h(x) for some h(x)ÎF[x]. In order to conclude that m<n, assume m³n and deduce a contradiction. Suppose m³n then there is a tÎW with m = n+t. Let t(x) = g_n^-1r_mx^t. The polynomial g(x)t(x) has degree m and leading coefficient r_m. Set s(x) = r(x)-g(x)t(x). Deg(s(x))<m.

But, s(x)=[f(x)-g(x)h(x)]-g(x)t(x) = f(x)-g(x)[h(x)-t(x)]ÎS and has degree smaller than the smallest element of S. This is a contradiction. Therefore, Deg(r(x))<n and so taking q(x)=h(x) where r(x)=f(x)-g(x)r(x) gives the result.

Finally, suppose (*) f(x) = g(x)q₁(x)+r₁(x) = g(x)q₂(x)+r₂(x). where either r₁(x)=0 or 0£Deg(r₁(x))<Deg(g(x)), and either r₂(x)=0 or 0£Deg(r₂(x))<Deg(g(x)). Rewrite equation (*) as g(x)[q₁(x)-q₂(x)]=r₂(x)-r₁(x). If r₂(x)-r₁(x)=0, then since F[x] is an integral domain and g(x)¹0 it follows that q₁(x)-q₂(x)=0 and so r₂(x)=r₁(x) and q₂(x)=q₁(x) as required. Suppose r₁(x)-r₁(x)¹0. Let s(x)=r₂(x)-r₁(x). Deg(s(x))£m<n. On the other hand g(x)[q₁(x)-q₂(x)]=s(x) and it follows that Deg(s(x))³n. Thus, n£Deg(s(x))£m<n which is a contradiction. Therefore, r₂(x)-r₁(x)=0 and the uniqueness follows.

Factors and solutions to equations

· Definitions. Let R be a ring and let aÎR. The mapping n_a : R[x]®R defined by n_a(f(x)) = f₀+f₁a+f₂a²+…+f_naⁿ where f(x) is given by f₀+f₁x+f₂x²+…+f_nxⁿ is called the evaluation map at a. An element a in R is called a zero of f(x) provided n_a(f(x)) = 0 . (If we write f(x)=0 as an equation in the variable x with values from R then a zero of f(x) is the same as a root of the equation.)

· Examples and a discussion of the connection between the zeros of f(x) and linear factors of f(x).

HW:

q Compute the values in Z₇ for each of the following evaluation mappings.

a) f₂(x²+ 3) b) f₃((x⁴ + 2x)(x³ – 3x² + 3)) c) f₃(x⁴ + 2x) f₃(x³ – 3x² + 3)

q For each of the following equations in Z_7, either solve the equation or show the equation has no solution in Z₇ using arithmetic modulo 7.

a)2 – x = 5 b) 3x + 2 = 5 c) x² = 1 d) 3x² = 6 e) x³ = 6

f) x² + 2x + 2 = 0 g) (x – 4)² = 4

q For each of the following equations in Z₅, either solve the equation or show the equation has no solution in Z₅ using arithmetic modulo 5.

a)x – 3 = 2 b) 2 – x = 4 c) 3x = 4 d) 2x = 3 e) 4x = 2

f) x² = 4 g) x² = 3 h) x² + 4x + 2 = 0.

q Find all zeros in the indicated field of the given polynomial with coefficients in that field.

a)x² + 1 in Z₂ b) x³ + 2x + 2 in Z₇

http://www.math.csusb.edu/notes/cgi/contents.cgi

http://www.math.niu.edu/~beachy/aaol/contents.html#index

22. Laboratory Four with Mrs. Buracker. Topics included Solving equations with hands on Equations and more on eigth grade SOL’s

23. Polynomial equations.

· Facts about the valuation mapping: Let a be an element of a ring R and let f(x) and g(x) be elements of R[x]. n_a(f(x) ± g(x)) = n_a(f(x)) ± n_a(g(x)) and n_a(f(x)g(x)) = n_a(f(x)) n_a(g(x))

· Definitions: Let R be a commutative ring and let a and b be elements of R. The element a is a divisor of b means that there exists an element cÎR such that c¹0 and ac=b. We say b is a multiple of a or a is a divisor of b and write a|b. An element dÎR is called a common divisor of a and b provided d|a and d|b. An element dÎR is called a greatest common divisor of a and b provided d is a common divisor of a and b, and if c is any common divisor of a and b then c|d. Denote d by g.c.d.(a,b). An element mÎR is called a common multiple of a and b provided a|m and b|m. An element mÎR is called a least common multiple of a and b provided m is a common multiple of a and b, and if k is any common multiple of a and b the m|k. Denote m by l.c.m.(a,b). Let f(x) and g(x) be elements of F[x] with g(x)¹0. Extend F[x] to a field called the field of quotients of F[x] by creating for each g(x)¹0 an element (g(x))^-1 and denoted by . Force addition and multiplication to satisfy all of the ring properties to discover the form of sums and products of elements in this new field.

· Euclid’s Algorithm for finding the g.c.d.(a,b) where a and b are in Z.

· Theorems

1. A polynomial equation f(x) = 0 with f(x) in F[x] has a solution x =a in F if an only if (x-a) is a factor of f(x).

2. Let F be a field. The Euclidean Algorithm holds in F[x].

3. Let F be a field. The integral domain F[x] can be extended to a field by constructing, for each nonzero f(x), a multiplicative inverse denoted by and extending the operations of addition and multiplication to these new elements so that the properties of a field will hold. This is called the field of quotients for F[x].

A proof of Theorem 1. (Þ) Let f(x)=0 have a root x=aÎF. By the division algorithm there exist polynomials q(x) and r(x) so that f(x) = (x-a)q(x) + r(x) where either r(x)=0 or r(x)=k where kÎR and k¹0. Since x=a is a root of f(x) we know that n_a(f(x))=0. But then 0= n_a((x-a)q(x)) + r(x)) = n_a((x-a)q(x)) + n_a(r(x)) = n_a((x-a)) n_a(q(x)) + k

=(a-a)n_a(q(x)) + k = 0 + k. So r(x)=0 and (x-a)|f(x).

(Ü) Suppose (x-a) is a factor of f(x). Then there exists q(x)ÎF[x] such that

f(x)=(x-a)q(x). So n_a(f(x)) = n_a((x-a)q(x)) = n_a((x-a)) n_a(q(x)) = (a-a) n_a(q(x)) = 0. Therefore x=a is a root of f(x)=0.

HW:

q The polynomial x⁴ + 4 can be factored into a product of linear factors in Z₅[x]. Find this factorization.

q The polynomial x³ + 2x² + 2x + 1 can be factored into a product of linear factors in Z₇[x]. Find this factorization.

q Find a polynomial f(x) in Z₇ which has no linear factors. What does this say about the solvability of the equation f(x) = 0?

q Show that x² – 2 = 0 has no solutions in Q.

q Find the g.c.d. of each of the following pairs of polynomials over the field Q of rational numbers.

(a) 2x³ – 4x² + x – 2 and x³ – x² – x – 2

(b) x⁴ + x³ + x² + x + 1 and x³ – 1

(c) x⁵ + x⁴ + 2x³ – x² – x - 2 and x⁴ + 2x³ + 5x² + 4x + 4

(d) x³ – 2x² + x + 4 and x² + x + 1

q Let f(x) = x² – x - 2 and g(x) = 1/(3x² – 9) and h(x) = 3x³ –6x² +3x + 9 be in the field of quotients for Q[x]. Calculate each of the following.

(a) f(x) + g(x)

(b) f(x)g(x)

(c) f(x) + g(x) + f(x)g(x) – h(x)

http://www.math.csusb.edu/notes/cgi/contents.cgi

http://www.math.niu.edu/~beachy/aaol/contents.html#index

24. Graph theory

· Definitions. A graph is a non empty set, V, of points called vertices along with a set, E, of line segments that have vertices as endpoints. The line segments are called edges. A graph may be represented by an ordered pair G = (V,E). An edge with coincident endpoint vertex is called a loop. A graph (V,E) such that each edge is a directed line segment is called a directed graph or digraph. A Cayley digraph is a digraph with vertices the elements of a group and the edges determined by the group operation of a generating set acting on the elements of the group. A path in a graph is a sequence of edges E₀, E₁, …, E_n such that each pair of successive edges share a common vertex. If a path is named by its end vertices then E₀ = V₀V₁, E₁ = V₁V₂ , …, En = V_nV_n+1 . The path E₀, E₁, …, E_n is written V₀V₁…V_n+1. We say the path joins V₀ and V_n+1. A path is an open path if V₀ ¹ V_n+1. If V₀ = V_n+1 then the path is said to be a closed path. A graph is connected provided every pair of vertices is joined by a path. Otherwise it is disconnected. A graph is a planar graph provided it CAN be drawn in the plane with its edges intersecting only at vertices. A graph is non-flat if it is drawn in the plane in such a way that at least two of its edges meet at a non-vertex. Note: non-flat is a property of how the graph is represented and planar is a property of how the graph CAN be drawn. If a graph is non-planar then every representation in the plane is non-flat. A planar graph may have a non-flat representation in the plane. A graph has an edge path provided there exists a path in the graph containing each edge exactly once. A graph has a vertex path provided there exists a path in the graph containing each vertex exactly once. If a vertex is the terminal point of an edge then that edge is said to be incident to the vertex. The number of edges incident to a given vertex is called the vertex number or degree for that vertex. A vertex is called an even vertex if the degree of the vertex is even and similarly with odd vertex.

· Theorems

1. If a graph has more than two odd vertices, then it has no edge path.

A Proof of Theorem 1. The proof will be by contrapositive. Suppose a graph has an edge path. Such a path is either open or closed. Suppose a vertex is not a terminal point of the graph. Then for each edge that enters the vertex there must be a corresponding edge that leaves the vertex. Therefore the number of edges incident to the vertex must be even and so every intermediate vertex of the edge path must be even. If the path is closed then the initial vertex is the ending vertex and so it must also be even. Finally if the path is open then the initial and ending vertices must be odd. Therefore, if a graph has an edge path then at most two vertices can be odd. By the contrapositive, if a graph has more than two odd vertices then the graph has no edge path.

HW:

· Consider the following drawings.

		D
						I
										J
								(iii)
	(i)
					(ii)

					(v)
		(iv)					(vi)
			Z
		(vii)

Referring to figure (vii) above:

a) Identify a path from X to X that uses no edge more than once.

b) Identify a path from W to X that uses every edge at least once.

c) Identify a path from W to Z that is an edge path.

d) How many different edge paths are there from W to X?

e) How many different edge paths are there from X to Y?

f) How many different paths are there from X to Y?

http://www.math.csusb.edu/notes/cgi/contents.cgi

http://www.math.niu.edu/~beachy/aaol/contents.html#index

25. Laboratory Five with Mrs. Buracker. Topics included factoring polynomials using the distributive property, difference of squares, perfect trinomials, grouping, the Pythagorean theorem and Standards of Learning.

26. More on Graph Theory.

· Examples using previous definitions.

q Which of the drawings as labeled above represent graphs?

q Which of the graphs above are connected?

q Which of the graphs above are flat?

q Which of the graphs above contain a loop?

· Definitions. All graphs will be finite meaning the set of vertices is finite and the set of edges is finite. A vertex having degree 1 is called a terminal vertex. The one edge incident to a terminal vertex is called a terminal edge. A vertex with degree zero is called an isolated vertex. A graph G is nearly connected provided TFSIT. G is connected or G is connected except for one or more isolated vertices.

· Observations. A finite graph cannot have exactly one odd vertex. A terminal vertex cannot be an intermediate point on any path. It must be either a starting point or an ending point of a path.

· Theorems.

2. A graph that has an edge path is nearly connected.

3. If a graph is nearly connected and has at most two odd vertices then it has an edge path.

4. If a graph has a vertex path then it is connected.

5. If a graph has a vertex path then it has at most two terminal vertices.

6. If a graph has a closed vertex path then is has no terminal vertices.

A Proof of Theorem 2 The graph G will be nearly connected provided the non-isolated vertices are connected. Let P and Q be vertices of the graph G and suppose neither of these points is isolated. P is an endpoint of some edge and Q is an end point of some edge. Suppose G has an edge path. Write the edge path as V₁V₂…V_jPX₁X₂…X_kQY₁Y₂…Y_n . Obviously, the path PX₁X₂…X_kQ shows that P and Q are connected by a path. Therefore, the non-isolated points of G are connected.

A Proof of Theorem 3. Since no graph can have exactly one odd vertex, it must be shown that if a nearly connected graph G has either 0 odd vertices or exactly 2 odd vertices then it has and edge path. The proof is by construction. Case 1. Exactly two odd vertices. Let P and Q be the odd vertices in G. Construct a path in G as follows. Use an edge only once and whenever there is an unused edge at a vertex proceed along that edge. (a) Start at P and take any edge from P. Now, every other vertex including P, except for Q and possibly the vertex on the opposite end of the edge from P, has an even number of unused edges remaining. Every one of these vertices except Q must be an intermediate vertex on the path you are constructing since every one of them has an edge out and so it cannot be a terminal point of the path. Therefore, the path being constructed must end at Q and every edge in the path is used only once. If every edge of the graph occurs in this path it is an edge path. If an edge has not been used yet, then there must be a vertex of the path that has an unused edge incident to it because G is nearly connected. Suppose the path has the form PV₁V₂…V_iXW₁W₂…W_jQ where X is incident to an unused edge. (b) Start at any vertex in the path that is incident to an unused edge. Now, P and every remaining vertex with unused edges must have even degree and so constructing a path from this vertex as in part (a) will produce a closed path. (c) If X is the vertex selected and XZ₁Z₂…Z_kX is the newly constructed path, splice it into the original path PV₁V₂…V_iXW₁W₂…WjQ to get PV₁V₂…V_iXZ₁Z₂…Z_kX W₁W₂…WjQ. Either this path is an edge path or it has a vertex that is incident to an unused edge. Repeat steps (b) and (c). The finiteness of the graph ensures that the process must stop with the construction of an edge path for G. Case 2. No odd vertices. The same type of construction works except that in part (a) if you start at P you must end at P since every vertex has even degree.

A Proof of Theorem 5. Proof by contrapositive. Let G have at least 3 terminal vertices P, Q and R. No path in G can have any of these vertices as an intermediate vertex. So, every path in G can contain only two of these three points, one as the starting point and one as an ending point. Therefore, G can have no vertex path.

HW:

q If we define the distance between two vertices on a graph as the number of edges along a path connecting the two vertices which has the smallest number of edges:

a) In figure (vi), what is the distance from P to T?

b) In figure (vi), what is the distance from P to S?

c) In figure (vii), What is the distance from W to Y?

d) In figure (vii), what is the distance from W to Z?

q For each of the following sets of conditions, give an example of a graph with four vertices that satisfies all of the given conditions. If this is not possible, explain why not.

a) Disconnected and nonflat.

b) Disconnected, with an edge path.

c) Disconnected, with a vertex path.

d) Connected, with no vertex path.

e) With and edge path, but no vertex path.

f) With a vertex path, but no edge path.

g) With an edge path and a vertex path.

q Consider the figures below:

1.

2.

1. Find the degree of each vertex in figure (c).

2. Which of the six graphs have no edge path?

3. Which have an open edge path?

4. Which have a closed edge path?

5. Which are Euler graphs?

http://www.math.csusb.edu/notes/cgi/contents.cgi

http://www.math.niu.edu/~beachy/aaol/contents.html#index

27.

· Definitions: A graph G is called an Euler graph provided TFSIT, G is connected and has a closed edge path. A graph G is called a polygonal graph provided TFSIT, G is connected and flat. Each of the regions of the plane determined by a polygonal graph is called a face of the graph. A curve C is called a crossing curve for a polygonal graph without a terminal edge provided TFSIT, C crosses from one face of a polygonal graph to another, it intersects each edge of the graph exactly once and it passes through none of the vertices. If G has a terminal edge then C can remain in a single face when crossing a terminal edge. The order of a face is the number of edges incident to the face with a terminal edge being counted twice to get the order of the face containing it. Let G = (V,E) be a polygonal graph. The graph is called the dual of G provided TFSIT, is the set with elements the faces of the graph G and is the set with edges F_iF_j such that there exists an e_ijÎE and e_ij is incident to F_i and F_j. Note that E and are in one to one correspondence.

· Theorems

7. A polygonal graph has a crossing curve if and only if its dual graph has an edge path.

8. If a polygonal graph has a crossing curve, then either all faces have even order, or there are exactly two faces of odd order and the curve begins in one odd face and ends in the other.

9. If a polygonal graph has more than two odd faces, then it has no crossing curve.

A proof of Theorem 7. (Þ) Let C be crossing curve for a polygonal graph G. C must start in some face and stop in some face. The starting face identifies a specific vertex on as the starting vertex for a path and the stopping face identifies a specific vertex on as the ending vertex for a path. As the curve C crosses an edge of G it specifies a transition from one face to another (or from a face to itself) and this identifies an edge of that is incident to the corresponding vertices in . The crossing curve C crosses each edge of G exactly once and since E and are in one to one correspondence this means that every edge of gets used exactly once. Therefore, the crossing curve C specifies an edge path of .

(Ü) Let P be an edge path of . P has a starting vertex and an ending vertex. The starting vertex identifies a face of G as a starting face for a curve C and the ending vertex identifies a face in which C ends. P uses each edge of exactly once and each edge of identifies a transition from one face of G to another (or from a face to itself) that crosses an edge of G. Since E and are in one to one correspondence this means that every edge of G gets crossed exactly once. Therefore, the edge path P of specifies crossing curve of G.

HW:

Consider the figures from last class.

6. Identify the faces and the orders of the faces of graphs (a), (b), (e) and (f).

7. Draw the duals of graphs (a), (b), (e) and (f).

8. Which of the graphs (a), (b), (e) and (f) have crossing curves?

http://www.math.csusb.edu/notes/cgi/contents.cgi

http://www.math.niu.edu/~beachy/aaol/contents.html#index

28.

· Definitions. A graph G is called a Hamilton graph provided TFSIT. G has a closed vertex path. A vertex C in a connected graph G is called a critical vertex provided TFSIT. The removal of C and all edges incident to C leaves a disconnected graph. A graph G is called a simple graph provided TFSIT. There is no more than one edge between any two vertices of G. An edge E of a simple graph G is called an H-edge provided TFSIT. If P is any closed vertex path for G then E must be a part of P. An H-edge E is called a first order H-edge provided TFSIT. E is incident to a vertex of degree 2. If G is a simple graph and G’ is obtained from G by removing all first order H-edges and all paths that cannot be on any closed vertex path, then a first order H-edge for G’ is called a second order H-edge for G. The second order H-edges of G are H-edges of G. The process can be iterated.

· Theorems

10. A Hamilton graph contains no critical vertices.

11. In a Hamilton graph no vertex is incident with more than 2 H-edges.

12. If the H-edges of a graph G include a closed path among some, but not all, vertices then G is not a Hamilton graph.

13. An edge incident to a vertex of degree two is an H-edge.

14. Starting with a single vertex and then expanding by successively performing one of two types of construction one may construct any polygonal graph. Type 1. Add a new vertex and join it by an edge to an existing vertex. Type 2. Add a new edge [possibly a loop] by joining two [not necessarily distinct] vertices already present.

A proof of Theorem 14. Let G be a polygonal graph. G is connected. Choose two vertices in G and connect them with a path in G consisting of distinct vertices. Write as P = V₁V₂…V_n . Starting with V₁ and performing a Type 1 construction n-1 times with vertices V₂, V₃, …, V_n gives P. If every vertex in G appears in P then the remaining edges of G can be added by using a Type 2 construction the appropriate number of times. In this way G is constructed as required. If there are still vertices of G not included in P then select a vertex on P and one not on P and connect them with distinct edges of G using Type 1 constructions. Continue this process until all vertices and all edges of G have been supplied and the theorem is proved.

HW:

q Consider the figures below:

1. Which graphs have terminal vertices?
2. Which graphs have critical vertices?
3. Which graphs are not simple?
4. Identify the H-edges of graphs (c), (d), (e) and (f).
5. Identify the secondary H-edges of graphs (c), (d), (e) and (f).
6. Which graphs are not Hamilton Graphs?
7. Which graphs are Hamilton Graphs?
8. Identify the number of vertices, the number of edges and the number of faces for graphs (c), (e) and (f).

http://www.math.csusb.edu/notes/cgi/contents.cgi

http://www.math.niu.edu/~beachy/aaol/contents.html#index

29.

· Definitions. A solid, S, in three space is called a regular solid provided TFSIT.

Each face of S is an equiangular and an equilateral polygon, and the same number of faces of S meet at every vertex of S.

· Theorems

15. Euler’s Formula. Let G = (V,E) be a polygonal graph and let n = #(V), e= #(E) and j be the number of faces of G. n + j - e = 2.

16. In any regular solid, S, where D is the degree of each vertex, R is the order of each face and e is the number of edges in the flat graph that represents S.

A proof of Theorem 15. Let G = (V,E) be a polygonal graph. G can be constructed from a single point by performing a succession of type I or type II constructions. Note that a type I construction increases n by one and increases e by one. Similarly, a Type II construction increases e by one and increases j by one. So, if G_i is any polygonal graph for which Euler’s formula holds and you construct G_i+1 using a type I or type II construction then the formula still holds for graph G_i+1. Now, if G₀ is a graph consisting of a single vertex from G then the formula holds for G₀ since n + j - e = 1 + 1 – 0 = 2. By the previous theorem we can realize G by the sequence G₀, G₁, G₂, … G_n =G where every construction of type I or type II. The formula holds for all cases and so the formula holds for G.

A proof of Theorem 16. Every regular solid S has a representation as a polygonal graph. A vertex in the plane can represent each vertex of S, each edge of S connects vertices of S and hence vertices in the plane, every vertex of S has the same number of faces meeting there and that number is the degree of each vertex in the plane. So, if D is the degree of each vertex in the polygonal graph representation of S, then nD = 2e since each edge connects two vertices and is counted twice in this product. Similarly, if R is the order of each face in the polygonal graph representation of S, then Rj = 2e since each edge separates two faces [there are no terminal edges]. Now use Euler’s formula to get the result.

From Theorem 16. it is easy to deduce that there are exactly 5 regular solids and these are called the Platonic Solids.

HW:

q Which of the graphs of the tetrahedron, hexahedron, octahedron and icosahedron are Euler graphs? Which are Hamilton graphs?

q A certain construction job has several phases to it and each phase requires a certain amount of time to complete. The table below summarizes the time required for each phase of the job.

Task	Days
A. Frame the walls	3
B. Panel walls	4
C. Hang acoustic ceiling	3
D. Install wiring	2
E. Install electrical fixtures	1
F. Do Plumbing	3
G. Install wet bar	2
H. Lay carpet	2
Total	20

There are always at least two workers assigned to each job and so it will take 10 days to complete the job with a two-person crew. A further examination of the project suggests that certain phases must be completed before other phases begin. The table below summarizes the precedence requirements of the job.

Before Starting Task	We Must Complete Task
B	A,D,F
D	A
E	A,B,C,D
G	F
H	A,B,C,D,E,F,G

Use this information to construct a directed graph to summarize the information and then study that digraph to determine if a two-person crew can complete the job in less than 10 days. What about two or more two-person crews? Assume that a crew will have to be paid for a whole day whether it works the whole day or not. What option would be cheapest? What option would be quickest?

30. Discussion of the last homework problem. Wrap up the course. Hand out the final examination to be due in one week. Take student evaluations.