MTH 310.003
Abstract Algebra I

• Daily quiz-prep problems: Not collected, but you must do these after every lecture to be ready for the next Quiz. Solutions posted, but only look after a serious effort.
• Weekly hand-in problems: Due in class on date indicated (usually Mon after they are assigned). I encourage teamwork in solving these problems, but everyone must turn in a final solution in their own words, not copied from someone else. Give credit to any person or reference that helped you.
• Extra credit problems: Optional, may be handed in within a week or two of the HW date. Again, give credit to any person or reference that helped you.

Reading: Notes below, Wikipedia.    
Exercises:

1. Consider the following statements. A: I am hungry. B: I eat a sandwich. Write each implication below in terms of A,B. Which pairs of statements are converses of each other (and thus logically different)? Which pairs are contrapositives (and thus logically equivalent)?
   1. If I am hungry, I eat a sandwich. (This is A ⇒ B.)
   2. If I eat a sandwich, I am hungry.
   3. If I'm not eating a sandwich, I am not hungry.
   4. If I'm not hungry, I don't eat a sandwich.
2. C: All food looks good to me. This statement is actually an implication: If there is any food, then it looks good to me.
   1. Write the contrapositive, the converse, and the negation of C.
   2. Write the logical framework (discussed in class) to prove a compound statement like (A ⇒ C): "If I am hungry, then all food looks good to me."
   3. Write the contrapositive and the converse of (A ⇒ C).
   4. Extra Credit: Write as many statements as you can which are equivalent to (A ⇒ C).

1. The pair (a),(c) are equivalent contrapositives. So are the pair (b),(d) are contrapositives of each other, and converses of (a),(c).

2a. Take C to be (D ⇒ E). Contrapositive: NOT(E) ⇒ NOT(D), "If something looks bad to me, it isn't food.". Converse: E ⇒ D, "If something looks good to me, then it is food", or "Nothing besides food looks good to me." Negation: D and NOT(E), "This is food, but it looks bad to me", or "Some food looks bad to me."

2b. Assume "I am hungry" and "there is some food", and deduce "it looks good to me". That is, to prove A ⇒ (D ⇒ E), we show the equivalent statement (A and D) ⇒ E.

2c. Contrapositive: NOT(C) ⇒ NOT(A): "If some food looks bad to me, then I'm not hungry". Converse: C ⇒ A: "If all food looks good to me, then I'm hungry."

A proof is a sequence of logical deductions from specified facts and assumptions to a desired conclusion. Writing proofs is an art, with no easy method to it, but the following steps are the basics.

1. Get a feel for the proposition in manageable examples, as many as you can.
   • If the statement doesn't seem reasonable in the examples, it is probably false, or you are not understanding it properly.
   • If a general statement clearly fails for just one example (a counter-example), then it is certainly false: no proof could exist, since it would also apply to the counter-example.
2. Determine the parts of the proposition.
   • Hypothesis: what is given or assumed, the setup, often appearing after "if" or "let" or "for any" in the statement.
   • Conclusion: what is to be proved, often appearing after "then" in the statement.
   • Write the hypothesis at the top of your page, the conclusion at the bottom, leaving lots of blank space between.
   • Be clear on the background you are allowed to use in the proof, depending on your audience. In this course, we assume all facts of arithmetic and high-school algebra applying to integers and rational numbers. You can use these without justification, since we all know them. (We do not know the corresponding facts about other number systems until we prove them or assume them as Axioms.)
   • Use previous results in your proof by refering to them (no need to re-prove). Once such facts become thoroughly familiar, you can just use them without references.
3. Construct a bridge of logical implications (⇒) from the hypothesis to the conclusion. This is the hard part! Strategies:
   • Review the defintion of each term in the hypothesis and conclusion. Write the definitions near the terms: they will almost certainly be needed in your proof.
   • Break down more complicated propositions into sub-statements, each with its hypothesis and conclusion.
   • Work from both ends, transforming the hypothesis and conclusion into different forms until you get both in the same form.
   • Transform the statement logically, such as into the contrapositive: P ⇒ Q is equivalent to NOT(Q) ⇒ NOT(P).
     Example: "If it is raining, then I carry an umbrella" is equivalent to "If I do not carry an umbrella, then it is not raining".
   • Warning: Do not confuse a statement P ⇒ Q with its converse Q ⇒ P.
     Example: "If it is raining, then I carry an umbrella" is logically independent from "If I carry an umbrella, then it is raining".
   • Break the proposition P into a sequence of statements P₀ , P₁ ,..., and try a proof by induction.
   • If all else fails, try proof by contradiction: assume the hypothesis is true, the conclusion is false, and logically derive a nonsensical statement that something is both true and false.
     Not recommended for beginners! Any mistake will lead to a contradiction which looks like a success.
4. Make a final draft of the proof:
   • Start with a complete statement of the Proposition (or Theorem for important propositions, Lemma for less important ones).
   • The logical flow of deductions must be clear: FROM the hypothesis TO the conclusion (no more working from both ends).
   • Each successive statement must be clearly true, given the previous statements. Inferences can be justified by definitions, by previously proved statements, or by general logical principles, such as: if two things are equal, then we can substitute one for the other in any statement or equation.
   • Leave out: the story of how you found the proof, examples and specific cases that you tried, and anything else outside the logical path from hypothesis to conclusion.
   • Judge your audience: leave out details that will be obvious to them. As in other forms of expository writing, more words = more pain. We consider a proof rigorous not if it spells out every last detail, but rather if it is clear to the audience how every last detail could be supplied if wanted.
     In your HW, assume your audience is one of your classmates who has not done this assignment and needs a good deal of explanation. Do NOT assume the audience is the professor, who knows all about the problem and needs only a hint that you understand the proof.

Reading: Ch 1.1, p. 3-8; Ch 1.2 Ex 15, p. 15. Notes on Euclidean Algorithm.
HW:

1. Perform the Euclidean Algorithm for the pairs a,b on p.14 #1(a)-(d). You should work out the arithmetic by hand, but you can check it on WolframAlpha using QuotientRemainder.
   1. Verify that the last non-zero remainder r_k is a divisor of a and b.
   2. Working backward from r_k = q_k+1r_k−1 − r_k−2, write r_k = na + mb for integers n,m.
2. Hand In Wed 9/5: The usual division-with-remainder algorithm takes input integers a,b with a ≥ 0 and b > 0, and gives output integers q,r such that a = bq + r with 0 ≤ r < b.
   Problem: Find and clearly describe an algorithm to make this work for any integer a, even if a is negative. (We still have 0 ≤ r < b, but the quotient q may be negative.) Given the known properties of the usual division-with-remainder, prove that your extended algorithm also works.
   Example: For a = −365 and b = 7, we have −365 = 7(−52) − 1 = 7(−53) + 6, so q = −53 and r = 6. How to do this in general, and how to be sure it works?
   
   • State the inputs and outputs of the algorithm.
   • Give a step-by-step description of the algorithm, introducing new variables as needed.
   • You may use the division-with-remainder algorithm for positive integers: take it as known, no need to describe its steps.
   • Waste no words: no need for more than a couple of short steps, three or four lines at most.
3. Extra Credit: State the Extended Euclidean Algorithm from the notes as a recursive formula. (Introduce new variables as needed.)

