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.

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."

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.

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:

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:

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

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.

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.

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].

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:

• 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.

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.

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

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].

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.

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₂₉.

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)

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.)

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.

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.

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.

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:

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

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:

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

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.

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. 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

(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.

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

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]:

• 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)

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:

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:

• 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.

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'x²]

  = [ss' + st'x + s'tx + tt'(x²+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.

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.

• 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.

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:

• 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).

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:

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 − α:

• 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}

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

• 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).

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'].

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:

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.

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.

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: