Abstract Algebra

Well-Ordering Axiom

Every nonempty set of nonnegative integers contains a smallest element.

Theorem 1.1: The Division Algorithm

Let \(a, b\) be integers with \(b > 0\). Then there exist unique integers \(q\) and \(r\) such that: $$ a = bq + r \quad \text{and} \quad 0 \leq r < b. $$

Definition of Divisibility

Let \(a\) and \(b\) be integers with \(b \neq 0\). We say that \(b\) divides \(a\) (or that \(b\) is a divisor of \(a\), or that \(b\) is a factor of \(a\)) if \(a = bc\) for some integer \(c\). In symbols, "b divides a" is written \(b | a\) and "b does not divide a" is written \(b \nmid a\).

Definition of Greatest Common Divisor

Let \(a\) and \(b\) be integers, not both 0. The greatest common divisor (gcd) of \(a\) and \(b\) is the largest integer \(d\) that divides both \(a\) and \(b\). In other words, \(d\) is the gcd of \(a\) and \(b\) provided that:

1. \(d | a\) and \(d | b\);
2. If \(c | a\) and \(c | b\), then \(c \leq d\).

Theorem 1.2: The Linear Combination of the GCD

Let \(a\) and \(b\) be integers, not both 0, and let \(d\) be their greatest common divisor. Then there exist (not necessarily unique) integers \(u\) and \(v\) such that

$$ d = au + bv. $$

Corollary 1.3: Conditions for the GCD

Let \(a\) and \(b\) be integers, not both 0, and let \(d\) be a positive integer. Then \(d\) is the greatest common divisor of \(a\) and \(b\) if and only if \(d\) satisfies these conditions:

1. \(d \mid a\) and \(d \mid b\);
2. If \(c \mid a\) and \(c \mid b\), then \(c \mid d\).

Theorem 1.4: Divisibility Condition

If \(a \mid bc\) and \((a, b) = 1\), then \(a \mid c\).

Definition of Prime

An integer \(p\) is said to be prime if \(p \neq 0\), \(\pm 1\), and the only divisors of \(p\) are \(\pm 1\) and \(\pm p\).

Theorem 1.5: Primes Dividing a Product

Let \(p\) be an integer with \(p \neq 0, \pm 1\). Then \(p\) is prime if and only if it has the property:

$$ \text{whenever } p \mid bc, \text{ then } p \mid b \text{ or } p \mid c. $$

Corollary 1.6: Prime Divisors in Products

If \(p\) is prime and \(p \mid a_1a_2\cdots a_n\), then \(p\) divides at least one of the \(a_i\).

Theorem 1.7: Every Integer is a Product of Primes

Every integer \(n\) except 0, \(\pm 1\) is a product of primes.

Theorem 1.8: The Fundamental Theorem of Arithmetic

Every integer \(n\) except 0, \(\pm 1\) is a product of primes. This prime factorization is unique in the following sense: If

$$ n = p_1p_2\cdots p_r \quad \text{and} \quad n = q_1q_2\cdots q_s $$

with each \(p_i\), \(q_j\) prime, then \(r = s\) (that is, the number of factors is the same) and after reordering and relabeling the \(q_j\)'s,

$$ p_1 = \pm q_1, \quad p_2 = \pm q_2, \quad p_3 = \pm q_3, \quad \dots, \quad p_r = \pm q_r. $$

Corollary 1.9: Unique Factorization

Every integer \(n > 1\) can be written in one and only one way in the form

$$ n = p_1p_2p_3 \cdots p_r, $$

where the \(p_i\) are positive primes such that \(p_1 \leq p_2 \leq p_3 \leq \dots \leq p_r\).

Theorem 1.10: Primality Test

Let \(n > 1\). If \(n\) has no positive prime factor less than or equal to \(\sqrt{n}\), then \(n\) is prime.

Definition of Congruence Modulo \(n\)

Let a, b, n be integers with n > 0. Then a is congruent to b modulo n (written "a ≡ b (mod n)"), provided that n divides a - b.

Theorem 2.1: Congruence Properties Theorem

Let n be a positive integer. For all a, b, c ∈ ℤ:

1. \(a ≡ a \pmod{n}\);
2. if \(a ≡ b \pmod{n}\), then \(b ≡ a \pmod{n}\);
3. if \(a ≡ b \pmod{n}\) and \(b ≡ c \pmod{n}\), then \(a ≡ c \pmod{n}\).

Theorem 2.2: Addition and Multiplication Congruence Theorem

If \(a \equiv b \pmod{n}\) and \(c \equiv d \pmod{n}\), then:

1. \(a + c \equiv b + d \pmod{n}\);
2. \(ac \equiv bd \pmod{n}\).

Definition of Congruence Class

Let \(a\) and \(n\) be integers with \(n > 0\). The congruence class of \(a\) modulo \(n\) (denoted \([a]\)) is the set of all integers that are congruent to \(a\) modulo \(n\). That is:

Theorem 2.3: Equivalence of Congruence and Congruence Classes

\(a \equiv c \pmod{n}\) if and only if \([a] = [c]\).

Corollary 2.4: Disjointness or Identity of Congruence Classes

Two congruence classes modulo \(n\) are either disjoint or identical.

Corollary 2.5: Distinct Congruence Classes Modulo \(n\)

Let \(n > 1\) be an integer and consider congruence modulo \(n\).

1. If \(a\) is any integer and \(r\) is the remainder when \(a\) is divided by \(n\), then \([a] = [r]\).
2. There are exactly \(n\) distinct congruence classes, namely \([0], [1], [2], \dots, [n-1]\).

Definition of \(\mathbb{Z}_n\) ("Z mod n")

The set of all congruence classes modulo \(n\) is denoted \(\mathbb{Z}_n\) (which is read "Z mod n").

Theorem 2.6: Independence of Class Representatives

If \([a] = [b]\) and \([c] = [d]\) in \(\mathbb{Z}_n\), then:

\([a + c] = [b + d] \quad \text{and} \quad [ac] = [bd]\).

Properties of Modular Arithmetic

Now that addition and multiplication are defined in \(\mathbb{Z}_n\), we want to compare the properties of these "miniature arithmetics" with the well-known properties of \(\mathbb{Z}\). The key facts about arithmetic in \(\mathbb{Z}\) (and the usual titles for these properties) are as follows. For all \(a, b, c \in \mathbb{Z}\):

1. If \(a, b \in \mathbb{Z}\), then \(a + b \in \mathbb{Z}\). [Closure for addition]
2. \(a + (b + c) = (a + b) + c\). [Associative addition]
3. \(a + b = b + a\). [Commutative addition]
4. \(a + 0 = a = 0 + a\). [Additive identity]
5. For each \(a \in \mathbb{Z}\), the equation \(a + x = 0\) has a solution in \(\mathbb{Z}\).
6. If \(a, b \in \mathbb{Z}\), then \(ab \in \mathbb{Z}\). [Closure for multiplication]
7. \(a(bc) = (ab)c\). [Associative multiplication]
8. \(a(b + c) = ab + ac\) and \((a + b)c = ac + bc\). [Distributive laws]
9. \(ab = ba\). [Commutative multiplication]
10. \(a \cdot 1 = a = 1 \cdot a\). [Multiplicative identity]
11. If \(ab = 0\), then \(a = 0\) or \(b = 0\).

Theorem 2.7: Properties of Addition and Multiplication in \(\mathbb{Z}_n\)

For any classes \([a], [b], [c]\) in \(\mathbb{Z}_n\):