1a. ([H] p.14, #1(c)) Euclidean algorithm:
72 = 1·56 + 16; 56 = 3·16 + 8; 16 = 2·8 + 0.
Last non-zero remainder is d = r₂ = 8, a common divisor of 72 = 9·8 and of 56 = 7·8.
(Here it is easy to see this is the greatest common divisor, gcd(72,56) = 8.)

1b. Extended Euclidean Algorithm. Move remainder to left of each division equation:
8 = 56 − 3·16; 16 = 72 − 1·56. Starting with the first equation, then substituting the second:

8  =  56 − 3·16  =  56 − 3(72 − 1·56)  =  −3·72 + 4·56.

That is, 8 = n·72 + m·56 for n = −3, m = 4.

Reading: Ch 1.2, p. 9-14.
HW:

1. Propositon: For integers a,b ∈ Z, if a|b and a|c, then a | (nb+mc) for any n,m ∈ Z. Prove this using only the definition of divisibility.
2. True or false: If a|c and b|c, then ab|c? Prove this from the definition, or give a counterexample (i.e. specific a,b,c for which the hypothesis is true but the conclusion is false).
3. Proposition: If n,m ∈ Z with nm = 1, then n = m = 1 or n = m = −1. Prove this using the usual algebraic properties of multiplication, ordering ( > and < ), and absolute values.
4. Hand In Wed 9/5: Proposition: For integers a,b ∈ Z, if a|b and b|a, then a = b or a = −b. Give a formal proof.
   • Start by stating the proposition.
   • In the rough draft of your proof, identify the hypothesis or setup (what is assumed), and the conculusion or punchline (what is to be deduced). Also state the definitions of the key terms in the hypothesis and conclusion.
   • Find a sequence of logical deductions from the hypothesis to the conclusion. This is an easy proof requiring only one or two deductive steps.
   • You may quote and use any previous propositions which have already been proved, such as the previous HW problem.
   • Hand in only the clean final draft of your proof, in which you state only the essentials of the proof in logical if-then order, not the story of how you found it.
5. Extra Credit: Prove: If a|c and b|c with gcd(a,b) = 1, then ab|c. Use our theorems about gcd and linear combinations.

1. Proposition: For integers a,b,c ∈ Z, if a|b and a|c, then a | (nb+mc) for any n,m ∈ Z.
Proof: (HYPOTHESIS) Suppose a,b,c ∈ Z with a|b and a|c. By definition, this means b = ae and c = af for some e,f ∈ Z. Thus for any n,m ∈ Z, we have:

nb + mc = nae + maf = (ne+mf)a,

where ne + mf ∈ Z. Therefore by definition, a | (nb+mc) (CONCLUSION). QED

2. False. Taking a = 4, b = 6, and c = 36, we see 4 | 36 and 6 | 36, but 4·6 = 24 is not a divisor of 36. Even simpler: take a = b = c = 2. Any counter-example invalidates the theorem: there could be no general proof, since it would not work on this example.

3. Proposition: If n,m ∈ Z with nm = 1, then n = m = 1 or n = m = −1.
Proof: (HYPOTHESIS) Suppose n,m ∈ Z with nm = 1. This implies |n||m| = |nm| = 1, where |n|,|m| ∈ N. If we had |n| = 0 or |m| = 0, this would mean |n||m| = 0, contradicting the hypothesis. Thus |n|,|m| ≥ 1. If we had |n| > 1 or |m| > 1, this would mean |n||m| > 1·1 = 1, again contradicting the hypothesis. The only possibility left is |n| = |m| = 1, so we must have n = m = 1 or n = m = −1 (CONCLUSION). QED

Reading: Ch 1.3, pp. 17-22.
HW:

1. For the pairs a,b on p.12 #1(a)-(d), compute gcd(a,b) by finding the prime factorization of a and of b, and taking the prime factors common to both (counting repeats). Also compute the least common multiple lcm(a,b) by merging the lists of prime factors, and verify that lcm(a,b) = ab / gcd(a,b).
   Example: 12 = 2·2·3 and 20 = 2·2·5 have the common prime factors 2·2 = 4 = gcd(12,20). Meanwhile lcm(12,20) = 2·2·3·5 = 60 = ^12·20⁄₄.
2. The two examples below seem to give two different prime factorizations of the same number, giving counter-examples to the Fundamental Theorem (Thm 1.8, p. 20); but this should be impossible. What is wrong with the examples?
   1. 1001 = 7·143 = 11·91.
   2. 959 = 7·137 = 11·89.
3. Hand In Mon 9/10: p.18 #4: We know (Thm 1.5, p. 18) that for p a prime integer, if p|ab then p|a or p|b. Now prove the following converse statement: Suppose that an integer q ≠ 0, ±1, has the property that if q|ab, then q|a or q|b; this can only happen when q is a prime.
   • Hint: Suppose q has the property, and take any prime divisor p of q, so that q = pe. Then q | pe, and you can apply the property.
4. Hand In Mon 9/10: p.18 #12(a): Prove that if 3 | (a²+b²), then 3|a and 3|b. Hints:
   • Prove the equivalent contrapositive statement: if 3 does not divide a or 3 does not divide b, then 3 does not divide a²+b².
   • Use the fact that if 3 does not divide a number, then it is of the form 3c+1 or 3c+2.

1. p. 12 #1a. 56 = 2³ 7 , 72 = 2³ 3², so gcd(56,72) = 2³ = 8 , lcm(56,72) = 2³ 3² 7 = 504 , and indeed 504 = 5

2a. The factors 143 = 11·13 and 91 = 7·13 are not prime. The unique prime factorization is 1001 = 7·11·13.

2b. Compute: 7·137 = 959, while 11·89 = 979, so these are prime factorizations of two different numbers.

• Prime Divisibility Property: Let p be prime and a,b any integers. If p | ab, then p | a or p | b.
  Proof: Hypothesis: p | ab. In case p | b, then the conclusion holds. In the other case, p does not divide b, and gcd(p,b) = 1. By the Euclidean algorithm, we can write 1 = ps + bt for s,t ∈Z, so that a = aps + abt. Now p | ab by hypothesis, so p | abt; and obviously p | aps. Hence p | a = aps + abt, and the conclusion holds in this case too.
• Fundamental Theorem of Arithmetic for Integers: Any integer n ≠ 0, ±1 can be written uniquely as a product of primes, except for reordering the factors and changing signs.
  Equivalently, n ≠ 0 can be written uniquely as: n = 2^r₁ 3^r₂ 5^r₃ · · · p_k^r_k , where the exponents are whole numbers r₁, ... , r_k ≥ 0, and p_k is the largest prime factor of n (meaning r_k > 0).
  In short: Products of different primes are never equal.
• Fundamental Theorem of Arithmetic for Rationals: Any rational number ^a⁄_b ≠ 0 can be written uniquely as: ^a⁄_b = 2^r₁ 3^r₂ 5^r₃ · · · p_k^r_k , where the exponents are integers: r₁, ... , r_k are positve, negative, or zero (and r_k ≠ 0).
  Furthermore, we have ^a⁄_b = n ∈ Z an integer if and only if the exponents are non-negative: r₁, ... , r_k ≥ 0
• Examples:
  • ^a⁄_b = ³⁄₅ = 3¹ 5⁻¹ = 2⁰ 3¹ 5⁻¹.
    We would get the same if we computed with a non-reduced form of the same fraction: ³³⁰⁄₅₅₀ = (2×3×5×11) / (2×5²×11) = 2¹⁻¹ 3¹ 5¹⁻² 11¹⁻¹ = 2⁰ 3¹ 5⁻¹. Here p_k = 5, the largest prime factor of the numerator or denominator of ^a⁄_b (written in lowest terms).
  • Given an expression like 2³ 3⁻² 5⁻¹ 7¹, we know it could not be an integer since it has negative exponents, which could never be cancelled by the positive exponents on other primes.

HW:

1. Euclid's prime algorithm: Start with a list of known primes q₁,...,q_k, and factor the number a = q₁...q_k + 1. The factors are new primes, not previously on our list. If we add them to the list, we can repeat the process and get more and more new primes. Since this algorithm never gets stuck, it will produce an infinite list of primes.
   1. Generate 10 primes by Euclid's method, starting with q₁ = 2. Does this method seem to generate all primes? Hint: Wolfram Alpha will factor integers.
   2. Hand In Mon 9/10: Prove that the above algorithm never gets stuck: it always produces new primes not on the previousl list q₁,...,q_k.
2. Eratosthenes' method for generating all primes up to n: Make a table of numbers 2,...,n. Circle the first number 2 (a prime) and cross out all multiples 4,6,8,..., which cannot be primes. Circle the next number not crossed out, which is 3 (the next prime) and cross out all multiples 6,9,12,.... Continue until all numbers are circled or crossed out. In fact, you only need to continue up to √n; after that, there are no more numbers to cross out. (Why?)
3. Extra Credit: Formulas for primes. Is it possible to give a formula f(n) whose values are prime for all n = 0,1,2,...? Or even for infinitely many n?
   1. Prove or disprove: the formula f(n) = n² + n + 41 gives a prime for every n = 0,1,2,.....
   2. Is there any polynomial formula   f(n) = a_kn^k + a_k−1n^k−1 + ... + a₁n + a₀   which outputs only prime values for n = 0,1,2,...? What about a linear combination of exponentials? Explore!
   3. Prove: If 2^k + 1 is prime for a positive integer k > 0, then k = 2ⁿ for some integer n ≥ 0.
   4. Define the Fermat numbers F(n) = 2²ⁿ + 1, so that F(0) = 2¹ + 1 = 3, F(1) = 2² + 1 = 5, F(2) = 2⁴ + 1 = 17, etc. Find the first value of F(n) which is not prime.
   5. Prove that: F(n) = F(0)F(1)F(2)...F(n−1) + 2; and gcd(F(n),F(m)) = 1 for n ≠ m. Conclude that factors of Fermat numbers give infinitely many primes.

1a. See W|A.

2. There are 25 primes less than 100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71. A nice picture shows prime factors by colors around each number.

• Proposition: For any integer n > 0, the square root √n is either a whole number (√n ∈ Z; n is a perfect square); or √n is irrational (√n ∉ Q; √n is not any fraction ^a⁄_b).
  Proof: Suppose we have √n = ^a⁄_b, so that nb² = a². Denote the prime factorizations as follows: a = 2^r₁ 3^r₂ 5^r₃ ··· p_k^r_k,     b = 2^s₁ 3^s₂ 5^s₃ ··· p_k^s_k,     n = 2^t₁ 3^t₂ 5^t₃ ··· p_k^t_k. Writing both sides of nb² = a² in terms of prime factors: (2^t₁ 3^t₂ 5^t₃ ··· p_k^t_k) (2^s₁ 3^s₂ 5^s₃ ··· p_k^s_k)²   =   (2^r₁ 3^r₂ 5^r₃ ··· p_k^r_k)². Since prime factorization is unique, we can equate the exponents on the two sides: t₁ + 2s₁ = 2r₁ , . . . , t_k + 2s_k = 2r_k . Thus, for each prime, we have: t_i = 2(r_i − s_i) = 2u_i : that is, the exponent t_i = 2u_i is even, meaning each prime divides n an even number of times. But this means: n  =  2^2u₁ 3^2u₂ 5^2u₃ ··· p_k^2u_k  =  (2^u₁ 3^u₂ 5^u₃ ··· p_k^u_k)²  =  m² for an integer m. That is, n = m², meaning n is a perfect square (such as n = 1,4,9,16,...), and √n = m is a whole number.
  Our argument shows that this is the only way a square root can be a fraction. For any non-perfect-square n (such as n = 2,3,5,6,7,8,10,...), one of the equations t_i + 2s_i = 2r_i will have an odd number one side and an even on the other, which is impossible. Thus, n cannot have a rational square root, and √n is irrational. Q.E.D.

Reading: Ch 2.2, pp. 32-33.
HW:

1. Suppose someone claimed that √5

   ?

   =

   ^5×5⁄₁₁ . Show this must be wrong without doing any arithmetic. Use only that products of different primes are never equal (the most basic form of the Fundamental Theorem).
2. Hand In Mon 9/17: Prove: ∛2 is irrational. Hint: Adapt our proof for √2, using unique factorization to show that ∛2 = ^a⁄_b forces an exponent of 2 to be divisible and not divisible by 3, a contradiction.
3. Denote the numbers on a clock by [0] = [12], [1], [2], . . . , [11]. We also consider [13] = [1] = [−11], [−1] = [11], etc. Define clock multiplication by: [a][b] = [ab] = [r], where division by 12 gives ab = 12q + r with remainder 0 ≤ r < 12. For example, [5][7] = [35] = [11], since 35 = 12·2 + 11.
   Problem: Make a complete clock multiplication table, with all entries among [0] , [1] , . . . , [11]. Can it happen that [a],[b] ≠ [0], but [ab] = [0]?
4. Clock reciprocals.
   1. Determine which numbers [a] have a reciprocal [b] = [a]⁻¹ satisfying [a][b] = [1]. Not all [a]'s have such a reciprocal: do you notice something in common among the [a]'s which do have a reciprocal?
   2. Use the reciprocal [7]⁻¹ to solve the clock-arithmetic equation [7]x + [10] = [3].

1. This would mean 5 = 11² / 5², so 5³ = 11². But no positive power of 5 can equal a power of 11, since these are different primes. (Indeed, arithmetic shows: 5³ = 125 ≠ 121 = 11², and √5 ≈ 2.23, whereas 25/11 ≈ 2.27.)

3.

Notice that rows of [n] with gcd(n,12) = d > 1 have a repeating pattern including [0].

4. The numbers [n] having [1] in their row, so that they have a clock reciprocal with [n][m] = [1], are [n] = [1], [5], [7], [11]. These are all equal to their own reciprocals, which is a special feature of the 12-hour clock. Only [n] with gcd(n,12) = 1 have [1] in their row, and thus have a clock reciprocal [n][m] = [1].
To solve [7]x + [10] = [3], subtract [10] from both sides to get [7]x = [-7] = [5], then multiply [7]x = [5] by [7]⁻¹ = [7] to get:

[7][7]x  =  [7][5]

[7]⁻¹[7]x  =  [35]

[1]x  =  [35]

Thus x = [35] = [11] is the unique solution.

• For a fixed value of n, we say a and b are congruent or equivalent modulo n, written a ≡ b (mod n), whenever n | (a−b); that is, a−b = ne for some e ∈ Z.
  If the value of n is fixed, we write simply a ≡ b.
• The congruence class or equivalence class of a number a is the set of all integers congruent to a: [a]  =  {b ∈ Z such that b ≡ a}  =  { ... , a − n , a , a + n , a + 2n , ... }.
• For integers a,b ∈ Z, the following conditions are all equivalent: different ways of expressing the same thing.
  • [a] = [b] in Z_n
  • a ≡ b (mod n)
  • n | (a−b)
  • a and b have the same remainder when divided by n: that is, a = ns + r and b = nt + r for some r,s,t ∈ Z.

Reading: Ch 2.1, pp. 25-30. Ch 2.2 pp. 32-34.
HW:

1. Prove: If a ≡ b and b ≡ c, then a ≡ c. (This is called the transitive property of   ≡ .)
2. Hand In Mon 9/17: Prove: For any integers a,b, we have a ≡ b if and only if a and b have the same remainder when divided by n.
   Note: This is a statement of the form: "A if and only if B" (or A ⇔ B), which must be proved in two parts: "if A then B" (A ⇒ B) and "if B then A" (B ⇒ A). Hint: Consider the two remainders, and conclude they are the same.
3. We proved the rule for divisibility by 3 via the Propositon: If a = a_k10^k + a_k−110^k−1 + ... + a₁10 + a₀, then a ≡ a_k + a_k−1 + ... + a₁ + a₀ (mod 3). That is, a is congruent to the sum of its digits (mod 3). This is simply because 10 ≡ 1 (mod 3), so that 10ⁱ ≡ 1ⁱ ≡ 1 (mod 3).
   Work out the analogous proposition for divisibility by 2, 5, 11, and the corresponding divisibility rule. Hint: 10 = −1 (mod 11).
4. Prove or disprove: if a² ≡ b², then a ≡ b or a ≡ −b. Here we work modulo any given n.
5. Ch 2.3 Ex #11, p. 37: Solve congruences for an unknown x. Hint: Try each value of x (mod n), i.e. x = 0,1,...,n−1. Can you explain the result more simply in terms of multiplication?
6. Prove: For any a ∈ Z, we have ab ≡ 0 (mod 12) for some b, or a² ≡ 1 (mod 12) for any a. Hint: Use the multiplication table from last time.

3. Let a = a = a_k10^k + a_k−110^k−1 + ... + a₁10 + a₀.
For n = 2, we have 10 ≡ 0 (mod 2), so 10ⁱ ≡ 0 for i ≥ 1, and a ≡ a₀ (mod 2). That is, a number is even whenever its last digit is even. Similarly for n = 5.
For n = 11, we have 10 ≡ −1 (mod 11), so 10ⁱ ≡ (−1)ⁱ, and a ≡ a₀ − a₁ + a₂ − ... + (−1)^ka_k (mod 11). That is, a is congruent (mod 11) to its alternating (add/subtract) digit sum, and a is divisible by 11 whenever the alternating sum is divisible by 11 (i.e., when iterating the alternating sum eventually gives 0).

4. False: We have 2² ≡ 0² (mod 4), but 2 is not congruent to ± 0 (mod 4). Note: Usually, we would prove this by writing

a²−b² ≡ (a−b)(a+b) ≡ 0,

which would imply a−b or a+b ≡ 0. However, if there are zero-divisors in our clock arithmetic, with cd ≡ 0 even though c,d not ≡ 0, this implication fails. Still, there are no zero-divisors for n = p a prime, so the statement is true!

5. The equations are true for any x ∈ Z_n, because they are equivalent to [n]x = [0], i.e. [0]x = [0].

6. The every row of the multiplication table modulo 12 either contains [0] or has [1] on the main diagonal. Note that [a]² = [1] iff [a]⁻¹ = [a].

Proposition: A clock number [a] ∈ Z_n has a reciprocal [a]⁻¹ = [b] ∈ Z_n with [a][b] = [1], if and only if gcd(a,n) = 1.
Proof: (⇐) Suppose gcd(a,n) = 1. By the Extended Euclidean Algorithm, there exist s,t ∈ Z with as + nb = 1. Thus as = 1 − nb, so as ≡ 1 (mod n), and [a][s] = [1]. Thus, we have the reciprocal [a]⁻¹ = [s].
(⇒) The converse implication is an exercise below.

Reading: Ch 2.2 pp. 34-36.
HW:

1. Hand In Mon 9/17: Prove: For any a,n ∈ Z, if [a] ∈ Z_n has a reciprocal [a]⁻¹ = [b] with [a][b] = [1], then gcd(a,n) = 1.
2. Extra Credit: Alternative definition of clock arithmetic.
   1. The most obvious way to add two sets A,B ⊂ Z is to add all their elements pairwise: A + B  =  { a + b  for  a ∈ A, b ∈ B }. Show that this agrees with our previous definition of clock addition on the congruence class sets A = [a] = {a' such that a' ≡ a mod n}. That is, set addition defines the same operation on congruence classes as [a] + [b] = [a+b].
   2. Does a similar definiton of set multiplication agree with the previous definition of clock multiplication? Be careful.

• The reciprocal or multiplicative inverse of an element [a] ∈ Z_n means any solution x ∈ Z_n to [a]x = [1]. There is at most one such inverse, denoted by [a]⁻¹.
  Proof: We show [a]⁻¹ is unique. If we have two reciprocals [b],[c] with [a][b] = [a][c] = [1], then:
  [b]  =  [b]·[1]  =  [b][a][c]  =  [1]·[c]  =  [c].
  Thus, the two reciprocals are the same.
• Theorem: For [a] ∈ Z_n we have either:
  1.  gcd(a,n) = 1 and [a]⁻¹ exists (i.e. [a]⁻¹ = [b] ∈ Z_n with [a][b] = [1]); or
  2.  gcd(a,n) = d > 1 and [a] is a zero-divisor (i.e. there is [0] ≠ [e] ∈ Z_n with [a][e] = [0]), and [a] has no reciprocal.
  Proof: (i) As in Notes 9/14, if gcd(a,n) = 1, then the Extended Euclidean Algorithm gives as + nt = 1, so [a][s] = [as] + [nt] = [as + nt] = [1], and [a]⁻¹ = [s].
  (ii) Suppose gcd(a,n) = d > 1. Then d is a divisor of n, so we have an integer e = ⁿ⁄_d ∈ Z. Since n ≥ d > 1, we have 1 ≤ e < n, so [e] ≠ [0]. Also, d is a divisor of a, so a = cd. Thus:
  [a][e]  =  [cd·ⁿ⁄_d]  =  [cn]  =  [0],
  and [a] is a zero-divisor.
  If this [a] had a reciprocal [a]⁻¹, we would have:
  [e]  =  [a]⁻¹[a][e]  =  [a]⁻¹[0]  =  [0],
  which contradicts [e] ≠ [0]. Therefore [a] could not have a reciprocal.
• Corollary: Let p be prime. In Z_p, we have:
  1. The inverse [a]⁻¹ exists for all [a] ≠ [0].
  2. If [a][b] = [0], then [a] = 0 or [b] = [0].
  3. If [a] = [a]⁻¹, then [a] = [1] or [−1].
• Quadratic Formula: Let p ≠ 2 be a prime. Consider the quadratic equation:
  ax² + bx + c  =  0,
  with coefficients a,b,c ∈ Z_p, a ≠ 0, and an unknown solution x ∈ Z_p.
  An element d ∈ Z_p with d² = b²−4ac is denoted d = √(b²−4ac).
  • If there is no √(b²−4ac) ∈ Z_n then there is no solution x to the quadratic equation.
  • If there is √(b²−4ac) ∈ Z_n, then the solutions to the quadratic equation are exactly:
    x  =  (−b ± √(b² − 4ac)) (2a)⁻¹

• Wilson's Theorem: Let p be prime. Then p | (p−1)! + 1 .
  Proof: The conclusion is equivalent to [(p−1)!] = [−1] in Z_p.
  Now, [(p−1)!] = [1] [2] [3] ··· [p−1] is the product of all the non-zero elements of Z_p. By Corollary (a), every factor [a] in this product has an inverse [a]⁻¹ also in the product, cancelling it. The only factors which do not cancel are those with [a]⁻¹ = [a]; and by Corollary (c), this happens only for the first factor [1] and the last factor [p−1] = [−1]. Thus [(p−1)!] = [1] [−1] = [−1], which means p | ( (p−1)! − (−1) ) = (p−1)! + 1.

Reading: Ch 2.3, pp. 37-41.
HW:

1. Consider the modular arithmetic system Z₅ = {[0],[1],[2],[3],[4]}. For convenience, we will drop the brackets [ ] in the notation, so that 1 really means [1], etc.
   1. Write the addition and multiplication tables for Z₅.
   2. In Z₅, expand the binomial power (a+b)^k for k = 2,3,4,5. Something surprising happens for k = 5.
      Example: (a+b)² = a(a+b) + b(a+b) = a² + ab + ba + b² = a² + 2ab + b². Remember that the coefficients are in Z₅, so this might also be written as a² − 3ab + b², since 2 = −3 (meaning [2] = [−3]). Find the simplest form. For higher powers, note that (a+b)³ = (a+b)²(a+b) = (a²+2ab+b²)(a+b).
   3. In Z₅, show that (a−b)(a+b) = a² − b². Justify the steps using the algebraic properties of Z₅ (mainly distributivity).
   4. Find the reciprocal a⁻¹ for each a ≠ 0.
   5. Solve the following equation in Z₅: (2x−1) / (3x+2) = 2. Use the same techniques as in usual algebra, justifying by the algebraic properties, and check that the final answer really works.
   6. Which elements of Z₅ have square roots in Z₅? That is, for which a can we solve the equation x² = a for x ∈ Z₅ ? If there is one solution x, is −x also a solution? Surprisingly, we can solve x² = −1. How?
   7. Solve the equation 3x²+x+1 = 0 using the quadratic formula, and check that the solutions really do work.
   8. In Z₅, is it true that xy = 0 only if x = 0 or y = 0?
2. Try all the above for Z₆ and/or Z₉.
3. Equations in Z₂₉, where p = 29 is prime.
   1. In Z₂₉, use the Euclidean algorithm to find the reciprocal 5⁻¹.
   2. Solve the equation: 2x + 1 = −3x + 4 for x ∈ Z₂₉.

Soln: 1a.

+	0	1	2	3	4
0	0	1	2	3	4
1	1	2	3	4	0
2	2	3	4	0	1
3	3	4	0	1	2
4	4	0	1	2	3

•	0	1	2	3	4
0	0	0	0	0	0
1	0	1	2	3	4
2	0	2	4	1	3
3	0	3	1	4	2
4	0	4	3	2	1

1b. (a+b)² = a² + 2ab + b² ; (a+b)³ = a³ + 3a²b + 3ab² + b³ ;
(a+b)⁴  =  a⁴ + 4a³b + 6a²b² + 4ab³ + b⁴  =  a⁴ − a³b + a²b² − ab³ + b⁴ ;
(a+b)⁵  =  a⁵ + 5a⁴b + 10a³b² + 10a²b³ + 5ab⁴ + b⁵  =  a⁵ + b⁵ (!)
That is, (a+b)⁵ = a⁵ + b⁵ for a,b ∈ Z₅.

1c. (a−b)(a+b) = a(a+b) − b(a+b) = a·a + a·b − b·a − b·b = a² + a·b − a·b − b² = a² − b² .

1d. The mulitplication table has a single 1 in each row (except the row for mult by 0). This means precisely that each a ≠ 0 has a unique a⁻¹.

1e. (2x − 1) / (3x + 2) = 2  ⇔  2x − 1 = 2 (3x + 2)  ⇔  4x = −5 = 0  ⇔  x = 4⁻¹0 = 0 (unique solution).
Check: x = 0 plugs into the equation: (2(0) − 1)/(3(0) + 2) = (−1)/(2) = (4)(2⁻¹) = (4)(3) = 2

1f. Taking 0²,...,4², we find only 0, 1, and 4 = −1 have square roots.
If x² = a, then (−x)² = (−1)²x² = 1(x²) = a, so −x is also a square root.

1g. x = ( −b±√(b²−4ac) ) / 2a = ( −1 ± √(1−4(3)(1)) ) / 2(3) = ( −1 ± √(4) ) / 1 = (−1 ± 2), i.e. x = 1 or x = −3 = 2. We can verify the solutions by plugging them into the original quadratic equation.

1h. There is no 0 in any row of the mulitplication table, except in the row and column of multiplication by 0. Thus ab = 0 only for a = 0 or b = 0.

2. Z₆ has no reciprocals except 1⁻¹ = 1 and −1⁻¹ = −1. Also (2)(3) = 6 = 0. Equation (e) has no solution, and the Quadratic Formula does not work for equation (g) because the denominator 2a = 6 = 0, so it has no reciprocal and it is not meaningful to divide by it. Similarly for Z₉.

3a. The Extended Euclidean Algorithm gives 29 = 5·5 + 4 , 5 = 4 + 1, so that:

1  =  5 − 4  =  5 − (29 − 5·5)  =  6·5 − 29.

Thus 6·5 ≡ 1 mod 29, and 5⁻¹ = 6 ∈ Z₂₉.

3b. Solve 2x + 1 = −3x + 4 as usual for a linear equation, obtaining:

x  =  3/5  =  3·5⁻¹ = 3·6 = 18.

Plugging x = 18 into the original equation gives: 2·18 + 1 = 37 = 8, while −3·18 + 4 = −50 = 8, so the equation holds.
This is the unique solution, because the algebra leading from the equation to x = 3·5⁻¹ leaves no other possibilities.

1. Hand In Mon 9/24: A unit is an element [a] which has a reciprocal [a]⁻¹. A zero-divisor is an element [a] ≠ [0] which multiplies to give zero: [a][e] = [0] for some [e] ≠ 0.
   For each statement below, prove that it holds for all a,b,n ∈ Z, or find some counter-example where it does not hold. Rely only on definitions and properties of Z and Z_n which we have covered (see Notes 9/17, also 9/12, 9/14).
   1. If [a],[b] ∈ Z_n are units, then their product [a][b] is also a unit.
   2. If [a],[b] ∈ Z_n are units, then their sum [a] + [b] is also a unit.
   3. If [a],[b] ∈ Z_n with [a] a zero-divisor, then the product [a][b] is also a zero-divisor or it is zero.
   4. If [a],[b] ∈ Z_n are zero-divisors, then their sum [a] + [b] is also a zero-divisor.
2. Extra Credit. Proposition: For any integer a and prime p, we have a^p ≡ a (mod p), or equivalently a^p = a ∈ Z_p. (We will again denote the clock integer a ∈ Z_p by just a, relying on the context to distinguish it from the ordinary integer a ∈ Z.)
   Prove this using the following steps.
   1. Let a ∈ G = {1, 2, . . . , p−1} ⊂ Z_p, and H = {1, a, a², . . . } ⊂ G. Show that H = {1, a, a², . . . , a^k−1} for some k > 0 with a^k = 1 ∈ Z_p, so that the number of elements of H is #H = k.
   2. For b ∈ Z_p, define the coset bH = { bh for h ∈ H }. Show that #bH = #H.
   3. Show that for b,c ∈ Z_p, the cosets bH and cH are the same set, or they are disjoint (no intersection): either bH = cH or bH ∩ cH = {}.
   4. Show that G = b₁H ∪ ··· ∪ b_ℓH for some b₁, . . . , b_ℓ ∈ G, and conclude that p−1 = kℓ
   5. Finally, conclude that a^p−1 = 1 for any a ∈ G, and a^p = a for any a ∈ Z_p.

• Basic properties of a number system R which make algebra work.
  Let a,b,c be any elements of R.
  • Addition Closed:     a+b ∈ R
  • Associative:   (a+b)+c = a+(b+c)
  • Commutative:    a+b = b+a
  • Zero:   0 ∈ R   with   a+0 = 0+a = a
  • Negatives:   there is   −a ∈ R   with   a+(−a) = (−a)+a = 0
  • Multiplication Closed:     a·b = ab ∈ R
  • Associative:    (ab)c = a(bc)
  • Commutative:     ab = ba
  • One:   1 ∈ R   with   a1 = 1a = a
  • Reciprocals:   for a ≠ 0, there is   a⁻¹ ∈ R   with   aa⁻¹ = 1
  • Distributive:   a(b+c) = ab + ac   and   (b+c)a = ba + ca.
• A field is a number system with all the above properties.
• A ring (with identity) is a number system with all the properties except multiplication might not be commutative and might not have reciprocals. (Thus, any field is automatically a ring.)
• Examples of fields
  • rational numbers Q
  • real numbers R
  • complex numbers C
  • clock numbers with prime modulus Z_p
  • set of all functions f(x) on the real line (possibly zero or undefined only at isolated points), under addition and multiplication of functions (as in calculus)
• Examples of rings which are not fields
  • integers Z (missing reciprocals)
  • clock numbers with non-prime modulus Z_n (missing some reciprocals)
  • set of all functions f(x) defined everywhere on the real line (missing reciprocals, since ¹⁄_f(x) is not defined at points where f(x) = 0, so ¹⁄_f(x) is not in the ring)
  • set of all 2×2 matrices (or square matrices of any size) under term-by-term addition and matrix multiplication (missing commutativity and some reciprocals)

Reading: Ch 3.1, pp. 43-53.    
HW:

1. Check all the properties directly for the ring of 2×2 matrices. Associativity is not obvious. When does a matrix have a reciprocal?
2. Which of the properties holds for the vector space R³ under vector addition and cross-product multiplication? Does this form a ring?

1. Check the properties on generic matrices whose entries are a,b,c, . . . . A matrix has a reciprocal whenever it is non-singular, i.e. when its determinant is non-zero.

2. Vector addition satisfies the first five properties. Cross product multiplication is closed, and the distributive law holds. However, multiplication is not commutative since v×w = −w×v; not associative since i×(i×j) = i×k = −j, but (i×i)×j = 0×j = 0; there is no identity vector; and there are no reciprocals since the equation v×w = 1 does not even make sense.

Let R denote an arbitrary ring, and a,b,c arbitrary elements. We define subtraction and division by a−b = a+(−b) and a/b = ab⁻¹.
• Thm 3.3 p. 60:
  • Any a ∈ R has only one negative  −a ∈ R.
  • Any a ∈ R has at most one reciprocal a⁻¹ ∈ R.

  Proof Statement	Justification
  Suppose a+b = 0, a+c = 0.	Hypothesis
  Then b = 0+b,	Zero axiom
  b = (a+c)+b,	Substitution
  b = (c+a)+b,	Commutative axiom
  b = c+(a+b),	Associative axiom
  b = c+0,	Hypothesis
  b = c.	Zero axiom
  Therefore −a is unique.	Conclusion

  The proof of unique reciprocals is identical, with multiplication instead of addition, 1 instead of 0.
• Thm 3.5: For any a,b ∈ R, we have:
  1. a0 = 0.
  2. a(−b) = −(ab)
  3. −(−a) = a
  4. −(a+b) = (−a) + (−b)
  5. −(a−b) = b−a
  Proof of (1). The hypothesis here is that a ∈ R, a ring satisfying the defining axioms.

  Statement	Justification
  a0  =  a(0+0)	Zero axiom
  a0  =  a0 + a0	Distributive axiom
  a0 − a0  =  a0 + a0 − a0	Substitution
  0  =  a0 + 0  =  a0	Negative & Zero axioms

• Note: From now on, I will give less detail in proofs, assuming you can fill in the details. In particular, I will take associativity for granted, and just write a+b+c, abc, etc.
• A unit or invertible element of a ring R is an element u ∈ R which has an inverse u⁻¹ ∈ R, so that uu⁻¹ = 1.
  A zero-divisor is a non-zero element z ∈ R which multiplies by some non-zero element w ∈ R to give zero: zw = 0 for z,w ≠ 0.
• Thm: If a,b are units, then ab is also a unit.
  Proof: Given a⁻¹, b⁻¹ ∈ R by hypothesis, let c = b⁻¹a⁻¹. Then:
  (ab)c = abb⁻¹a⁻¹ = a1a⁻¹ = aa⁻¹ = 1.
  Therefore c = (ab)⁻¹. Note this holds even if multiplication in R is not commutative.
• A subring S of a given ring R is a subset which is itself a ring, with the identity 1 ∈ S the same as 1 ∈ R. Indeed, we only have to check that the subset S is closed under addition, multiplication, and taking negatives. (See Thm 3.6.)

Reading: Ch 3.2, pp. 59-66.    
HW:

1. Prove Thm 3.5(6): (−a)(−b) = ab. Your proof should use only the ring axioms and the previous results in the Notes above.
2. Prove that if we have two subrings S,T ⊂ R, then the intersection S∩T is also a subring.
3. Hand In Mon 10/1: For each of the following rings, find all the units and the zero-divisors: integers Z, rationals Q, reals R, clock arithmetic Z_n,   2×2 matrices M(R). Also, for an arbitrary R with known units and zero-divisors, what are the units and zero divisors of the product ring R×R.
4. Hand In Mon 10/1: Let R = M₂(R) be the ring of 2×2 matrices with real number entries.
   Claim: For any matrices A,B ∈ R, we have:
   (A+B) (A−B)   =   A² − B².
   1. Find a counter-example to the claim: give specific matrices for which the formula is false.
   2. Write out the usual algebra proof of the Claim in the case of real numbers, in two-column format with justifications.
   3. State exactly where the proof in (b) breaks down in the case of matrices. What axioms are missing to make the proof invalid?

1. See [H] p. 62.

2. Check that S∩T is closed under addition, multiplication, and negatives. These follow from the corresponding facts for the subrings S and T.

• Product ring R × S: operations (a,b)+(c,d) = (a+c,b+d), (a,b)(c,d) = (ac,bd).
• Matrix ring M₂(R), where R is any commutative ring. Upper triangular subring.
• Formal definition of complex number field C. (See Ch 3.1 Ex 45 p 59). We write a complex number equivalently as a pair (a,b) ∈ R² or as a linear combination a+b√(−1) = a+bi, where the traditional letter i denotes the square root of −1. Define the operations as:
  (a,b) + (c,d)  =  (a+c, b+d)         (a,b)(c,d)  =  (ac−bd, ad+bc).
  These are the same formulas we derived in class, from thinking of (a,b) as a+bi and applying the distributive law along with i² = −1. Note that i = 0+1i = (0,1), and i² = (0,1)(0,1) = (−1,0) = −1+0i = −1. For reciprocals, recall the trick of rationalizing the denominator:
  ¹⁄_a+bi   =   ¹⁄_a+bi · ^a−bi⁄_a−bi   =   ^a−bi⁄_a²+b²   =   (^a⁄_a²+b²) − (^b⁄_a²+b²) i.

Reading: Ch 3.1, Examples 6,7,11,13, Thm 3.1 pp 47-51.    
HW:

1. Hand In Mon 10/1: Carefully check all the field axioms for the above definition of C. (These axioms are all we need to ensure that all standard algebra works in C.)
2. Extra Credit: Geometry of complex numbers.

Reading: Ch 2.3, pp. 37-41.    
HW:

1. An example of isomorphism. Let R = Z₆ and S = Z₂×Z₃. Then define f : R → S by f([a]₆) = ([a]₂,[a]₃), where [a]_n means a class in Z_n. (For convenience, I will sometimes drop the brackets and just write f(a) = (a,a).) This is clearly one-to-one and onto since: f(0) = (0,0) , f(1) = (1,1) , f(2) = (0,2)
   f(3) = (1,0) , f(4) = (0,1) , f(5) = (1,2). Furthermore, f is clearly a homomorphism, since:
   f([a+b]₆) = ([a+b]₂, [a+b]₃) = ([a]₂,[a]₃) + ([b]₂,[b]₃) = f(a) + f(b),
   and similarly for f(ab) = f(a)f(b).
   Exercise: Write the + and × tables of R. Now replace each entry a with f(a), not bothering with brackets(!), and verify that you have produced the + and × tables of S. This is the case-by-case verification that f(a+b) = f(a) + f(b) and f(ab) = f(a)f(b).
2. Hand In Mon 10/8: An example of non-isomorphic rings. Let R = Z₄ and S = Z₂×Z₂.
   • If there were an isomorphism f : R → S, then f would turn the + and × tables of R into those of S, and every algebraic property of R would also hold in S.
   • We would have f(a) + f(0_R) = f(a+0_R) = f(a), so f(0_R) = 0_S. Similarly f(1_R) = 1_S; and every unit in R goes to a unit in S; and the same for zero-divisors.
   • But R consists of 0_R, two units, and one zero-divisor; whereas S consists of 0_S, one unit, and two zero-divisors. There could not possibly be a mapping which turns the multiplication table of R into that of S.
   • Another way the + tables of R and S differ: In S we have a+a = 0_S for all a ∈ S. In R, we have 1+1 ≠ 0_R. If there were an isomorphism, we would have f(1+1) = f(1) + f(1) = 0_S, and f(0_R) = 0_S, so f would not be one-to-one. Again: no possible isomorphism.
   Exercise: For the following pairs of rings R,S, either give an isomophism f : R → S as in (1), or show as above that no isomorphism is possible.
   1. R = Z₁₂ , S = Z₃×Z₄
   2. R = Z₁₂ , S = Z₂×Z₆
   3. R = Z₂×Z₆ , S = Z₂×Z₂×Z₃
   4. R = C, complex numbers; S = R×R, product ring of real numbers with (a,b)(c,d) = (ac,bd)
   Hints:
   • To show isomorphism, you do not need to write out the whole addition and multiplication tables. Rather, use formulas to show f(a+b) = f(a) + f(b) and f(ab) = f(a)f(b), as I did in (1) above.
   • To show non-isomorphism, it is not enough that your guess for f does not work. You must show that the operations of R and S are basically different, and there is no possible correspondence, as I did above.

• Proposition: If d is a divisor of n, then there is a homomorphism f : Z_n → Z_d defined by f([a]_n) = [a]_d. (Here [a]_n means the clock number [a] ∈ Z_n.)
  Proof: It is immediately clear why f respects addition and multiplication: f(a+b) = f(a) + f(b), f(ab) = f(a)f(b). The subtle issue is whether the mapping is well-defined. That is, if we have two forms of the input class, [a]_n = [a']_n, then a' = a + nt = a + dst, where n = ds; and f gives the same output when applied to either form of the input:
  f([a']_n)  =  [a']_d  =  [a+dst]_d  =  [a]_d  =  f([a]_n).

• Chinese Remainder Theorem: Consider two relatively prime integers, gcd(n,m) = 1. Then:
  1. For any a,b ∈ Z, there is some c ∈ Z such that  c ≡ a mod n  and  c ≡ b mod m.
  2. The mapping f : Z_nm → Z_n × Z_m given by f([a]_nm) = ([a]_n, [a]_m) is an isomorphism.
  We may visualize part (i) by marking two times (a and b o'clock) on an n-hour clock and an m-hour clock; starting the two clocks at 0 and letting them for c hours, they will reach the two marked hours simultaneously.
  Proof: (i)  Since gcd(n,m) = 1, the Extended Euclidean Algorithm gives ns + mt = 1. Take e₁ = mt = 1 − ns and e₂ = ns = 1 − mt. Then clearly:
  e₁ ≡ 1 mod n , e₁ ≡ 0 mod m     and     e₂ ≡ 0 mod n , e₂ ≡ 1 mod m.
  Now take c = ae₁ + be₂, so that:
  c   ≡   a·1 + b·0   ≡   a mod n,     and     c   ≡   a·0 + b·1   ≡   b mod m.
  (ii)  It is clear f is a homomorphism from the previous Proposition, so it remains to show f is one-to-one and onto. The one-to-one part is an exercise below. To show f is onto, we must show that any ([a]_n, [b]_m) ∈ Z_n × Z_m is hit by some [c]_nm ∈ Z_nm. That is, we need some c ∈ Z such that
  f([c]_nm)   =   ([c]_n, [c]_m)   =   ([a]_n, [b]_m).
  But this is given precisely by the c from part (i).
  Note: Both the input and output sets of f have nm elements, so if f is onto, then it must be one-to-one, and we do not really need to prove this separately.

Reading: Ch 14.1, pp. 443-448.    
HW:

1. Chinese Remainder Theorem.
   1. Use the Chinese Remainder Theorem (and its proof involving the Euclidean Algorithm) to find c such that c ≡ 13 mod 21 and c ≡ 7 mod 8.
   2. For the isomorphism f : Z_21·8 → Z₂₁ × Z₈, find the element c ∈ Z_21·8 with f(c) = (13, 7).
   3. Give a general formula for the inverse mapping f⁻¹ : Z₂₁ × Z₈ → Z_21·8 which reverses f. That is, given (a,b), we define f⁻¹(a,b) = c, the input of f which produces f(c) = (a,b).
2. Properties of isomorphisms. Let R,S be rings.
   1. Prove that if f : R → S is an isomorphism, then f respects all the algebraic structures of R and S:
      1. f(0_R) = 0_S
      2. f(1_R) = 1_S
      3. f(−a) = −f(a)
      4. If a is a unit, then f(a⁻¹) = f(a)⁻¹.
      5. If R is a field, then S is a field.
      Hint: Show that f(0) obeys the zero axiom in S, so it must be the unique zero-element. Similarly for the other properties. Be careful to explicitly use the one-to-one and/or onto property when needed.
   2. Which of these must be true for a homomorphism f : R → S?
3. Extra Credit: Prove directly that the homomorphism in the Chinese Remainder Theorem (ii) is one-to-one. Use our previous results on divisibility and factorization.
4. Extra Credit: Using the Chinese Remainder Theorem (ii) you can factor any Z_k into products of smaller rings. How far can you factor? What are the "primes" in this situation?

1. We are looking for an integer c such that c ≡ 13 mod 21 and c ≡ 7 mod 8. Applying the Euclidean Algorithm to the moduli 21 and 8 gives: 21 = 2·8 + 5 , 8 = 1·5 + 3 , 5 = 1·3 + 2 , 3 = 1·2 + 1. Then the Extended Euclidean Algorithm gives: 1 = 3 − 2 , 2 = 5 − 3 , 3 = 8 − 5 , 5 = 21 − 2·8, which works back to:

1  =  −3·21 + 8·8.

Now taking e₁ = 8·8 = 1 + 3·21 = 64 and e₂ = −3·21 = 1 − 8·8 = −63 gives:

e₁ ≡ 1 mod 21 , e₁ ≡ 0 mod 8
e₂ ≡ 0 mod 21 , e₂ ≡ 1 mod 8.

Therefore,

c  =  13e₁ + 7e₂  =  13·64 + 7·(−63)  =  391  ≡  55 mod 168,

where 168 = 21·8. Check: 55 = 2·21 + 13 and 55 = 6·8 + 7.

2. Claim (i): A homomorphism f : R → S takes f(0_R) = 0_S.
Proof: We have:

f(0_R)  =  f(0_R+0_R)  =  f(0_R) + f(0_R).

Subtracting f(0_R) from both sides gives 0_S = f(0_R).

Claim (ii): An isomorphism f : R → S takes f(1_R) = 1_S.
Proof: Since f is onto, for any s ∈ S we can find r ∈ R with f(r) = s. Then:

s·f(1_R)  =  f(r)·f(1_R)  =  f(r·1_R)  =  f(r)  =  s.

That is, multiplying by f(1_R) has no effect on any s ∈ S, so f(1_R) is an identity element of S (Identity Axiom). But we previously proved that the identity element is unique, so f(1_R) = 1_S.

Claim (iii): A homomorphism f : R → S takes f(−a) = −f(a).
Proof: We have: Then:

f(a) + f(−a)  =  f(a+(−a))  =  f(0_R)  =  0_S,

by the previous Claim. Thus f(−a) cancels f(a) in S, meaning f(−a) is a negative of f(a) (Negative Axiom). But we previously proved that negatives are unique, so f(−a) = −f(a).

The other claims are proved similarly.

Claims (ii), (iv), (v) require f : R → S to be an isomorphism, not just a homomorphism, as can be seen from the homomorphism f : R → R×R, f(a) = (a,0). Then f(1) = (1,0) ≠ (1,1) = 1_S; also f(a) = (a,0) is a zero-divisor, so f(a)⁻¹ will never exist; and the domain (input ring) is a field but the codomain (output ring) is not.

• A polynomial is a function:
  f(x)  =  a_nxⁿ + a_n−1xⁿ⁻¹ + · · · + a₂x² + a₁x + a₀,
  having coefficients a_i in any given field F, such as Q, R, or Z_p. The leading coefficient is assumed non-zero: a_n ≠ 0 (unless f(x) = 0, the zero constant function).
• The degree of f(x) is deg f(x) = n, the largest power of x appearing in f(x). Specially, the degree of the zero constant function f(x) = 0 is undefined.
• Degree 0 polynomials are constants f(x) = a₀. Degree 1 is called linear, degree 2 quadratic, degree 3 cubic.
• The degree of a product of nonzero polynomials is the sum of their degrees:
  deg f(x)g(x)  =  deg f(x) + deg g(x).
  Indeed, if the highest term of f(x) is a_nxⁿ, and the highest term of g(x) is b_mx^m, then the highest term of f(x)g(x) is a_nxⁿb_mx^m = a_nb_mx^n+m.
• We work with the polynomial ring F[x], the set of all polynomials with the usual operations of addition and multiplication of functions. These are easily checked to satisfy the axioms of a commutative ring.
  (For example, we write R[x] if F = R, the real number field.)
• The polynomials F[x] are strongly analogous to the integers Z, with the coefficients of a polynomial corresponding to the digits of an integer in the usual base-ten notation. In fact, base-ten notation means we write a positive integer a as:
  a  =  a_n10ⁿ + a_n−110ⁿ⁻¹ + · · · + a₂10² + a₁10 + a₀     for     a_i ∈ {0,1,2, . . . ,9},
  meaning a = f(10) for a corresponding polynomial f(x). (Note: This analogy does not amount to an isomorphism or homomorphism.)
• The key property which F[x] shares with Z is the division-with-remainder algorithm. For any a(x),b(x) ∈ F[x], we can compute quotient and remainder polynomials q(x), r(x) ∈ F[x] with
  a(x)  =  q(x)b(x) + r(x)     with     deg r(x) < deg b(x)     or    r(x) = 0.
  It is crucial that the remainder r(x) has strictly smaller degree than the divisor b(x), just as in Z, the remainder in a = qb + r has absolute value strictly smaller than the divisor: |r| < |b|.
• We shall see that all the theory of divisibility and primes for Z carries over to F[x], using the same Euclidean Algorithm arguments.

Reading: Polynomial Division Ch 4.1, pp. 86-92; tutorial, video, Khan Academy practice.
      Polynomial Euclidean Algorithm. Ch 4.2 Divisibility pp. 95-99.    
HW:

1. Prove that the units (elements with reciprocals) in F[x] are precisely the nonzero constant polynomials f(x) = u. Also, there are never any zero-divisors in F[x]. Hint: Use the fact that deg f(x)g(x) = deg f(x) + deg g(x).
2. Hand In Mon 10/8: Perform the Extended Euclidean Algorithm for the polynomials in [H] Ch 4.2 #5(a) p. 99:
   a(x) = x⁴ − x³ − x² + 1     and     b(x) = x³ − 1.
   Compute d(x) = gcd(a(x),b(x)) and write d(x) = f(x)a(x) + g(x)b(x) for polynomials f(x),g(x) ∈ Q[x]. You should do your computations by hand, but you can check them with Wolfram Alpha.

1. Proposition:

1. The units in the polynomial ring F[x] are the constant functions f(x) = u ∈ F.
2. The polynomial ring has no zero-divisors.

Proof: (a) Suppose f(x) is a unit, so that there is g(x) with f(x)g(x) = 1 ∈ F[x]. Letting

f(x)  =  a_nxⁿ + · · · + a₁x + a₀,         g(x)  =  b_mx^m + · · · + b₁x + b₀,

with highest coefficients a_n, b_m ≠ 0, we see the highest non-zero term in f(x)g(x) is a_nb_mx^n+m. Since f(x)g(x) = 1 = 1x⁰, we must have n + m = 0, but since n,m ≥ 0, this means n = m = 0. That is, f(x),g(x) both have degree zero, meaning they are constant functions, f(x) = a₀ = u, and g(x) = b₀ = ¹⁄_u.

(b) Assume f(x) multiplies to zero, meaning there is some g(x) ≠ 0 with f(x)g(x) = 0. (Here 0 means the zero constant function.) If we also had f(x) ≠ 0, we could multiply as above to find f(x)g(x) has highest term a_nb_mx^n+m with a_nb_m ≠ 0. But f(x)g(x) = 0 = 0x⁰ has no non-zero terms. This contradiction shows we could not have f(x) ≠ 0 with f(x)g(x) = 0, so there are no zero-divisors.

• Almost all theorems about the ring of integers Z have close analogs for the ring of polynomials F[x] with coefficients in a given field F. The basic reason is that the size |n| for integers corresponds to the degree deg f(x) for polynomials.
• The Division Algorithm for integers a ÷ b produces remainder with 0 ≤ r < b, so |r| < |b|; correspondingly, the Division Algorithm for a(x) ÷ b(x) produces remainder with deg r(x) < deg b(x) or r(x) = 0.
• In Z, the units are the smallest non-zero elements n = ±1 with |n| = 1, and there are no zero-divisors. Correspondingly in F[x], the units are the smallest non-zero polynomials, constant polyomials f(x) = u with deg f(x) = 0, and again there are no zero-divisors.
• For Z, divisibility a | b is equivalent to ±a | b; correspondingly for F[x], divisibility a(x) | b(x) is equivalent to u a(x) | b(x).
• Since the division algorithm works for F[x], so does the Euclidean Algorithm for finding the greatest common denominator d(x) = gcd(a(x),b(x)) and the Extended Euclidean Algorithm for writing d(x) = f(x)a(x) + g(x)b(x).
• Prime numbers p ∈ Z, with no factors other than ±p and ±1, correspond to irreducible polynomials p(x), with no factors other than u p(x) and constant u.
• The Prime Divisibility Property for a prime p ∈ Z says that if p | ab, then p | a or p| b. Correspondingly, for irreducible p(x) ∈ F[x], if p(x) | a(x)b(x), then p(x) | a(x) or p(x) | b(x). For both, the proof uses the Extended Euclidean Algorithm.
• The Fundamental Theorem of Arithmetic for Z says that any integer can be factored into primes in only one way, unique except for reordering factors and changing signs. Correspondingly, the Unique Factorization Theorem for F[x] says that any polynomial can be factored into irreducibles in only one way, unique except for reordering factors and multiplying by non-zero constants.
  For both, the proof uses the Prime Divisibility Property.
• Linear Factor Theorem: For a polynomial f(x) ∈ F[x] and number a ∈ F, x−a is a divisor of f(x) if and only if a is a root of f(x), meaning f(a) = 0.
  Proof: This is a fact with no analog in Z, but its proof still hinges on the Division Algorithm. For any f(x) ∈ F[x] and a ∈ F, we can divide to get f(x) = q(x)(x−a) + r(x) with deg r(x) < deg (x−a) = 1 or r(x) = 0, meaning deg r(x) = 0 and r(x) = c a constant polynomial. Thus f(a) = q(a)(a−a) + c = c; that is, r(x) = f(a). Now it is clear that (x−a) | f(x) ⇔ r(x) = 0 ⇔ f(a) = 0.

Reading: Ch 4.3, pp. 100-103. Ch 4.4, pp. 105-109.    
HW:

1. Factor f(x) = x⁴ − 4 into irreducibles in Q[x], R[x], and C[x].
2. For the results below, go back in the HW above to find the corresponding fact about integers Z, and adapt its proof to polynomials.
   1. Proposition: In F[x], if f(x) | g(x) and g(x) | f(x), then f(x) = u g(x) for a non-zero constant u.
   2. If d(x) | a(x), d(x) | b(x), and d(x) = f(x)a(x) + g(x)b(x), then d(x) is the greatest common divisor of a(x),b(x), meaning that any common divisor c(x) is also a divisor of d(x). (See [H] Ch 1.2.)
   3. Even if F is a finite field, such as F = Z₂, the polynomial ring F[x] has infinitely many irreducible polynomials. In fact, given a list p₁(x), . . . , p_k(x), there is an algorithm to produce more irreducibles not on the list. Starting with the degree-one polynomials x, x−1 ∈ Z₂[x], use this algorithm to produce a irreducibles of degree 2 and 3. (Use the Linear Factor Theorem to check irreducibility.)

1. x⁴ − 4 factors as (x²−2)(x²+2) in Q[x], as (x−√2)(x+√2)(x²+2) in R[x], and as (x−√2)(x+√2)(x−i√2)(x+i√2) in C[x].

2a. See Hand-In HW 8/31 #4. If f(x) = h(x)g(x) and g(x) = k(x)f(x), then f(x) = f(x)h(x)k(x) and 1 = h(x)k(x), so h(x),k(x) are units in F[x]. But the only such units are non-zero constants, so h(x) = u and f(x) = u g(x).

2b. [H] Corollary 1.3 Step 1, p. 13. Suppose that d(x) = f(x)a(x) + g(x)b(x). If c(x) is a common divisor with c(x) | a(x) and c(x) | b(x), then c(x) also divides the linear combination f(x)a(x) + g(x)b(x) = d(x). That is, c(x) | d(x).

2c. Euclid's Prime Algorithm, HW 9/7 #1. To get new irreducible polynomials, take

q(x)  =  p₁(x)···p_k(x) + 1.

If we had p_i(x) | q(x), then p_i(x) would also divide the linear combination q(x) − p₁(x)···p_k(x) = 1, i.e. p_i(x) | 1. But the only divisors of 1 are units f(x) = u, which are not irreducibles. This contradiction shows p_i(x) ∤ q(x), so the irreducible factors of q(x) are new irreducible polynomials.

Example: In Z₂[x], p₁(x) = x , p₂(x) = x−1 = x+1 are irreducible, since they are non-units of minimal degree (any non-trivial factors would have degree less than one). Thus q(x) = x(x+1) + 1 = x² + x + 1 has irreducible factors different from x, x−1. But any non-trivial factor would have degree 1, and x, x+1 are the only such in Z₂[x], so q(x) is irreducible.

Taking the Algorithm one step further in Z₂[x]:

q(x)  =  x(x+1)(x²+x+1) + 1  =  x⁴ + 2x³ + 2x² + x + 1  =  x⁴ + x + 1 .

Any non-trivial irreducible factors would have degrees 1+3, 1+1+2, 1+1+1+1, or 2+2. In the first three cases, at least one factor would be linear, x or x+1, but these are not factors. In the second case, the only irreducible of degree 2 is x²+x+1 (there are only 4 polynomials of deg 2, and the others clearly factor). Thus, q(x) has no non-trivial factors and is irreducible.

• The Midterm Exam (Mon 10/15 in class) will cover all the sections in Ch 1.1−4.4. The key facts are mostly covered in the Quizzes, and questions will be similar.
• Chapter 1. Divisibility in integers Z
  • Extended Euclidean Algorithm for integers Z
    For a,b ∈ Z, produce s,t ∈ Z with sa + tb = gcd(a,b).
  • Divisibility and primes
    Definition:  c | a means a = bc for c ∈ Z
    Basic property:  c | a and c | b ⇒ c | sa + tb
  • Prime Divisibility Property: If prime p | ab, then p | a or p | b.
    Proof:  If p | ab, but p ∤ a, then gcd(p,a) = 1 = sa + tp, and p | sab + tpb = b.
  • Fundamental Theorem of Arithmetic: Factorization into primes is unique.
  • Square roots are irrational.
    Proof: Imagine a rational square root, compare prime powers in factorizations.
  • Euclid's Prime Algorithm to produce new primes:
    q = p₁p₂···p_k + 1 has prime factors different from p₁, p₂, . . . , p_k.
• Chapter 2. Modular arithmetic
  • Z_n = {[0], [1], . . . , [n−1]} with clock add, mult
  • Definition:  [a] = {. . . , a−n, a, a+n, a+2n, . . . } ⊂ Z
  • Modular equivalence:  a ≡ b mod n  means equivalently:
    • a = b + nk for k ∈ Z
    • n | a − b
    • a = q₁n + r₁, b = q₂n + r₂  with r₁ = r₂
    • [a] = [b] ∈ Z_n
  • Modular Reciprocal Theorem:  [a] ∈ Z_n has reciprocal [a]⁻¹ = [b] ∈ Z_n ⇔ gcd(a,n) = 1.
    Proof: (⇐) If gcd(a,n) = 1 = as + nt, then [1] = [a][s] + [nt] = [a][s], so [a]⁻¹ = [s].
  • Z_p is a field for p prime: all [a] ≠ [0] have reciprocals.
    Can do usual algebra in Z_p: solving equations, Quadratic Formula
• Chapter 3. Rings and fields, isomorphisms and homomorphisms
  • Field axioms: (addition) closed, commutative, associative, zero element, negatives; (multiplication) closed, commutative, associative, identity element, reciprocals of any non-zero element; distributive law of multiplication over addition
  • Ring: all axioms, but multiplication possibly not commutative (like matrix ring) or possibly missing reciprocals (like integers)
  • Ring examples: Z, Z_n, matrices M₂(R) for a commutative ring R, polynomial ring F[x] for a field F
  • Field examples: Q, R, C, Z_p for prime p
  • Product ring: R × S = {(r,s) for r ∈ R, s∈ S}, set of all pairs (r,s)
    (r,s) + (r',s') = (r+r', s+s'), (r,s)(r',s') = (rr', ss')
  • Subring R ⊂ S means R is itself a ring inside bigger ring S
    Equivalently: R is closed under addition, negatives, multiplication
    Examples:   Z ⊂ Q ⊂ R
  • Unit:  element u ∈ R with reciprocal u⁻¹ ∈ R, so uu⁻¹ = 1
    Zero-divisor:  z ≠ 0 with zw = 0 for some w ≠ 0
  • Homomorphism: a mapping f from ring R to ring S which respects addtion and multiplication
    f : R → S  with  f(a+b) = f(a) + f(b), f(ab) = f(a)f(b)
  • Isomorphism: a homomorphism which is one-to-one and onto
    The addition and multiplication tables of R, relabeled by f, produce the tables of S
  • Isomorphism examples
    • f : Z_nm → Z_n × Z_m with gcd(n,m) = 1,  f([a]_nm) = ([a]_n, [a]_m);
      Put a hours from nm-hour clock onto n-hour and m-hour clocks
    • Let R = {[

      a	−b
      b	a

      ] ∈ M₂(R)}, a subring of 2×2 real matrices
      f : R → C,     f([

      a	−b
      b	a

      ])  =  a + bi   where   i = √(−1)
  • To show R and S are non-isomorphic, with no possible isomorphism, show they have different numbers of units, or zero-divisors, or disagree in commutativity, or some other algebraic difference in addition an multiplication
• Chapter 4. Polynomial rings
  • For F any field, a polynomial is a function f : F → F, f(x) = a_nxⁿ + ··· + a₁x + a₀
  • Highest xⁿ with a_n ≠ 0 is the degree: deg f(x) = n.
    Degree zero means a constant f(x) = a₀.
    Zero constant poly f(x) = 0 has no degree.
  • deg f(x)g(x)  =  deg f(x) + deg g(x)
  • Units of F[x] are constants f(x) = u ≠ 0. No zero-divisors in F[x].
  • Division with remainder:   a(x) = q(x)b(x) + r(x) for deg r(x) < deg b(x) or r(x) = 0
  • Euclidean Algorithm computes gcd(a(x),b(x)) = d(x)
    Extended Euclidean Algorithm: gives d(x) = f(x)a(x) + g(x)b(x)
  • Divisibility. Unaffected by units: a(x) | b(x) ⇔ u a(x) | b(x) for constant u ≠ 0
  • Irreducible polynomials, Irreducible Divisibility Property
  • Unique Factorization Theorem: Factorization into irreducibles is unique
  • Linear Factor Theorem: f(a) = 0 ⇔ f(x) = (x−a)g(x)

HW:

1. Prove: Let f : R → S be a homomorphism, and T = { s = f(r) for r ∈ R}, the image or output-set of the mapping f. Then T is a subring of S. (Also, T has its own identity 1_T which may be different from 1_S.)
2. Prove: Let m,n be relatively prime, meaning gcd(m,n) = 1. If m | a and n | a, then mn | a. Hint: Write ms + nt = 1 and ams + ant = a. Examine this equation carefully.
3. Non-isomorphic rings.
   1. Define the mapping f : Z₈₈ → Z₄ × Z₂₂ by f([a]₈₈) = ([a]₄, [a]₂₂).
      Hint: Find a particular non-zero element a ∈ Z₈₈ with f(a) = (0,0). What isomorphism property will this violate? Instead of trial-and-error, reduce this to a statement about integers: a ≡ 0 mod 4 and a ≡ 0 mod 22, but a not ≡ 0 mod 88. Find such a.
   2. Show that R = Z₈₈ and S = Z₄ × Z₂₂ are not isomorphic rings. This means there is no possible isomorphism f : R → S . Even though there are many possible mappings f, none will ever work as an isomorphism. Hint: For a ∈ Z define k_R = 1_R + ... + 1_R (k summands), and similarly for k_S. Show that if there were an isomorphism f, it would take f(k_R) = k_S. Now find a k such that k_S = 0_S, but k_R ≠ 0. What is the contradiction?
   3. Find a product ring Z_n × Z_m with nm = 88 which is isomorphic to Z₈₈.
4. Define the mapping f : Z₈₈ → Z₈ × Z₁₁ by f([a]₈₈) = ([a]₈, [a]₁₁). Prove the following statements.
   1. f is one-to-one. Hint: Translate this into statements about integers. If f(a) = f(b) = (c,d), then a ≡ b mod 8 and a ≡ b mod 11. Then...
   2. f is onto. Hint: First write 8s + 11t = 1. Note that f(11t) = (1,0) and f(8s) = (0,1). Now find the number a with f(a) = (c,d) = (c,c)(1,0) + (d,d)(0,1).
5. Give the detailed definition of the product ring R = R⁴. Show it is not isomorphic to the ring S = M₂(R) of 2×2 real matrices. Note: It is not enough to show that the obvious mapping f : R → S is not an isomorphism. You must show that there is no possible map f which is an isomorphism.
6. Give an example of a ring R such that the equation x² = 0 has exactly 7 non-zero solutions x ∈ R. Give an example where it has infinitely many solutions.
   Extra Credit: For any given n, find a ring where it has exactly n solutions.

Solutions: 1. To see that T = {a = f(r) s.t. r ∈ R} is a subring of S, we must check the following. First, T is closed under + : if a,b ∈ T, then a = f(c), b= f(d), so a+b = f(c)+f(d) = f(c+d) since f is a homomorphism, and a+b ∈ T. Similarly, T is closed under multiplication. Also f(0_R) = 0_S ∈ T. Finally, if a ∈ T, then a = f(c), and f(c) + f(−c) = f(c+(−c)) = f(0_R) = 0_S, so −a = f(−c) and −a ∈ T.

2. Since gcd(m,n) = 1, the Eulcidean Algorithm lets us write ms + nt = 1 for some integers s,t. Then ams + ant = a. Since n | a and m | m, clearly nm | ams, and similarly mn | ant. Finally mn | ams + ant = a. That is mn | a, which is our desired conclusion.

3a. The least common multiple is lcm(4,22) = (4)(22) / gcd(4,22) = 44. Thus, 44 ≠ 0 in Z₈₈, but f(44) = (44,44) = 0 in Z₄ × Z₂₂. Hence f is not one-to-one and cannot be an isomorphism. (However, f does respect addition and multiplication, so it is a homomorphism.)

3b. Any isomorphism would have to take units in one ring to units in the other, and the same with zero-divisors. The units in Z_n are [a] with gcd(a,n) = 1, and all other elements are zero-divisors. Thus in Z₈₈ we can count 40 units, 47 zero-divisors, and the zero element. The units in Z₄ × Z₂₂ are the pairs (a,b) where a ∈ Z₄ and b ∈ Z₂₂ are both units, so there are 2·10 = 20 units, 67 zero-divisors, and the zero-element. Since these numbers differ for the two rings, there can be no isomorphism between them. Here is another proof. Suppose f is an isomorphism: one-to-one, onto, respecting addition and multiplication. I claim f(1_R) = 1_S. This is because f is onto, so 1_S = f(r) for some r ∈ R, and f(1_R) = 1_S f(1_R)= f(r) f(1_R) = f(r 1_R) = f(r) = 1_S, which shows the claim.
Now, consider 44 ∈ Z₈₈ and (44,44) = (0,0) ∈ Z₈₈. Since f respects addition, we have:

f(44) = f(1_R + ··· + 1_R) = f(1_R) + ··· + f(1_R) = 1_S + ··· + 1_S = (44,44) = (0,0) .

Thus f(44) = (0,0) = f(0), even though 44 ≠ 0, so f cannot be one-to-one. This contradiction shows there can be no such f.

3c. According to the Chinese Remainder Theorem (Notes 10/1), the mapping f : Z_nm → Z_n × Z_m given by f([a]_nm) = ([a]_n, [a]_m) is an isomorphism, provided gcd(n,m) = 1. Thus, we must take n = 11, m = 8.

4a. If f(a) = f(b) = (c,d) ∈ Z₈ × Z₁₁, then a ≡ b mod 8 and a ≡ b mod 11, which means 8 | (a−b) and 11 | (a−b). Since gcd(8,11) = 1, Problem 2 above implies 88 = (8)(11) | (a−b), and a = b in Z₈₈ . Thus, f(a) = f(b) only for a = b, so f is one-to-one.

4b. The Euclidean Algorithm gives 8s + 11t = 8(−4) + 11(3) = 1. Hence 11t &equiv 1 − 8s ≡ 1 mod 8, and 11t ≡ 0 mod 11, and we get f(11t) = f(33) = (1,0) ∈ Z₈ × Z₁₁. Similarly, f(8s) = f(−32) = f(56) = (0,1). Finally, given any (c,d) ∈ Z₈ × Z₁₁, we find a ∈Z₈₈ with f(a) = (c,d): since f respects addtion and multiplication, f(33c + 56d) = (1,0)(c,c) + (0,1)(d,d) = (c,d), so a = 33c + 56d = 11tc + 8sd works.
These arguments would work to show Z_mn≅ Z_n × Z_m whenever gcd(n,m) = 1.

5. R is a commutative ring ( r r' = r' r ) but S is not. Thus there could be no isomorphism which turns the multiplication table of R into that of S. Formally, suppose f : R → S were an isomorphism. Take any s = f(r) and any s' = f(r') and compute: s s' = f(r) f(r') = f(r r') = f(r' r) = f(r') f(r) = s' s, which would mean S is commutative, but we know matrices do not always commute. This contradiction means there could not be any isomorphism f.

6. An element a ≠ 0 with a^k = 0 for some k is called a nilpotent of R. The simplest ring with a nilpotent element is R = Z_(n²), since n ≠ 0 but n² = 0 in R. To get 7 = 2³−1 nilpotents, take R³ = R×R×R, for example Z₄ × Z₄ × Z₄ , which has the 7 nilpotents (2,0,0), (0,2,0), (0,0,2), (2,2,0), (2,0,2), (0,2,2), (2,2,2).
To get infinitely many nilpotents, take the ring R of 2×2 real matrices. This contains infinitely many nilpotents of the form:

0	x
0	0

• Fundamental Theorem of Algebra: Consider any polynomial f(x) ∈ C[x]. Then:
  • f(x) has a root a ∈ C with f(a) = 0.
  • the irreducible factors of f(x) are all linear: f(x) = (x−a₁) ··· (x−a_n), where a₁, . . . , a_n ∈ C are the roots of f(x), possibly with repeats.
• Irreducibles in R[x] can be linear, or quadratics with no real roots. Any higher degree f(x) ∈ R[x] has lower-degree factors.

Reading: Ch 4.6, pp. 120-123.    
HW:

1. Consider the polynomial:  f(x)  =  x³ − 3x² + 5x − 3.
   1. Guess a root x = a with f(a) = 0. (It may help to graph the polynomial.)
   2. For the above a, factor f(x) into a linear and a quadratic factor: f(x) = (x−a)g(x).
   3. Find the two roots of g(x), giving all three roots of f(x).
   4. Give the irreducible factorization of f(x) in each ring: C[x], R[x], Q[x].
2. Hand In Mon 10/22: Consider the ring Z₂[x] of polynomials with coefficients in the clock ring Z₂ = {0,1}, in which −1 = 1. The degree 1 polynomials are just x, x+1: there is no other possibility. List all the polynomials of degree 2 and 3, and find the irreducible factorization of each. Hint: What does the Linear Factorization Theorem imply in this case?
3. Extra Credit: In Z₂[x], determine the total number of polynomials of degree n. List the irreducible polynomials of degrees 4,5. What more can you say about such polynomials?

1. Guess f(1) = 0. To factor f(x), do long division by x−1, getting quotient x² − 2x + 3, which has roots 1+i√2, 1−i√2 by the Quadratic Formula (and some simplification). Thus we may factorize f(x) = (x−1)(x−1−i√2)(x−1+i√2) in C[x]; but the last two factors are not in R[x], so f(x) = (x−1)(x²−2x+3) ∈ R[x], and also in Q[x].

• In class, we discussed congruence of polynomials in F[x] modulo a given polynomial f(x) of degree n. This can be defined equivalently as:
  • a(x) ≡ b(x) mod f(x)
  • f(x) | b(x)−a(x)
  • b(x) = a(x) + q(x)f(x)
• We constructed the polynomial modular ring R = F[x] / (f(x)). Formally, the class of a(x) is the set of all b(x) equivalent to a(x) mod f(x):

  [a(x)]

  = { b(x) such that b(x) ≡ a(x) mod f(x) },

  so that [f(x)] = [0] and [a(x)] = [a(x) + g(x)f(x)]. If a(x) = q(x)f(x) + r(x) has remainder r(x) with deg r(x) < n, then [a(x)] = [r(x)], the standard form of the class [a(x)].
• Operations on R are formally defined by [a(x)] + [b(x)] = [a(x)+b(x)] and [a(x)] [b(x)] = [a(x)b(x)].
• We consider the example of F[x] = R[x] modulo f(x) = x² + 1 with degree n = 2:
  R  =  R[x]/(x²+1)  =  {[s+tx] for s,t ∈ R},
  since we can write any class in the standard form [a(x)] = [r(x)] for a remainder r(x) = s + tx of degree less than 2. Since [0] = [x²+1] = [x]² + [1], we have [x]² = −[1].
• For computation, we compute the standard forms:

  [s+tx] + [s'+t'x]	=	[s+tx+s'+t'x] = [(s+s')+(t+t')x]
  [s+tx][s'+t'x]	=	[(s+tx)(s'+t'x)] = [ss' + st'x + s'tx + tt'x2]
  	=	[ss' + st'x + s'tx + tt'(x2+1) −tt'] = [(ss'−tt') + (st'+s't)x].

  The standard form for the product is the remainder of (s+tx)(s'+t'x) divided by f(x) = x² + 1.
• In fact, R is a field. For [s + tx] ≠ [0], we have: [s+tx]⁻¹   =   [ ^s⁄_(s²+t²) − ^t⁄_(s²+t²) x ] , which you can check by mulitplying to get [1].
• These computations should look familiar: the ring R is isomorphic to C, with [x] going to i = √(−1) and [s+tx] going to s+ti. Both rings are built from the real numbers R by adjoining an element whose square is −1.

Reading: Ch 5.1, pp. 37-41.    
HW:

1. Hand In Mon 10/22: Imitating the above, compute the addition and multiplication formulas for the ring Q[x] / (x²−2).
2. Hand In Mon 10/22: Find the reciprocal of [s+tx] ∈ Q[x] / (x²−2).
   Hint: [x] behaves like √2. Imitate rationalizing the denominator of ¹⁄_(s+t√2).
3. Consider the ring S = R[x] / (x²−2). This will have the same formulas as Q[x] / (x²−2), but with real rather than rational coefficients. Show that (x−√2) is a zero-divisor in the ring S. Why does the reciprocal formula above not work for this element?

3. [x−√2][x+√2] = [x²−2] = [0]. The reciprocal formula does not work for [x−√2]⁻¹ because the denominator of the formula becomes zero.

• Theorem: Consider the polynomial modular ring R = F[x]/(f(x)).
  1. An element [a(x)] ∈ R has a reciprocal [a(x)]⁻¹ ∈ R if and only if gcd(a(x),f(x)) = 1.
  2. If f(x) is an irreducible polynomial in F[x], then R = F[x]/(f(x)) is a field.
• Proof:
  1. (⇐) Suppose gcd(a(x),f(x)) = 1. By the Extended Euclidean Algorithm for polynomials, we can write a(x)b(x) + f(x)g(x) = 1. But [f(x)g(x)] = [0], so [a(x)][b(x)] = [1] ∈ R, so [a(x)]⁻¹ = [b(x)].
     (⇒) If [a(x)][b(x)] = [1], then a(x)b(x) = 1 + f(x)g(x) and a(x)b(x) − f(x)g(x) = 1. Now, if c(x) is a common divisor of a(x) and f(x), then c(x) | a(x)b(x) − f(x)g(x) = 1, so c(x) = u, a constant, and the gcd is 1.
  2. We need to show that the commutative ring R has reciprocals for all non-zero elements. Since f(x) is irreducible, it has no factors except itself and 1 (or more precisely u f(x) and u). If [a(x)] ≠ [0] ∈ R, then f(x) ∤ a(x), so a(x) and f(x) cannot have any common factors except 1, which means gcd(a(x),f(x)) = 1. By part (a), this means [a(x)] has a reciprocal in R, which means R is a field.

Reading: Ch 5.2−5.3, pp. 130-138.    
HW: Consider the ring R = Q[x]/(x²+x+1) from class.

• In this ring, we have [x]² + [x] + [1] = [0], so the element α = [x] ∈ R is a root of the polynomial f(x) = x² + x + 1.
• Any element of R can be written in standard form [ax+b] = [a][x] + [b] = aα + b, where a,b ∈ Q.
• We would like to "rationalize the denominator" for expressions with α, i.e. to find reciprocals:
  ¹⁄_(aα+b)  =  [ax+b]⁻¹  =  [cx+d]  ∈  R.

Problems

1. Use the Extended Euclidean Algorithm to write  (2x+3)b(x) + (x²+x+1)g(x)  =  1.
   Hint: It is enough to get any constant on the right hand side, then divide both sides by that constant to get 1.
2. Find the reciprocal [2x+3]⁻¹ ∈ R
3. Similarly, find the reciprocal of an arbitrary element [ax+b] ∈ R.

1,2. Division gives:   x² + x + 1  =  (¹⁄₂x − ¹⁄₄)(2x + 3) + ⁷⁄₄,   so:

⁻⁴⁄₇(¹⁄₂x − ¹⁄₄)(2x + 3) + ⁴⁄₇(x² + x + 1)  =  1,       [2x + 3]⁻¹  =  ⁻⁴⁄₇[¹⁄₂x − ¹⁄₄]  =  [−²⁄₇x + ¹⁄₇].

3. Dividing  f(x) = x² + x + 1  by  ax + b:

	q(x) = 1⁄ax + (a−b)⁄a2	rem   r = (a2−ab+b2)⁄a2
ax + b	)   x2 + x + 1
	−(x2 + b⁄ax)
	(1−b⁄a)x + 1
	−((a−b)⁄ax + (ab−b2)⁄a2)
	1 − (ab−b2)⁄a2

This means  f(x) = q(x) (ax+b) + r,  and  −[q(x)][ax+b] + [f(x)] = [r],  and  ⁻¹⁄_r [q(x)][ax+b] = [1],  so that:

[ax + b]⁻¹   =   ⁻¹⁄_r [q(x)]   =   ^−a2⁄_{(a²−ab+b²)} [¹⁄_ax + ^(a−b)⁄_a²]   =   ⁻¹⁄_{(a²−ab+b²)} [ax + a−b].

Change of notation and viewpoint.

• Consider an irreducible polynomial p(x) ∈ F[x]. We previously denoted elements of the field K = F[x]/(p(x)) by
  [a(x)]  =  [a_kx^k + ··· + a₁x + a₀]  =  [a_k][x]^k + ··· + [a₁][x] + [a₀]   with all   a_i ∈ F.
  Now we will denote the class of a constant polynomial [c] by just c, and the class [x] by α (Greek letter alpha). Thus we write:
  [a(x)]  =  a_kα^k + ··· + a₁α + a₀.

• The element α ∈ K is a root of p(x), since p(α) = p([x]) = [p(x)] = [0] = 0 ∈ K. We may use the notation K = F[α] to suggest the ring generated by constants F, the new "number" α, and all sums and products of these.
• Suppose ᾱ ∈ R is an irrational real root of an irreducible polynomial p(x) ∈ Q[x]. Define the subring:
  Q[ᾱ]  =  {a_kᾱ^k + ··· + a₁ᾱ + a₀ with all a_i ∈ Q}  ⊂  R.
  Then there is an isomorphism:
  f : Q[ᾱ] → K = Q[x]/(p(x))   with   f(ᾱ) = α = [x].
  That is, ᾱ and α behave exactly the same in any algebraic formula.
• Example:  Q[√2] ≅ Q[x]/(x²−2), and a formula like  (√2 + 1)² = 2√2 + 3  in Q[√2] corresponds to  (α + 1)² = 2α + 3 for α = [x] ∈ Q[x]/(x²−2).

Reading: Ch 5.3, pp. 135-138.    
HW:

1. Consider the irreducible polynomial p(x) = x³ − 3x − 1 ∈ Q[x], and the field K = Q[x]/(p(x)) = Q[α], where α = [x] and α³ − α − 1 = 0.
   1. Graph the function p(x) = x³ − 3x − 1 to approximate its largest real root ᾱ > 0.
      Note: There is no standard symbol (such as √2) for the irrational number ᾱ. However, we have Q[ᾱ] ≅ K, which means we can do exact algebraic computations with ᾱ by using α = [x] in K.
   2. Rationalize the denominator of ¹⁄_(α²+2). That is, write [x²+2]⁻¹ = [ax² + bx + c] using the Extended Euclidean Algorithm, so that ¹⁄_(α²+2) = aα² + bα + c.
   3. Let y be a new variable, and consider the ring K[y], the polynomials of the form f(y) = b_ky^k + ··· + b₁y + b₀ with coefficients b_i ∈ K. Since y = α ∈ K is a root of p(y) = y³ − 3y − 1, this polynomial has the linear factor (y−α). Use long division to write p(y) = (y−α)q(y) for q(y) ∈ K[y].
      Hint: Use our previous methods of computation for the coefficients in K, writing all elements in standard form aα²+bα+c.
   4. Use the Quadratic Formula on q(y) above to find the two other roots of p(y) in terms of α. Verify your result by numerically computing these roots using the approximation to ᾱ from part (a), and comparing with the roots seen on the graph.
2. Hand In Mon 10/29: Consider field Z₂ = {0,1} with 2 = 0 and −1 = 1. For the polynomial p(x) = x³ + x + 1 ∈ Z₂[x], consider the ring K = Z₂[x]/(p(x)).
   1. Show that p(x) is irreducible in Z₂[x]. Hint: What would be the degrees of any non-trivial factors of p(x)? Use the Linear Factor Theorem:  f(x) = (x−a)g(x)   ⇔   f(a) = 0.
   2. List the 8 elements of the field K in standard form, starting with the constants 0 and 1. To avoid brackets, write α instead of [x]. We think of α as a kind of "irrational number" with respect to the original field Z₂.
   3. Make complete addition and multiplication tables for the ring K.
   4. What feature of the multiplication table shows that K is commutative? What feature shows it has reciprocals?
   5. Looking at the multiplication table, determine which elements of K have square roots in K. Is the Quadratic Formula valid for solving the equation ay² + by + c = 0, for a,b,c ∈ K?
3. Extra Credit: The Fibonacci numbers are a sequence F₁, F₂, F₃, . . . defined recursively by F_n  =  F_n−1 + F_n−2, starting from F₁ = F₂ = 1. That is, F₃ = 1+1 = 2, F₄ = 1+2 = 3, F₅ = 2+3 = 5, etc.
   The golden ratio is the number φ  =  ^{(√5 + 1)}⁄₂  ≈  1.6, with reciprocal ψ  =  ¹⁄_φ  =  ^{(√5 − 1)}⁄₂  ≈  0.6. Then φ and −ψ are the roots of the equation x² − x − 1 = 0.
   1. Show that φⁿ = F_nφ + F_n−1.   Hint: Use induction, computing in the ring Q[φ].
   2. Show Binet's formula:  F_n  =  ¹⁄_√5(φⁿ − (−ψ)ⁿ).

1a. Zooming in on the graph shows the roots of x³ − 3x − 1 are about ᾱ ≈ 1.88 , β̄ ≈ −0.35 , γ̄ = −1.53 .

1b. The Euclidean Algorithm for p(x) = x³ − 3x − 1 and a(x) = x² + 2 gives:

p(x)  =  x a(x) + r₁(x),         a(x)  =  (⁻¹⁄₅x + ¹⁄₂₅) r₁(x) + r₂(x),

with r₁(x) = −5x−1 and r₂(x) = ⁵¹⁄₂₅. The Extended Euclidean Algorithm gives:

⁵¹⁄₂₅  =  r₂(x)  =  a(x) − (⁻¹⁄₅x + ¹⁄₂₅)(p(x) − x a(x))
 =  (¹⁄₅x − ¹⁄₂₅) p(x) + (⁻¹⁄₅x² + ¹⁄₂₅x + 1) a(x).

Multiplying by ²⁵⁄₅₁ gives:

(⁵⁄₅₁x − ¹⁄₅₁) p(x)  +  ¹⁄₅₁(−5x² + x + 25) a(x)   =   1.

Therefore, in the field K = Q[x]/(p(x)), we have [x² + 2]⁻¹  =  [a(x)]⁻¹  =  ¹⁄₅₁[−5x² + x + 25]. Switching to the notation α = [x], this says:

¹⁄_{(α² + 2)}   =   ¹⁄₅₁(−5α² + α + 25).

The same formula holds for the real number ᾱ because of the isomorphism K ≅ Q[ᾱ].

1c. In the polynomial ring K[y] with variable y and coefficients in K = Q[α] satisfying α³ − 3α − 1 = 0, we divide  f(y) = x³ − 3y − 1  by  y − α:

	q(x)  =  y2 + αy + (α2−3)
y − α	)   y3         − 3y − 1
	−(y3 − αy2)
	αy2 − 3y − 1
	−(αy2 − α2y)
	(α2−3)y − 1
	−((α2−3)y − (α3−3α2))
	r(x) = α3−3α2−1 = 0

That is:

y³ − 3y − 1   =   (y − α) (y² + αy + α²−3)

1d. Applying the Quadratic Formula to  y² + αy + α²−3  =  0  gives:

y   =   ¹⁄₂(−α ± √(α² − 4(α²−3)))   =   ¹⁄₂(−α ± √(12 − 3α²)) .

This gives the values of the other two roots  y = β, γ  of  p(y) = y³ − 3y − 1,  in terms of the root  y = α. To check our solutions numerically, we substitute α ≈ 1.88 from part (a), getting β ≈ −0.35 and γ ≈ −1.53, as we expected.

Note that β, γ are no longer in K = Q[α], since they involve square roots of α's; rather, they are in an even bigger field. This is called the splitting field of p(x), denoted L = Q[α, β, γ], because the polynomial splits into linear factors if we allow coefficients in L:  p(x) = (x−α)(x−β)(x−γ) ∈ L[x].

• We are going to abstract the the construction of the modular ring Z_n and the polynomial modular ring F[x]/(f(x)) to an arbitrary ring. The key structure is the zero class I = [0], a subset of R; from this, we will construct arbitrary classes [r] which are elements of a "modular" ring R/I. Below, we describe the conditions for an appropriate zero class I, called an ideal. In the next lecture, we will define R/I, called the quotient ring.
• In a ring R, an ideal is a subset I ⊂ R which is closed under addition within itself, and closed under multiplication by R:
  1. If i, j ∈ I, then i+j ∈ I
  2. If i ∈ I and r ∈ R, then ir, ri ∈ I
  The second condition says that multiplication by I "absorbs" any element of R into I, which will guarantee that multiplication by [0] will "absorb" any element of R/I to [0].
• Example: In R = Z, let I = (n) = {kn for k ∈ Z}, all multiples of n. This is an ideal.
  Proof: This satisfies (i) because for any i,j ∈ I, we have i = kn, j = ℓn, so i + j = kn + ℓn = (k+ℓ)n , and i+j ∈ I. It satisfies (ii) because for any i ∈ I and r ∈ R, we have i = kn, so ir = kn r = (kr)n, and ir ∈ I. QED
  Note that I = [n] = [0], the zero-class in the modular ring Z_n, which we will now denote as the quotient ring R/I = Z/(n).
• Example: In R = F[x], we have the ideal I = (f(x)) = {g(x)f(x) for k ∈ Z}, all multiples of f(x). Then I = [f(x)] = [0], the zero-class in the polynomial modular ring R/I = F[x]/(f(x)), a quotient ring.
• For any element q in a commutative ring R, we can define the principal ideal (q) = {rq for r ∈ R}. This satisfies (i) and (ii) just as in the examples above.
• For any elements q₁, . . . , q_m in commutative R, we define the ideal generated by these elements to be the set of all linear combinations of them:
  (q₁, . . . , q_m)  =  {r₁q₁ + ··· r_mq_m  for  r₁, . . . , r₁ ∈ R}

Reading: Ch 6.1, pp. 141-148.    
HW:

1. Show that in the polynomial ring F[x], the set I = (f(x)) is an ideal.
2. Show that in the ring Z₆, the set I = {[0], [2], [4]} is an ideal.
3. Let R × S be the product ring from Notes 9/26, whose elements are pairs (r,s) with r ∈ R and s ∈ S. Show that the set I = (R,0) = {(r,0) for r ∈ R} is an ideal. Also, find an element (p,q) such that I is the principal ideal generated by (p,q), namely ((p,q)) = {(p,q)(r,s) for (r,s) ∈ R×S}
4. Show that (q₁, . . . , q_m) ⊂ R defined in the Notes above is an ideal.

1. I = (f(x)) ⊂ F[x] is a principal ideal. It satisfies (i) because g(x)f(x) + h(x)f(x) = (g(x) + h(x))f(x) ∈ I; and (ii) because g(x)f(x) h(x) = (g(x)h(x)) f(x) ∈ I for all h(x) ∈ F[x].

2. This is the principal ideal ([2]) = {[0], [2], [6]}, all multiples of [2] in Z₆.

3. (R,0) ⊂ R × S satisfies (i) because (r,0) + (r',0) = (r+r',0) ∈ (R,0); and (ii) (r,0)(r',s') = (rr', 0) for all (r',s') ∈ R × S. In fact, this is the principal ideal (R,0) = ((1,0)).

4. The set (q₁, . . . , q_m) ⊂ R satisfies (i) because

r₁q₁+···+r_mq_m  +  r'₁q₁+··· +r'_mq_m   =   (r₁+r'₁)q₁+ ··· + (r_m+r'_m)q_m   ∈   (q₁, . . . , q_m)

and (ii) because

r (r₁q₁+···+r_mq_m)   =   (rr₁)q₁ + ··· + (rr₁)q_m

• Definition: For an ideal I in a ring R, we define a is congruent to b modulo I, to mean:
  a ≡ b mod I     ⇔     a − b ∈ I     ⇔     a = b + i  for some i ∈ I.
  This generalizes the case of R = Z and I = (n) in 9/12, and the case of R = F[x] and I = (f(x)) in 10/19.
• Congruence is an equivalence relation.
  • reflexive:  a ≡ a
  • symmetric:  a ≡ b   ⇒   b ≡ a
  • transitive:  a ≡ b  &  b ≡ c   ⇒   a ≡ c
• The congruence class of an element is the set of all elements congruent to it:

  [r]	=	{r' ∈ R with r' ≡ r mod I}
  	=	{r + i for i ∈ I}
  	=	r + I.

  This splits up R into disjoint classes, with no overlap: [r] ∩ [r'] = ∅ for [r] ≠ [r'].
• Quotient Ring Theorem: For any ideal I ⊂ R, we let R/I = {[r] for r ∈ R}, the set of all congruence classes, with operations defined by:   [a] + [b]  =  [a+b]  and  [a][b]  =  [ab].  Then R/I is a ring, which is commutative if R is commutative.
  Proof: The ring properties from 9/12 are all inherited from the corresponding properties for the original ring R. For example, the ring R has commutative addition, a+b = b+a ∈ R, so  [a] + [b] = [a+b] = [b+a] = [b] + [a] ∈ R/I, and R/I also has commutative addition. The zero element is [0] = I, negatives are given by −[r] = [−r], and the identity element is [1].
  The only subtle issue is whether addition and multiplication are well-defined. That is, if we take different representatives for given classes,  [a] = [a']  and  [b] = [b'], do we have  [a+b] = [a'+b']  and  [ab] = [a'b']? Yes we do:  a ≡ a', b ≡ b'  means  a' = a + i, b' = b + j  for  i,j ∈ I, so:
  a' + b'  =  a + i + b + j  =  a + b + (i+j)  ≡  a + b,
  
  a'b'  =  (a + i)(b + j)  =  ab + aj + bi + ij  ≡  ab,
  since i + j ∈ I from closure under addition, and aj, bi, ij ∈ I from closure under multiplication by R, so aj + bi + ij ∈ I again from closure under addition.
• The reason for the name quotient ring is that if R is finite with #R elements (for example R = Z_n with #R = n), then R/I is finite, and
  #(R/I)   =   ^#R⁄_#I .
  This is because the classes [r] = r + I are all shifts of [0] = I, and they all have the same number of elements: #[r] = #I. If we write the elements of R in a table with each row being a class [r], then there are #(R/I) rows and #I columns, so #R = #(R/I) · #I. Dividing by #I gives the result.
  Similarly, a finite product ring has  #(R×S) = (#R)(#S).

Reading: Ch 6.2, pp. 152-154.    
HW:

1. Recall the product ring R = Z×Z = {(m,n) for m,n ∈ Z}, with termwise addition and multiplication.
   1. Show that the subset S = {(k,k) s.t. k ∈ Z} is a subring with identity, but not an ideal.
      Extra Credit: If we tried to define a quotient ring R/S, exactly where would the construction go wrong? What ring property would be missing?
   2. Recall from 10/29 that I = Z × {0} = {(k,0)  for  k ∈ Z} is an ideal, so we have a quotient ring R/I. Write a typical class [(m,n)] in an appropriate standard form. That is, for any (m,n) ∈ R, add an element (k,0) ∈ I to put it into a unique, simpler form.
      Hint: Here standard form is not defined by the remainder of long division, but by a different kind of "cutting down" by I.
   3. Give a ring isomorphism R/I ≅ Z. That is, quotienting by the ideal I undoes the product R = Z×Z.
2. Hand In Mon 11/5: Operations on ideals. Let R be a ring with two ideals I,J ⊂ R.
   1. Prove that the intersection I ∩ J = {k with k ∈ I and k ∈ J} is also an ideal of R. Hint: Look at the proof that (n) ⊂ Z and Ker(f) ⊂ R are ideals in Notes 10/29 and 11/2.
   2. Prove that the sum I + J = {i + j for i ∈ I, j ∈ J} is also an ideal of R.
   3. For R = Z and principal ideals I = (a), J = (b), prove that I + J = (d), where d = gcd(a,b), the greatest common divisor.
      Hint: First show that I + J ⊂ (d), any element of I + J is also an element of (d); that is, if i + j ∈ I + J for i ∈ I and j ∈ J, then i + j ∈ (d). Then show (d) ⊂ I + J, any element of (d) can be written in the form i + j. Use our previous knowledge about integers.
3. Extra Credit: In (2c) above, prove that if gcd(a,b) = 1, then the intersection I ∩ J = (ab).
4. For a ring R we have the ideals (0) = {0} and (1) = R. Prove that R/(0) ≅ R and R/(1) ≅ {0}, the degenerate ring with one element.

1a. S is closed under addition, multiplication, and negatives, and contains 1_R = (1,1), so it is a subring with identity. However, it is not closed under multiplication by R: for (k,k) ∈ S and (m,n) ∈ R, we have (k,k)(m,n) = (km,kn), which is not always in S.

1b. To standardize (m,n) by adding an element (k,0), cancel the first coordinate: [(m,n)] = [(m,n) + (−m,0)] = [(0,n)]. This is unique, since if the same element had two standard forms [(0,n)] = [(0,n')], then (0,n) − (0,n') = (0, n − n') ∈ I, which can only happen if n − n' = 0, namely n = n'. We conclude: R/I = {[(0,n)] for n ∈ Z}.

1c. Define the mapping f : R/I → Z by f([(0,n)]) = n. This mapping clearly respects addition and multiplication, and is one-to-one and onto, and so is an isomorphism.

4. R/(0) consists of one-element classes [r] = r + {0} = {r}. Thus f : R → R/(0) with f(r) = [r] is clearly an isomorphism.
Also R/(1) = R/R consists of a single class: [r] = r + R = R = [0] for any r. The operations are [0] + [0] = [0] and [0][0] = [0]. Note that in this degenerate ring [0] = [1].

• There is an intimate relationship between quotient rings and homomorphisms between rings. The connection is given by the kernel ideal of a homomorphism.
• Definition/Theorem: ([H] Thm 6.10) Given a homomorphism between rings, f : R → S, define the kernel of f to be the set:
  Ker(f)  =  {i ∈ R with f(i) = 0}.
  Then Ker(f) is an ideal in R.
  Proof: Ker(f) is closed under addition since if i, i' ∈ Ker(f), then f(i) = f(i') = 0, so f(i+i') = f(i) + f(i') = 0 + 0 = 0, so i + i' ∈ Ker(f).
  Ker(f) is closed under multiplication by R since if  i ∈ Ker(f)  and  r ∈ R, then  f(i) = 0, so  f(ir) = f(i) f(r) = 0 f(r) = 0.
• Natural Homomorphism Theorem: ([H] Thm 6.12) For an ideal I in a ring R, there is a surjective homomorphism  f : R → R/I  given by f(r) = [r]. That is, the element r ∈ R is mapped to the class [r] ∈ R/I. This homomorphism has kernel Ker(f) = I.
  Proof: This is a homomorphism, respecting addition and multiplication, because of the definition of these operations in R/I: that is, f(r + r') = [r + r'] = [r] + [r'] = f(r) + f(r'), and similarly for multiplication. It is surjective (onto) because any class [r] is the class of some  r ∈ R,  so  [r] = f(r).
  Finally, Ker(f) = I, since:
  r ∈ Ker(f)   ⇔   f(r) = [r] = [0]   ⇔   r ≡ 0 mod I   ⇔   r ∈ I.
  Note: f is not injective (one-to-one), because we can take any pair of elements with r ≡ r' mod I to get f(r) = [r] = [r'] = f(r').
• First Isomorphism Theorem: (Thm 6.13) If f : R → S is a surjective homomorphism, then S is isomorphic to the quotient of R by I = Ker(f): that is,  S ≅ R/I.
  Proof: Given the homomorphism  f : R → S, we define the isomorphism  f̃ : R/I → S  by  f̃([r]) = f(r); that is, the class  [r] ∈ R/I  corresponds to the element  f(r) = s ∈ S. We must check the isomorphism properties. It is a homomorphism because f is a homomorphism:
  f̃([r]+[r'])  =  f̃([r+r'])  =  f(r+r')  =  f(r) + f(r')  =  f̃([r]) + f̃([r']),
  and similarly for multiplication.
  Also f̃ is surjective because f is surjective: given s ∈ S, there is r ∈ R with f(r) = s, so there is [r] ∈ R/I with f̃([r]) = f(r) = s.
  Finally we show f̃ is injective: that f̃ produces the same outputs only from the same inputs. Suppose  f̃([r]) = f̃([r']), so that  f(r) = f̃([r]) = f̃([r']) = f(r'). Then  f(r−r') = f(r) − f(r') = 0, so r−r' ∈ Ker(f) = I, therefore [r] = [r'] ∈ R/I. That is f̃([r]) = f̃([r']), only when [r] = [r'].

Reading: Ch 6.2, pp. 154-159.    
HW:

1. Prove that any ideal I ⊂ R contains the zero element: 0 ∈ I.
2. From HW 10/29 #2, in the ring R = Z₆ = {0,1,2,3,4,5}, consider the ideal I = (2) = {2,4,6}. (We drop bracket notation in Z₆, so that 6 = 0 etc.)
   1. Write the elements of R in a table so that each class [r] = r + I ∈ R/I is one row: a total of two rows by three columns. Write the natural homomorphism  f : R → R/I  by labeling the classes [0] and [1] on the right of the corresponding rows; then each element r in the table goes to the class of its row. Check that this is a homomorphism.
   2. Find the kernel Ker(f), identifying it in your table. How does this relate to the Natural Homomorphism Theorem above?
3. Consider the mapping φ : R[x] → R which takes a polynomial f(x) ∈ R[x] to φ(f(x)) = f(0), the constant term of f(x). For example φ(x² + 3) = 3. We use the Greek letter phi φ to distinguish the ring mapping φ from a polynomial function f(x).)
   1. Show that φ is a homomorphism.
   2. Determine Ker(φ)
   3. Directly verify the First Isomorphism Theorem in this case: S = R ≅ R/I = R[x]/Ker(φ)
4. Extra Credit: Repeat #3 for the mapping φ(f(x)) = f(1), the value of f(x) at x = 1.
5. Extra Credit: Prove the Second Isomorphism Theorem: If a ring R has ideals I,J, then (I+J)/J ≅ I/(I∩J). (Here both sides are rings without identity element, J is an ideal in I+J, and I∩J is an ideal in I.)
6. Characteristic of a ring
   1. Prove that any ring R contains a copy of Z/(n) which includes the element 1_R.
      Hint: Define a homomorphism φ : Z → R by f(k) = k_R = ±(1_R + ··· + 1_R) with |k| terms. Now use the First Isomorphism Theorem.
      Note: The number n is called the characteristic of R. If the characteristic is n = 0, then R contains a copy of Z/(0) = Z, otherwise a copy of Z/(n) = Z_n. For example, any extension field K ⊃ Z_p has characteristic p, whereas Q, R, C ⊃ Z all have characteristic 0.
   2. Show that the characteristic of a field F must be 0 or prime p. That is, any field contains a copy of Z or Z_p for some p.
7. Hand In Mon 11/12: Prove: Let φ : R → S be a homomorphism. If Ker(φ) = {0}, then φ is injective (a one-to-one mapping). Hint: If Ker(φ) = {0}, then only r = 0 gives φ(r) = 0; show this allows only one r ∈ R with φ(r) = s, for any s ∈ S. Use the usual strategy for showing r is unique.

1. Prop: Any ideal I ⊂ R has 0 ∈ I.
Proof: I is closed under multiplication by R, so taking any i ∈ I and r = 0 ∈ R, we have ir ∈ I, but ir = i0 = 0, so 0 ∈ I.

2a. We show the natural homomorophism R = Z₆ → R/I = Z₆/(2) as:

R

0 2 4 1 3 5

→

[0] [1]

R/I

This is a homomorphism because the addition and multiplication of [0], [1] ∈ R/I are defined by usual operations on even and odd numbers in the table.

2b. The kernel of R → R/I is the set of all elements in R = Z₆ which go to [0] ∈ R/I, namely the elements of I = [0] ⊂ R: that is, Ker(f) = {2,4,6} = I, as predicted by the Natural Homomorphism Theorem.

3a. We have φ(f(x)+g(x)) = f(0) + g(0) = φ(f(x)) + φ(g(x)), and similarly for multiplication. Thus φ is a homomorphism.

3b. Ker(φ)  =  {f(x) ∈ R[x]  with  φ(f(x)) = f(0) = 0}; the polynomials with constant term zero, which are divisible by x in R[x]. That is,   Ker(f)  =  (x)  =  {x g(x)  for  g(x) ∈ R[x]}.

3c. The quotient ring R/I = R[x]/(x) has standard forms which are remainders r(x) under division by x, namely deg r(x) < 1, so that r(x) = r₀ a constant, and any class is [f(x)] = [r(x)] = [c], corresponding to c ∈ R; and the classes [c] ∈ R/I are added and multiplied in the same way as c ∈ R. The mapping on standard forms is obviously one-to-one and onto, so the natural mapping is an isomorphism.

6. Let P = {k_R = ±(1_R + ··· + 1_R) with |k| terms, for k ∈ Z}. Clearly this is a subring, and there is a surjective homomorphism φ : Z → R with φ(k) = k1_R. The First Isomorphism Theorem implies P ≅ Z / Ker(φ). But any ideal of Z is (n) for some n (possibly n = 0), so Ker(φ) = (n) and P ≅ Z/(n) = Z_n. P is called the prime ring of R.
b. The characteristic of a ring R is the smallest integer n such that n_R = 0_R. If n = ab with a,b > 1, then a_R, b_R ≠ 0_R, but a_R b_R = n_R = 0_R. Hence P = {k_R for k ∈ Z} has zero-divisors, and so does R ⊃ P. If R = F, a field, then there can be no zero-divisors, so we must have n = p prime.

1. Consider R = Z[x], the ring of polynomials with integer coefficients. (Until now, we have only considered coefficients in a field F, but the integers are not a field because they lack reciprocals.) Let I = (2,x) = { 2f(x) + xg(x) for f(x),g(x) ∈ R } be the ideal generated by the elements 2,x. Show that this ideal is not principal: that is, there is no a(x) ∈ R with I = (a(x)) = { a(x)f(x) for f(x) ∈ r}.
   Hint: If we had (2,x) = (a(x)), this would imply 2 = a(x)f(x); but this can only happen for deg a(x) = 0.
2. Hand In Mon 11/12: In the ring of integers R = Z, consider the ideal:
   (8,12,14)  =  { 8e + 12f + 14g for e,f,g, ∈ Z }.
   As in the Hand-in HW from 11/5, show this is equal to the principal ideal (2), using the following steps.
   1. Find integers a,b with 8a + 12b = 4, and c,d with 4c + 14d = 2. Comibine these to get e,f,g with
      8e + 12f +14g  =  2.

   2. Use part (a) to show that (2) ⊂ (8, 12, 14).
   3. Show that (8, 12, 14) ⊂ (2) by using the definition.
   4. Combine parts (b) & (c) to show (8, 12, 14) = (2).

1. Prop: The ideal (2,x) ⊂ Z[x] is not prinicipal.
Proof: Suppose that (2,x) = (a(x)) were a principal ideal. Then 2 ∈ (a(x)), meaning 2 = a(x)f(x) for f(x) ∈ Z[x], which means 0 = deg a(x) + deg f(x), so deg a(x) = 0, and a(x) = a, non-zero constant. Thus 1 = aa⁻¹ ∈ (a), but clearly 1 ∉ (2,x), so (1,x) ≠ (a), contradicting our original assumption. This contradiction shows the assumption is impossible, and (2,x) is not principal.

• In a ring R, a maximal ideal is an ideal I which is as large as possible given that I ≠ R. That is, equivalently:
  • the only ideals J with  I ⊂ J ⊂ R  are  J = I  and  J = R;  or
  • adding any outside element a ∉ I into I generates the ideal  (a) + I = R.
• Theorem: A quotient ring R/I is a field if and only if I is a maximal ideal.
  Proof: We prove (⇒) and (⇐) simultaneously. Consider any [a] ≠ [0] ∈ R/I, or equivalently a ∉ I. We have:

  R/I is a field	⇔	[a][b] = [1]  for some  [b] ∈ R/I
  	⇔	ab ≡ 1 mod I  for some  b ∈ R
  	⇔	ab = 1 + i  for some  b ∈ R,  i ∈ I
  	⇔	ab − i = 1  for some  b ∈ R,  i ∈ I
  	⇔	(a) + I ∋ 1
  	⇔	(a) + I = (1) = R.
  	⇔	I is a maximal ideal.

Reading: Ch 6.3, pp. 163-164.    
HW:

1. Hand In Mon 11/12: We know that, in the ring of integers R = Z, all ideals are pincipal ideals: 
   I  =  (n)  =  {kn for k ∈ Z},  all the multiples of a single element n.
   1. Show that:  (n) ⊂ (m)   ⇔   m | n,  i.e. m is a divisor of n.
   2. Show that if I = (n) is maximal ideal, with no other ideals between I and R, then n = p, a prime number.

Reading: Ch 7.1, p. 169-180.
HW:

1. Work out the symmetry group G = Sym(S) of the square S below, including rotations and reflections. There are 8 symmetries, including the identity.
   
   1. Sketch how each symmetry L(x,y) moves the square, and write its matrix, which consists of the column vectors [ L(1,0) | L(0,1) ]. For example, the 90° counter-clockwise rotation R is [

      0	−1
      1	0

      ].
   2. For each symmetry, write the corresponding permutation of the four vertices (numbered as shown). For example, the above rotation R is (

      1	2	3	4
      2	3	4	1

      ), where the columns mean vertex 1 is moved to vertex 2, . . . , vertex 4 is moved to vertex 1.
   3. Give each symmetry a letter: the identity I, the rotations R, R², R³, and reflections A, B, C, D. Write out the 8×8 multiplication table of G under the composition operation, computing entries either as products of matrices or compositions of permutations.
2. Hand In Mon 11/:19 As in #1a,b,c, work out the symmetry group G = Sym(T) of the equilateral triangle T below. There are 6 symmetries, including the identity: explain why there could not be any more.
   
   The coordinates of the vertices are:
   v₁  =  (1,0)
   v₂  =  (cos(θ), sin(θ))  =  (⁻¹⁄₂ , ^√3⁄₂)  for  θ = 120°
   v₃  =  (cos(θ), sin(θ))  =  (⁻¹⁄₂ , ^−√3⁄₂)  for  θ = −120°.

1a,b. The symmetries of the square are:

I	Identity mapping, no motion	[  1   0  0 1 ]	(  1   2   3   4  1 2 3 4 )
R	90° rotation counterclockwise	[  0  −1  1 0 ]	(  1   2   3   4  2 3 4 1 )
R2	180° rotation	[ −1   0  0 −1  ]	(  1   2   3   4  3 4 1 2 )
R3	270° = −90° rotation	[  0   1  −1  0 ]	(  1   2   3   4  4 1 2 3 )
A	reflection across y-axis	[ −1   0   0   1  ]	(  1   2   3   4  2 1 4 3 )
B	reflection across x-axis	[  1   0   0  −1  ]	(  1   2   3   4  4 3 2 1 )
C	reflection across y = x	[  0   1   1   0  ]	(  1   2   3   4  1 4 3 2 )
D	reflection across y = −x	[  0  −1  −1   0  ]	(  1   2   3   4  3 2 1 4 )

Claim: The above 8 are the only symmetries of the square.
Proof: Consider how an arbitrary symmetry X moves the vertices 1,2,3,4.

• Choose X(1) = 1,2,3,4.
• Given X(1), choose X(2) = X(1) ± 1, one of the two neighbors of X(1).
• X(3) must be the unique unused neighbor of X(2)
• X(4) must be the unique unused neighbor of X(3).

Thus, there are at most 4×2 = 8 choices of symmetry, and we have found all of them above.

1c. The group table of G:

⚬	I	R	R2	R3	A	B	C	D
I	I	R	R2	R3	A	B	C	D
R	R	R2	R3	I	D	C	A	B
R2	R2	R3	I	R	B	A	D	C
R3	R3	I	R	R2	C	D	B	A
A	A	C	B	D	I	R2	R	R3
B	B	D	A	C	R2	I	R3	R
C	C	B	D	A	R3	R	I	R2
D	D	A	C	B	R	R3	R2	I

To compute compositions, we can multiply the corresponding matrices, or compose permutations. For example, doing A after R:

A ⚬ R  =  (

1	2	3	4
2	1	4	3

) ⚬ (

1	2	3	4
2	3	4	1

)   =   (

1	2	3	4
1	4	3	2

)   =   C,

since:

A(R(1)) = A(2) = 1  ,  A(R(2)) = A(3) = 4  ,  A(R(3)) = A(4) = 3  ,  A(R(4)) = A(1) = 2.

• Standard groups
  • Symmetric group S_n = Sym{1, . . . , n}, all permutations of n objects; |S_n| = n!
  • Dihedral group D_n, rigid symmetries of regular n-gon; n rotations, n reflections, |D_n| = 2n
  • Cyclic group C_n, rotations only of regular n-gon; C_n = {I, R, R², . . . , Rⁿ⁻¹} with Rⁿ = 1
    Relabeling Rⁱ with [i] gives addition table of Z_n: isomorphism (C_n, ·) ≅ (Z_n, +)
  • General linear group GL_n(R) = {invertible A ∈ M_n}, symmetries of vector space Rⁿ
  • More structure ⇒ less symmetry: subgroups  C_n ⊂ D_n ⊂ S_n
  • Write symmetries in G as permutations: subgroup  G ⊂ S_n
    Write plane symmetries in G as linear mappings: subgroup  G ⊂ GL₂(R)
• Any ring (R, +, ·) gives two groups
  • additive group (R, +)
  • multiplicative group (R^×, ·), where R^× = {units u ∈ R}
• Abstract group:  (G, ·) obeying the operation axioms in notes for all A,B,C ∈ G:  
  • Closed operation:  A·B ∈ G
  • Associative:  A·(B·C) = (A·B)·C
  • Identity:  A·I = I·A = A
  • Inverses:  all A have A⁻¹ with A·A⁻¹ = A⁻¹·A = I
• Any abstract group G can be represented as symmetries of some object:  G = Sym(S).
  Example: Given additive group (Z, +), represent Z = Sym(S) for some S
  Adding n ∈ Z gives a symmetry of S = Z itself: shift  a ↦ a+n.
  To ensure reflections like a ↦ −a are not symmetries, give S orientation structure (arrows)
  

• An abstract group may represent several different types of symmetries.
  Example:  G = {I, C} with C² = I
  • C can represent a reflection (bilateral symmetry):  S = butterfly or stick man
  • C can represent a 180° rotation (point symmetry):  S = parallelogram or 2-bladed propeller

Reading: Ch 7.1, pp. 169-180.    
HW:

1. Consider the group G = GL₂(Z₂), invertible matrices with entries in the clock-number field Z₂, under matrix multiplication.
   1. Write the multiplication table of G.
   2. What known group is this isomorphic to?
   3. By definition, G is the symmetries of the vector space F² for F = Z₂. Find a representation of G as all permutations of a set.
      Hint: What are the vectors of F²?
2. Find the number of elements in G = GL₂(Z_p), invertible matrices with entries in field Z_p for a prime p. How many elements in G?
   Hint: The columns of an invertible matrix make a basis of F². Count the choices of each vector.
3. Extra Credit: Find the number of elements in G = GL_n(F), where F is a finite field with q elements, such as F = Z_p with q = p elements.

1a. A matrix in G = GL₂(Z₂), has columns which are a basis of F² for F = Z₂. Choosing the basis vectors one at a time:

[

1	0
0	1

]     [

0	1
1	0

]     [

1	1
1	0

]
[

1	1
0	1

]     [

0	1
1	1

]     [

1	0
1	1

]

Find the multiplication table by multiplying matrices.

1b. G is non-commutative; it has an identity I, three elements with A² = I, and two elements with A³ = I. This is just like the group D₃ in HW 11/14 #2, the symmetries of a triangle; D₃ is also isomorphic to S₃, since the symmetries permute the 3 vertices of the triangle in all possible ways.

1c. Since G ≅ S₃, it can be represented as permuting 3 objects. We can take these to be the three non-zero vectors in F² for F = Z₂:

F²  =  { (0,0), v₁ = (1,0), v₂ = (0,1), v₃ = (1,1) }.

The corresponding permutations are:

[

1	0
0	1

] = (

1	2	3
1	2	3

)     [

0	1
1	0

] = (

1	2	3
2	1	3

)     [

1	1
1	0

] = (

1	2	3
3	1	2

)
[

1	1
0	1

] = (

1	2	3
1	3	2

)     [

0	1
1	1

] = (

1	2	3
2	3	1

)     [

1	0
1	1

] = (

1	2	3
3	2	1

).

Reading: Wikipedia
HW:

1. Extra Credit: Let T be the tetrahedron, a pyramid whose three sides and bottom are all equilateral triangles. Let G = Sym(T) be its rigid symmetry group, including rotations, reflections, and their compositions.
   1. Clearly G ⊂ S₄, since each symmetry permutes the four vertices. Show that |G| = 4! = 24 and G ≅ S₄.
   2. List all the symmetries as permutations using two-line notation, or the more compact cycle notation. Describe each symmetry geometrically, by how it moves space.
   3. Determine the coordinates of the corners, and give 3×3 matrices for (some of) the above symmetries.
2. Extra Credit: Same for symmetries of a cube C, having corners (±1,±1,±1).
   1. Describe all rotation and reflection symmetries as permutations of the 6 faces (easier than permutations of the 8 vertices), and show |G| = 48.
   2. Describe the symmetries geometrically, and as matrices.
   3. Further, let H ⊂ G be the subgroup of rotations only. Show that |H| = 24. In fact, H ≅ S₄: what 4 objects inside the cube are permuted in all possible ways?

• An abstract group is defined solely by its multiplication table obeying the four group axioms, without considering its representations as symmetries.
• We change notation slightly, denoting the identity as e ∈ G rather than I. For any a,b,c ∈ G:
  • Closed operation:  a·b ∈ G
  • Associative:  a·(b·c) = (a·b)·c
  • Identity:  a·e = e·a = a
  • Inverses:  all a have a⁻¹ with a·a⁻¹ = a⁻¹·a = e
  Furthermore, G is a commutative or abelian group if it obeys:
  • Commutative:  ab = ba
• In the propositions below, a,b,c ∈ G are arbitrary elements of a group.
• Uniqueness of identity: There can be only one identity element in G.
  Proof: Suppose e, e' ∈ G both obey the Identity axiom. Then e = ee' because e' is an identity, and e' = ee' because e is an identity. Thus e = e' (by transitivity of equality), so there is only one identity.
• Cancellation law: If ab = ac, then b = c.
  Proof: If ab = ac, then a⁻¹(ab) = a⁻¹(ac) (by substitution of equal quantities), so (a⁻¹a)b = (a⁻¹a)c (by Associativity), and eb = ec (by Inverses), and b = c (by Identity).
• Inverse of a product: (ab)⁻¹ = b⁻¹a⁻¹.
  Compact proof: We have (ab)(b⁻¹a⁻¹) = a(bb⁻¹)a⁻¹ = aa⁻¹ = e. Thus b⁻¹a⁻¹ is inverse to ab.
• Right-inverse equals left-inverse: If ab = e and ca = e, then b = c.
  Two-column proof:

  Suppose ab = e and ca = e.	State hypothesis
  Then:   c = ce,	Identity
  ce = c(ab),	Use hypothesis
  c(ab) = (ca)b,	Associativity
  (ca)b = eb,	Use hypothesis
  eb = b.	Identity
  Therefore   c = b.	Transitivity of equality

• The order of a ∈ G is:   ord(a)  =  min{ i > 0  with  aⁱ = e }, if the above set is non-empty, and ord(a) = ∞ if aⁱ ≠ e for all i > 0.
• Proposition: In a finite group G, any element has finite order.
  Proof: Since G is finite, the sequence a¹, a², . . . cannot have infinitely many distinct elements, so we must have aⁱ = a^j for some 0 < i < j. Therefore a^j−i = e, and the set { i > 0  with  aⁱ = e } is non-empty and has a minimal element k = ord(a).
• For any element of finite order k = ord(a), consider the set  ⟨a⟩ = {aⁱ  for  i ∈ Z}, where  a⁻ⁱ = (a⁻¹)ⁱ. Then ⟨a⟩ is a cyclic group isomorphic to C_k ≅ (Z_k, +), the additive group of clock arithmetic. In fact, the mapping f : ⟨a⟩ → Z_k with f(aⁱ) = [i] is an isomorphism.

Reading: Ch 7.2, pp. 196-200; Ch 7.3, pp. 203-207.    
HW:

1. Prove: If (ab)² = a²b² for all a,b ∈ G, then G is abelian (commutative).
2. Hand In Mon 12/3: Give two-column proofs assuming only the four axioms of an abstract group G.
   1. Inverses are unique: If ac = ca = e and ab = ba = e, then b = c.
   2. Inverse of an inverse:  (a⁻¹)⁻¹ = a.
3. Hand In Mon 12/3: Proposition: Let a ∈ G have finite order k = ord(a). Then aⁱ = e if and only if k divides i.
   Give a compact proof separated into (⇒) and (⇐) directions. You may assume everything we know about ring of integers.
   Hint: Show that the set I = { i ∈ Z with  with  aⁱ = e } is an ideal of Z. What do we know about such ideals?

1. Prop: If (ab)² = a²b² for all a,b ∈ G, then G is abelian.
Pf: Suppose (ab)² = a²b². This means abab = aabb, so  a⁻¹(abab)b⁻¹  =  a⁻¹(aabb)b⁻¹  and thus  ba = ab, meaning G is commutative.

• Let H ⊂ G be a subgroup; that is, a subset which is itself a group. The coset of H containing g ∈ G is the set
  gH  =  { gh for h ∈ H }.

• Example: For the dihedral group G = D₄ = {e, r, r², r³, a, b, c, d} from HW 11/14 #1, consider the cyclic subgroup H = ⟨r⟩ = {e, r, r², r³}. For h ∈ H, the coset hH = H is just a row of the multiplication table of H: it is just the set H itself. Other cosets (reading from the multiplcation table of G) are:
  aH = {a, b, c, d}, bH = {b, d, a, c}, cH = {c, b, d, a}, dH = {d, a, c, b}.
  That is, there are only two distinct cosets: H and aH = bH = cH = dH = {a,b,c,d}, and G = H ∪ aH, partitioning G into two disjoint subsets.
• Lemma:
  1. Two cosets are equal or disjoint: either aH = bH or aH ∩ bH = {}.
  2. Any cosets has the same number of elements as H: that is, |aH| = |H|
  3. The group is a union of cosets: G = a₁H ∪ ··· ∪ a_ℓH for a₁, . . . , a_ℓ ∈ G.
  Proof:
  1. Suppose aH and bH are not disjoint, so there is some c ∈ aH ∩ bH. That is, c = ah = bh' for h, h' ∈ H. That is, a = bh'h⁻¹, so that aH = bh'h⁻¹H = bH, since h'h⁻¹H = H is a row of the multiplication table of H.
     Therefore, the only possiblilities are that aH and bH are disjoint, or they overlap and aH = bH.
  The proofs of (ii), (iii) are exercises below.
• The number of distinct cosets in G = a₁H ∪ ··· ∪ a_ℓH is called the index of H in G, denoted ℓ = [G:H].
• Lagrange's Theorem: For finite groups H ⊂ G, the number of elements in G is the index of H in G, times the number of elements in H:
  |G|  =  [G:H] |H|.
  Proof: By Lemma (iii), G splits into a union of ℓ = [G:H] disjoint cosets, which by Lemma (ii) each have |H| elements. That is the number of elements in G is ℓ times |H|.
• Fermat's Little Theorem: For any prime p and any integer a, we have p | a^p − a.
  Proof:
  • The assertion is equivalent to a^p ≡ a mod p, or [a]^p = [a] in the finite field Z_p. In fact, for [a] ≠ [0] this is equivalent to [a]^p−1 = [1].
  • Now consider the multiplicative group of units Z_p^× = Z_p − {[0]}. For any [a] ≠ [0], we have the cyclic group H = {[1], [a], [a]², . . . , [a]^k−1}, where [a]^k = [1] for k = ord[a], the order of [a].
  • By Lagrange's Theorem, the size of the subgroup |H| = k is a divisor of the size of the whole group |Z_p^×| = p−1, so that p−1 = kℓ for ℓ ∈ Z.
  • Finally, we see: [a]^p−1 = [a]^kℓ = [1]^ℓ = [1], which was to be shown.

Reading: Ch 8.1, pp. 240-242 only.
HW:

1. Find all the subgroups H ⊂ G = D₃, and for each one, explicitly split G into its cosets.
   Also: draw a triangle with decorations which reduce the symmetry group to H.
2. Prove Lemmas (ii), (iii) above: why do the cosets all have the same size as H, and why does every element of G lie in some coset of H?
   Hints: For (ii), consider the mapping f : H → aH given by f(h) = ah. For (iii), explicitly find the coset aH which contains a particular element g ∈ G.
3. Hand In Mon 12/3: Find all subgroups H of G = D₄, the symmetries of the square, and for each H:
   1. Find |H| and ℓ = [G:H], and give specific elements a₁, . . . , a_ℓ ∈ G with G = a₁H ∪ ··· ∪ a_ℓH.
   2. Draw a square with decorations which reduce the symmetry group to H.
   3. Say if H is a normal subgoup, and if so, give the multiplication table of the quotient group G/H.

1. Write the dihedral group as G = D₃ = {e, r, r², a, b, c} with multiplication table:

·	e	r	r2	a	b	c
e	e	r	r2	a	b	c
r	r	r2	e	c	a	b
r2	r2	e	r	b	c	a
a	a	b	c	e	r	r2
b	b	c	a	r2	e	r
c	c	a	b	r	r2	e

The smallest subgroups are the cyclic subgroups ⟨g⟩; these are H = ⟨r⟩, ⟨a⟩, ⟨b⟩, ⟨c⟩. It is easy to see that repeatedly multiplying any outside element with any of these produces all of G, so they are the only subgroups (along with the trivial subgroups {e} and G itself). We have:

G  =  ⟨r⟩ ∪ a⟨r⟩  =  {e, r, r²} ∪ {a, b, c}

G  =  ⟨a⟩ ∪ r⟨a⟩ ∪ r²⟨a⟩  =  {e, a} ∪ {r, c} ∪ {r², b}

Similarly for the others.

Finally, each subgroup is the symmetry group of a decorated version of the triangle: the extra structures decrease the amount of symmetry from G to H. The rotation subgroup H = ⟨r⟩ is symmetries of an oriented triangle:

The subgroup H = ⟨a⟩, where a is horizontal reflection across the y-axis, is symmetries of a triangle with the bottom distinguished from the other sides:

2(ii)  Prop: |aH| = |H|. Pf: I claim the mapping f : H → aH given by f(h) = ah is one-to-one and onto, which immediately implies that H and aH have the same size. Indeed, f is one-to-one, since f(h) = f(h') means ah = ah', which gives h = h' by cancellation. Finally, f is onto, since if ah ∈ aH, then ah = f(a).

2(iii)  Prop: G is a disjoint union of cosets. Pf: Any g ∈ G lies in the coset gH, since g = ge and e ∈ H. Thus, the cosets cover all of G, and they are disjoint by Lemma (i).

• Syllabus of Topics I
• Chapter 4.6. Real and complex polynomials
  • Fundamental Thm of Algebra: Every f(x) ∈ C[x] has root x = a ∈ C with f(a) = 0.
    Every f(x)  =  c(x−a₁)···(x−a_n) for a_i ∈ C. Irreducibles in C[x] are linear x−a.
  • Irreducibles in R[x] are linear x−a and quadratic ax²+bx+c with b²−4ac < 0. Every f(x) ∈ R[x] is a product of linear and quadratic in R[x].
• Chapter 5. Polynomial modular rings
  • Congruence in F[x] modulo polyonomial p(x)
    f(x) ≡ g(x) mod p(x)  ⇔  p(x) | f(x)−g(x)  ⇔  f(x) = g(x) + q(x)p(x)
  • Congruence class  [f(x)]  =  {g(x) ≡ f(x) mod p(x)}
    [p(x)] = [0],   [f(x)] = [f(x)+q(x)p(x)]
  • Quotient ring  F[x]/(p(x)) ∋ [f(x)]
    Add  [f(x)] + [g(x)] = [f(x)+g(x)],  multiply [f(x)]·[g(x)] = [f(x) g(x)]
  • Standard form [f(x)] = [q(x)p(x) + r(x)] = [r(x)] for deg r(x) < deg p(x)
  • Reciprocals:  for gcd(f(x),p(x)) = 1, Euclidean Algor  f(x)g(x) + p(x)q(x) = 1
    [f(x)][g(x)] = [1],   [f(x)]⁻¹ = [g(x)]
  • Extension field: irrational α ∈ R root of p(α) = 0 for irreducible p(x) ∈ Q[x]
    Q[α] = {f(α) for f(x) ∈ Q[x]},  Q[α] ≅ Q[x]/(p(x)),  α ↔ [x]
  • Finite extension field:  Irred p(x) ∈ Z_p[x]
    Field  F = Z_p[x]/(p(x))  with pⁿ elements, n = deg p(x)
• Chapter 6. Ideals and quotient rings
  • Ideal I in ring R
    Closed under addition:  i, i' ∈ I  ⇒  i+i' ∈ I
    Closed under mult by R:  i ∈ I, r ∈ R  ⇒  ir ∈ I
  • Purpose of ideals: quotient ring R/I with I = [0] zero-class
    i+i' ∈ I because [0]+[0] = [0],  ir ∈ I because [0][r] = [0]
  • Congruence mod I:  a ≡ b mod I
        ⇔   a−b ∈ I   ⇔   a = b+i for i ∈ I
  • Congruence class [a]  =  { b ≡ a mod I }  =  a + I
  • [0] = I,  [a] = [a+i]
  • Quotient ring  R/I ∋ [a],  add  [a] + [b] = [a+b],  multiply [a]·[b] = [ab]
    Well-defined: [a] = [a'] , [b] = [b']  ⇒  [a+b] = [a'+b'],  [ab] = [a'b']
  • Principal ideal:  (r) = {ar for a ∈ R} all multiples of r
    Finitely generated ideal: (r,s) = (r) + (s) = {ar + bs for a,b ∈ R}
  • In R = Z, all ideals are principal, I = (r)
    In R = F[x], all ideals are principal, I = (r(x))
    Proof uses Extended Euclidean Algorithm
  • Maximal ideal I ⊂ R means: no ideals bigger than I, smaller than R
    I is a maximal  ⇔  R/I is a field;   large I  ⇔  small, nice R/I
    In R = Z, max ideals are I = (p) for p prime, quotient fields Z/(p) ≅ Z_p
    In R = F[x], max ideals are I = (p(x)) for p(x) irred, quotient fields F[x]/(p(x))
  • Kernel of homomorphism φ : R → S is Ker(φ) = {r ∈ R with φ(r) = 0}, an ideal.
    Ker(φ) = {0}  ⇔  φ is one-to-one;   large Ker(φ)  ⇔  φ is far from one-to-one
  • Ideals  ⇔  onto homomorphisms
    Ideal I ⊂ R   ⇒   onto homomorphism φ : R → R/I,  r ↦ [r]
    Onto homomorphism φ : R → S   ⇒   S ≅ R/I for I = Ker(φ)
• Chapter 7: Groups and symmetry
  • Symmetry of object X: invertible mapping A : X ↔ X preserving structure
    For rigid shape X, symmetry takes X onto itself with no stretching or shrinking
  • Symmetry group G = Sym(X) = {all symmetries of X}
    Composition operation C = A∘B with C(x) = A(B(x)) for x ∈ X
  • Compute symmetry as linear mapping A : R² → R²
    Matrix  [A] = [

    a	c
    b	d

    ]  where A(1,0) = (a,b),  A(0,1) = (c,d)
  • Compute symmetry as permutation of vertices A : {1,...,n} → {1,...,n}
    Two-line notation A = (

    1	2	···	n
    A(1)	A(2)	···	A(n)

    ).
  • Abstract group G defined by multiplication table alone
    Representation of G is X with G = Sym(X)
    Example: G = {I, R} with R² = I
    Representation as bilateral reflection symmetry; or as 180° rotation symmetry
  • Axioms for abstract group G, for all a,b,c ∈ G

    Closed:	ab ∈ G
    Associative:	(ab)c = a(bc)
    Identity:	e ∈ G  with  ea = ae = a
    Inverses:	a−1 ∈ G  with  aa−1 = a−1a = e

  • Abelian group also has  Commutative:   ab = ba
    Denote with mult operation (G, · ) or addition operation (G, +)
  • Examples of groups
    Symmetric S_n, all permutations of {1,...,n}
    Cyclic C_n = {e, r, r², . . . , rⁿ⁻¹} with rⁿ = e, rotation sym of n-gon
    Dihedral D_n = {e, n−1 rotations & n reflections of n-gon}
    GL_n(F) = {invertible n×n matrices, entries in F}
  • Ring (R, +, · ) gives two groups
    Additive group (R, +) abelian; example: (Z_n, +) ≅ (C_n, · )
    Multiplicative group (R^×, · ) for R^× = {units u ∈ R}
  • Cyclic subgroup of a ∈ G is ⟨a⟩ = {aⁱ for i ∈ Z}
    Order  ord(a) = min{i > 0 with aⁱ = e};  ord(a) = ∞ if aⁱ ≠ e for all i
    Cyclic  ⟨a⟩ ≅ C_n  for  n = ord(a)
    Infinite cyclic  ord(a) = ∞  means  ⟨a⟩ ≅ (Z, +) ≅ C_∞
  • Subgroup H ⊂ G means H is closed under mult and inverses
    If G = Sym(X), then H = Sym(Y) for Y = X with asymmetric decorations
  • Cosets:  aH = {ah for h ∈ H}; cosets are disjoint from each other
    Cosets partition the group:  G  =  a₁H ∪ ··· ∪ a_ℓH
    Index [G : H] means number of distinct cosets = ℓ
  • Lagrange's Theorem:  For a subgroup H ⊂ G, number of elements in H divides the number of elements in G; in fact |G| = |H| [G : H].
    Proof:  G  =  a₁H ∪ ··· ∪ a_ℓH,  with  |a_iH| = |H|, so  |G| = |H| ℓ = |H| [G : H].
  • Corollary:  For a ∈ G,  ord(a) divdes n = |G|, and aⁿ = e.
    Fermat's Little Theorem:  In Z_p for p prime, get [a]^p = [a], i.e. p divides a^p−a.

The most important topic on the Final Exam will be quotient rings:  Z_n = Z/(p),  F[x]/(f(x)),  and general R/I; and computing reciprocals with the Euclidean Algorithm.
1. Examples in rings: Give examples of the following situations.
   1. A ring element r ∈ R which is neither a zero-divisor nor a unit.
   2. Zero-divisors z,w ∈ R with zw = 0 but wz ≠ 0.
      Hint: Let R = M₂ and w = [

      1	0
      0	0

      ]. Considering matrices as linear mappings z,w : R²→R², the equation zw = 0 means Ker(z) ⊃ Im(w).
2. Construct the following rings, all having 16 elements.
   1. A ring where every element r ≠ 0,1 is a zero-divisor.
   2. A field. Hint: Find an irreducible degree 4 polynomial f(x) ∈ Z₂[x], and take the quotient ring Z₂[x]/(f(x)). Explain why this has 16 elements, and how to add and multiply them.
   3. A non-commutative ring
   4. In addition to the above, find as many as possible other rings with 16 elements, and prove that none are isomorphic to each other.
3. Suppose that in a field F, every a ≠ 0 satisfies a⁻¹ = a. Prove that F is isomorphic to Z₂ or Z₃.
   Hint: Solve the equation x⁻¹ = x in a general field. Then show that any field with 2 or 3 elements must be isomorphic to the ones we know.
4. Ideals
   1. Show that a field F has no ideals except (0) and (1) = F. That is, (0) is a maximal ideal.
   2. For any rings R, S, show that all ideals of the product ring R×S are of the form I×J, where I is an ideal of R and J is an ideal of S. Hint: This is a two-part proof: first that I×J is an ideal, second that any ideal K ⊂ R×S is of the form K = I×J.
   3. Find an isomorphism from Z₁₅ to the product R×S = Z₃×Z₅, and an inverse isomorphism the other way. Hint: Use the Chinese Remainder Theorem.
   4. Use the above to find all ideals of Z₁₅.

1a. Take R = Z integers or F[x] polynomials. Then there are no zero-divisors, but there are only a few units: ±1 ∈ Z and f(x) = c ∈ F[x]. Any other elements are neither zero-divisors nor units.

Recall the definitions: a zero-divisor multiplies to give 0; a unit multiplies to give 1; there is no reason an arbitrary element must have one or the other, though this does happen for some rings, such as R = Z_n and R = M₂.

1b. In the matrix ring R = M₂(R), the linear mapping w = [

1	0
0	0

] has Im(w) = R(1,0), i.e. the output space is the x-axis; and Ker(w) = R(0,1), i.e. the y-axis is crushed to zero. Now choose z so it takes the x-axis to zero: z = [

0	a
0	b

] for any (a,b); then z(w(x,y)) = z(x,0) = (0,0), and the composition is zw = 0. However, Ker(z) = R(1,0) and Im(z) = R(a,b), so taking a ≠ 0, we find w(z(1,0)) = w(a,b) = (a,0) ≠ (0,0), and wz ≠ 0. We can take our final answer to be:

w = [

1	0
0	0

]           z = [

0	1
0	0

].

Here we used the linear algebra meaning of kernel for a linear mapping like w : R² → R², namely Ker(w) = {v such that w(v) = 0}. This is analogous to the ring definition of kernel for a homomorphism φ : R → S, namely Ker(φ) = {r such that φ(r) = 0}. In both cases, the larger the kernel, the farther the mapping is from being one-to-one.

2a. Suppose R is a ring where every r ≠ 0,1 is a zero-divisor. Now, −1 is never a zero-divisor (since −a = (−1)a = 0 implies a = 0), so we must have −1 = 1. Thus R must be built up from Z₂. Indeed, R = Z₂×Z₂ works, or to get 16 = 2⁴ elements we take R = Z₂×Z₂×Z₂×Z₂ with 14 zero-divisors.

2b. We construct a field with 16 = 2⁴ elements as an extension of Z₂. First, we need a degree 4 irreducible polynomial p(x) ∈ Z₂[x]. The leading term is x⁴; and p(x) has no linear factor, hence no root, so p(0) ≠ 0 and the constant term is 1; also p(1) ≠ 0 so there is an odd number of terms. Thus p(x) could be:

x⁴+x³+1,  x⁴+x²+1,  x⁴+x+1,  x⁴+x³+x²+x+1.

However, ruling out linear factors is not enough to guarantee p(x) is irreducible: the unique degree 2 irreducible polynomial x²+x+1 gives the reducible polynomial (x²+x+1)² = x⁴+x²+1, which is why the second polynomial on the list is crossed out.

Now take p(x) ∈ Z₂[x] = R to be any of the above 3 choices, take the principal ideal I = (p(x)) = {g(x)p(x) for g(x) ∈ Z₂[x]}, and construct K = R/I = Z₂[x]/(p(x)), the quotient or modular ring consisting of classes

[f(x)]  =  f(x) + I  =  {f(x) + g(x)p(x) for g(x) ∈ Z₂[x]}

with [p(x)] = [0] and [f(x)] = [f(x) + g(x)p(x)] for any g(x). Dividing f(x) by p(x), we have [f(x)] = [q(x)p(x) + r(x)] = [r(x)] for a remainder with deg r(x) < deg p(x) = 4. Thus, any class can be put into the standard form

[f(x)]  =  [r(x)]  =  [ax³ + bx² + cx + d]

The choice of a,b,c,d ∈ Z₂ gives 2⁴ = 16 elements. The ring K is a field, because for any standard for r(x) ≠ 0, we have gcd(r(x),p(x)) = 1, and r(x)s(x) + p(x)t(x) = 1 for s(x), t(x) ∈ Z₂[x] by the Extended Euclidean Algorithm. Thus [r(x)][s(x)] + [0][t(x)] = [1], and [r(x)]⁻¹ = [s(x)] ∈ K.

2c. The only non-commutative rings we have covered are M_n(F), the n×n matrices with entries in a field F. If F is a finite field with q elements, the ring M_n(F) has q^m2 elements; so M₂(Z₂) has 2⁴ = 16 elements.

2d. We can take products of modular rings Z₂, Z₄, Z₈, Z₁₆ and fields F₄, F₈, F₁₆ to get commutative rings with 16 elements:

Z₁₆,   Z₈×Z₂,   Z₄×Z₄,   Z₄×Z₂×Z₂,   (Z₂)⁴,
F₁₆,   F₈×Z₂,   F₄×F₄,   F₄×Z₂×Z₂,   F₄×Z₄.  

To show these are not isomorphic, we need to find algebraic properties which are unique to each, since any isomorphism would establish identical algebraic properties. For example, consider the numbers of zero-divisors:

7,   11,   11,   13,   14,
0,   9,   7,   12,   9.

This gives three possible pairs of isomorphic rings, and looking at their units does not help, since here every element is either zero, a zero-divisor, or a unit. However, Z₁₆ is not isomorphic to F₄×F₄, since in the first ring 1+1 = 2 ≠ 0, but in the second ring 1 + 1 = 0 since each factor is an extension of Z₂. Similarly for the pair Z₈×Z₂,  Z₄×Z₄, and the pair F₈×Z₂,  F₄×Z₄.

Of course the non-commutative M₂(Z₂) cannot be isomorphic to any of the above commutative rings.

3. Suppose F is a field with a⁻¹ = a for all a ≠ 0. Now, for x ≠ 0, the equation x⁻¹ = x is equivalent to x² = 1, to x² − 1 = 0, to (x−1)(x+1) = 0, which has the solutions x = ±1. Since every x = a ∈ F satisfies this equation, we must have a three-element field F = {0,1,−1} or a two-element field F = {0,1 = −1}. Now consider the standard ring homomorphism φ : Z → F with φ(±k) = ±(1+···+1) with k 1's. Then by the First Isomorphism Theorem, the image of φ is isomorphic to Z/(n) = Z_n for I = Ker(φ) = (n). Thus Z_n is a subring of F, which means Z₃ = F in the first case or Z₂ = F in the second case.

4a. Proposition: In a field F, the only ideals are (0) and (1).
Proof: Let I be an ideal of the field F. If I ≠ (0), then I contains some a ≠ 0, so that a⁻¹ ∈ F, and 1 = aa⁻¹ ∈ I by the sucking-in property. Hence for any b ∈ F, we have b = b1 ∈ I, and I = F.

4b. Proposition: The only ideals of R×S are I×J for ideals I ⊂ R and J ⊂ S.

Proof: First, we show that I×J is an ideal. Indeed, for (i₁,j₁), (i₂,j₂) ∈ I×J, we have i₁+i₂ ∈ I and j₁+j₂ ∈ J since I and J are ideals, so

(i₁,j₁) + (i₂,j₂)  =  (i₁+i₂, j₁+j₂)  ∈  I×J,

which shows I×J is closed under addition. Similarly, I×J is closed under multiplication by R×S, and I×J satisfies the two properties of an ideal.

Second, suppose K is any ideal of R×S. Let

I = {i ∈ R with (i,j) ∈ K for some j ∈ S},

and similarly for J ⊂ S, so that K ⊂ I×J by definition. We show I is an ideal. If i₁, i₂ ∈ I because (i₁, j₁), (i₂, j₂) ∈ K, then

(i₁+i₂, j₁+j₂)  =  (i₁,j₁) + (i₂,j₂)  ∈  K,

since K is an ideal; and thus i₁+i₂ ∈ I. A similar argument shows ir ∈ I for any i ∈ I, r ∈ R. Also J is ideal by the same argument.
Finally, consider an arbitrary element (i₁, j₂) ∈ I×J, where i₁ ∈ I because (i₁, j₁) ∈ K, and j₂ ∈ J because (i₂, j₂) ∈ K. Then:

(i₁, j₂)  =  (i₁, 0) + (0, j₂)  =  (i₁, j₁)(1,0) + (i₂, j₂)(0,1)  ∈  K,

since K is closed under under multiplication by R×S and under addition within itself. This shows I×J ⊂ K, and hence I×J = K.

4c. We have the standard homomorphism φ : Z₁₅ → Z₃×Z₅ defined by φ([a]₁₅) = ([a]₃, [a]₅). This is an isomorphism, since we can check by a table that it is one-to-one and onto.

Z15	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
Z3×Z5	(0,0)	(1,1)	(2,2)	(0,3)	(1,4)	(2,0)	(0,1)	(1,2)	(2,3)	(0,4)	(1,0)	(2,1)	(0,2)	(1,3)	(2,4)

In the second row, every possible output appears exactly once. The mapping is one-to-one because no output appears more than once; it is onto because every possible output appears at least once.

We also want an inverse isomorphism:

ψ : Z₃×Z₅ → Z₁₅,       ψ([a]₃, [b]₅)  =  [c]₁₅,

which maps back to the original input:

φ([c]₁₅)  =  ([c]₃, [c]₅)  =  ([a]₃, [b]₅).

To compute this mapping, for given integers a,b, we need c with c ≡ a mod 3 and c ≡ b mod 5. This is found by the Chinese Remainder Theorem. First, write 3m + 5n = 1 for m = 2, n = −1, so that 5n = 1 − 3n and 3m = 1 − 5m. Then let c = 5na + 3mb, so that:

c  =  (1−3n)a + 3mb  ≡  a mod 3,     c  =  5na + (1−5m)b  ≡  b mod 5.

That is:

ψ([a]₃, [b]₅)  =  [5na + 3mb]₁₅  =  [−5a + 6b]₁₅.

Indeed, this finds the elements of Z₁₅ which correspond to the generators of Z₃ and Z₅: that is, −5 ↔ (1,0) and 6 ↔ (0,1).

4d. Since part (c) shows Z₁₅ ≅ Z₃×Z₅, a product ring, we can use part (b) to find its ideals I×J for ideals I ⊂ Z₃ and J ⊂ Z₅. Now, Z₃ and Z₅ are fields, so by part (a) their only ideals are the trivial ideals (0) and (1). This means the only non-trivial ideals of Z₃×Z₅ are the principal ideals generated by (1,0) and (0,1). We send these back to Z₁₅ via the isomorphism ψ of part (c):

ψ([1]₃, [0]₅) = [−5]₁₅   and   ψ([0]₃, [1]₅)  =  [6]₁₅.

That is, other than (0) and (1), the only ideals of Z₁₅ are (−5) = (5) and (6) = (3). We did not really need the isomorphism to figure this out, but this analysis generalizes to find the ideals of any Z_n. Also, it focused our attention on the two elements a = −5, 6 ∈ Z₁₅; since (1,0)² = (1,0) and (0,1)² = (0,1), we conclude that these are the two idempotent elements, satisfying a² = a.

• Midterm review above
• Group problems Hand-in HW 12/3 solutions
• Modular rings review with solutions