1. If \([a] \in \mathbb{Z}_n\) and \([b] \in \mathbb{Z}_n\), then \([a] \oplus [b] \in \mathbb{Z}_n\).
2. \([a] \oplus ([b] \oplus [c]) = ([a] \oplus [b]) \oplus [c]\).
3. \([a] \oplus [b] = [b] \oplus [a]\).
4. \([a] \oplus [0] = [a] = [0] \oplus [a]\).
5. For each \([a]\) in \(\mathbb{Z}_n\), the equation \([a] \oplus X = [0]\) has a solution in \(\mathbb{Z}_n\).
6. If \([a] \in \mathbb{Z}_n\) and \([b] \in \(\mathbb{Z}_n\), then \([a] \odot [b] \in \(\mathbb{Z}_n\).
7. \([a] \odot ([b] \odot [c]) = ([a] \odot [b]) \odot [c]\).
8. \([a] \odot ([b] \oplus [c]) = [a] \odot [b] \oplus [a] \odot [c]\) and \(([a] \oplus [b]) \odot [c] = [a] \odot [c] \oplus [b] \odot [c]\).
9. \([a] \odot [b] = [b] \odot [a]\).
10. \([a] \odot [1] = [a] = [1] \odot [a]\).

Theorem 2.8: Prime \(p\) and Equivalent Conditions in ℤ_p

If \(p > 1\) is an integer, then the following conditions are equivalent:*

1. \(p\) is prime.
2. For any \(a \neq 0\) in \(\mathbb{Z}_p\), the equation \(ax = 1\) has a solution in \(\mathbb{Z}_p\).
3. Whenever \(bc = 0\) in \(\mathbb{Z}_p\), then \(b = 0\) or \(c = 0\).

Theorem 2.9: Solving \(ax=1\) in ℤ_n

Let \(a\) and \(n\) be integers with \(n > 1\). Then:

The equation \([a]x = [1]\) has a solution in \(\mathbb{Z}_n\) if and only if \((a, n) = 1\) in \(\mathbb{Z}\).

Theorem 2.10: Conditions for Units in ℤ_n

Let \(a\) and \(n\) be integers with \(n > 1\). Then:

\([a] \text{ is a unit in } \mathbb{Z}_n \text{ if and only if } (a, n) = 1 \text{ in } \mathbb{Z}\).

A nonzero element \(a\) of \(\mathbb{Z}_n\) is called a zero divisor if the equation \(ax = 0\) has a nonzero solution (that is, if there is a nonzero element \(c\) in \(\mathbb{Z}_n\) such that \(ac = 0\)).

Definition of Rings

A ring is a nonempty set \(R\) equipped with two operations* (usually written as addition and multiplication) that satisfy the following axioms. For all \(a, b, c \in R\):

1. If \(a \in R\) and \(b \in R\), then \(a + b \in R\). [Closure for addition]
2. \(a + (b + c) = (a + b) + c\). [Associative addition]
3. \(a + b = b + a\). [Commutative addition]
4. There is an element \(0_R\) in \(R\) such that \(a + 0_R = 0_R + a = a\) for every \(a \in R\). [Additive identity or zero element]
5. For each \(a \in R\), the equation \(a + x = 0_R\) has a solution in \(R\). [Additive inverse]
6. If \(a \in R\) and \(b \in R\), then \(ab \in R\). [Closure for multiplication]
7. \(a(bc) = (ab)c\). [Associative for multiplication]
8. \(a(b + c) = ab + ac\) and \((a + b)c = ac + bc\). [Distributive laws]

A commutative ring is a ring \(R\) that satisfies this axiom:

\(ab = ba\) for all \(a, b \in R\). [Commutative multiplication]

A ring with identity is a ring \(R\) that contains an element \(1_R\) satisfying this axiom:

\(a1_R = 1_Ra = a\) for all \(a \in R\). [Multiplicative identity]

Definition of Integral Domain

An integral domain is a commutative ring \(R\) with identity \(1_R \neq 0_R\) that satisfies this axiom:

Whenever \(a, b \in R\) and \(ab = 0_R\), then \(a = 0_R\) or \(b = 0_R\).

Definition of Fields

A field is a commutative ring \(R\) with identity \(1_R \neq 0_R\) that satisfies this axiom:

For each \(a \neq 0_R\) in \(R\), the equation \(ax = 1_R\) has a solution in \(R\).

Theorem 3.1: Cartesian Product of Rings

Let \(R\) and \(S\) be rings. Define addition and multiplication on the Cartesian product \(R \times S\) by:

\((r, s) + (r', s') = (r + r', s + s') \quad \text{and} \quad (r, s)(r', s') = (rr', ss')\).

Then \(R \times S\) is a ring. If \(R\) and \(S\) are both commutative, then so is \(R \times S\). If both \(R\) and \(S\) have an identity, then so does \(R \times S\).

Definition of Subrings

If \(R\) is a ring and \(S\) is a subset of \(R\), then \(S\) may or may not itself be a ring under the operations in \(R\). In the ring \(\mathbb{Z}\) of integers, for example, the subset \(E\) of even integers is a ring, but the subset \(O\) of odd integers is not, as we saw in Examples 3 and 4. When a subset \(S\) of a ring \(R\) is itself a ring under the addition and multiplication in \(R\), then we say that \(S\) is a subring of \(R\).

Theorem 3.2: Subring Test

Suppose that \( R \) is a ring and that \( S \) is a subset of \( R \) such that:

1. \( S \) is closed under addition (if \( a, b \in S \), then \( a + b \in S \));
2. \( S \) is closed under multiplication (if \( a, b \in S \), then \( ab \in S \));
3. \( 0_R \in S \);
4. If \( a \in S \), then the solution of the equation \( a + x = 0_R \) is in \( S \).

Then \( S \) is a subring of \( R \).

Theorem 3.3: Existence of a Unique Solution

For any element \(a\) in a ring \(R\), the equation \(a + x = 0_R\) has a unique solution.

Theorem 3.4: Cancellation Property in Rings

If \(a + b = a + c\) in a ring \(R\), then \(b = c\).

Theorem 3.5: Properties of Zero and Negatives in Rings

For any elements \(a\) and \(b\) of a ring \(R\), the following properties hold:

1. \(a \cdot 0_R = 0_R = 0_R \cdot a\). In particular, \(0_R \cdot 0_R = 0_R\).
2. \(a \cdot (-b) = -(a \cdot b)\) and \((-a) \cdot b = -(a \cdot b)\).
3. \(-(-a) = a\).
4. \(-(a + b) = (-a) + (-b)\).
5. \(- (a - b) = -a + b\).
6. \(-(a \cdot b) = (-a) \cdot b\).
7. If \(R\) has an identity, then \((-1_R) \cdot a = -a\).

Theorem 3.6: Subring Conditions

Let \(S\) be a nonempty subset of a ring \(R\) such that:

1. \(S\) is closed under subtraction (if \(a, b \in S\), then \(a - b \in S\));
2. \(S\) is closed under multiplication (if \(a, b \in S\), then \(ab \in S\)).

Then \(S\) is a subring of \(R\).

Definition of Zero Divisors

An element \(a\) in a ring \(R\) is a zero divisor provided that:

1. \(a \neq 0_R\);
2. There exists a nonzero element \(c \in R\) such that \(ac = 0_R\) or \(ca = 0_R\).

Theorem 3.7: Cancelation in an Integral Domain

Cancelation is valid in any integral domain \(R\): If \(a \neq 0_R\) and \(ab = ac\) in \(R\), then \(b = c\).

Theorem 3.8: Every Field is an Integral Domain

Every field \(F\) is an integral domain.

Theorem 3.9: Every Finite Integral Domain is a Field

Every finite integral domain \(R\) is a field.

Definition of Isomorphism

A ring \(R\) is isomorphic to a ring \(S\) (in symbols, \(R \cong S\)) if there is a function \(f: R \to S\) such that:

1. \(f\) is injective;
2. \(f\) is surjective;
3. \(f(a + b) = f(a) + f(b)\) and \(f(ab) = f(a)f(b)\) for all \(a, b \in R\).

In this case, the function \(f\) is called an isomorphism.

Definition of Homomorphism

Homomorphism: Let \(R\) and \(S\) be rings. A function \(f: R \to S\) is said to be a homomorphism if:

\(f(a + b) = f(a) + f(b) \quad \text{and} \quad f(ab) = f(a)f(b)\)

for all \(a, b \in R\).

Theorem 3.10: Properties of Homomorphisms

Let \(f: R \to S\) be a homomorphism of rings. Then:

1. \(f(0_R) = 0_S\).
2. \(f(-a) = -f(a)\) for every \(a \in R\).
3. \(f(a - b) = f(a) - f(b)\) for all \(a, b \in R\).

If \(R\) is a ring with identity and \(f\) is surjective, then:

4. \(S\) is a ring with identity \(f(1_R)\).
5. Whenever \(u\) is a unit in \(R\), then \(f(u)\) is a unit in \(S\) and \(f(u^{-1}) = (f(u))^{-1}\).

Definition of an Image of a Homomorphism

If \(f: R \to S\) is a function, then the image of \(f\) is this subset of \(S\):

\(Im f = \{s \in S \mid s = f(r) \text{ for some } r \in R\} = \{f(r) \mid r \in R\}.\)

Corollary 3.11

If \( f: R \to S \) is a homomorphism of rings, then the image of \( f \) is a subring of \( S \).