MATH 135: Algebra for Honours Mathematics

Estimated study time: 41 minutes

Table of contents

Chapter 1: Introduction to Proof Methods

Section 1.1: A First Look at Proofs

This chapter introduces the foundational vocabulary of mathematical reasoning: statements, propositions, and axioms.

Definition 2.2.1 (Statement). A statement is a sentence that has a definite state of being either true or false.

A proposition is a mathematical claim posed as a statement that needs to be proven or demonstrated false. A theorem is a particularly significant proposition; a lemma is a subsidiary “helper” proposition; a corollary follows almost immediately from a theorem. An axiom is a statement assumed true without proof.

Definition 2.3.1 (Even and Odd). An integer is even if it can be written in the form \(2k\) where \(k\) is an integer. Otherwise, it can be written in the form \(2k+1\) and is called odd.

Section 1.2: Truth Tables and Logical Operators

We build compound statements from simpler components using logical operators.

Definition 3.2.1 (Compound Statement). A compound statement is a statement composed of several individual statements called component statements.

Definition 3.3.1 (NOT). The negation of \(A\), written \(\neg A\), is true when \(A\) is false, and false when \(A\) is true.

Definition 3.3.2 (AND). The conjunction \(A \wedge B\) is true only when both \(A\) and \(B\) are true.

Definition 3.3.3 (OR). The disjunction \(A \vee B\) is false only when both \(A\) and \(B\) are false. In mathematics, OR is always inclusive.

Definition 3.5.1 (Logical Equivalence). Two compound statements \(S_1\) and \(S_2\) are logically equivalent, written \(S_1 \equiv S_2\), if they have the same truth values for all possible states of their component statements.

Proposition (De Morgan’s Laws, DML). For any two statements \(A\) and \(B\):

\(\neg(A \vee B) \equiv (\neg A) \wedge (\neg B)\)
\(\neg(A \wedge B) \equiv (\neg A) \vee (\neg B)\)

The Distributivity Laws also hold: \(A \wedge (B \vee C) \equiv (A \wedge B) \vee (A \wedge C)\) and \(A \vee (B \wedge C) \equiv (A \vee B) \wedge (A \vee C)\).

Section 1.3: Implications and the Direct Proof

Definition 4.2.1 (Implication). An implication \(A \Rightarrow B\) is defined by the truth table where \(A \Rightarrow B\) is false only when \(A\) is true and \(B\) is false. The component \(A\) is the hypothesis and \(B\) is the conclusion.

The negation of an implication satisfies \(\neg(A \Rightarrow B) \equiv A \wedge (\neg B)\), and we also have \((\neg A) \vee B \equiv A \Rightarrow B\).

A direct proof of \(A \Rightarrow B\) assumes \(A\) is true and deduces that \(B\) must be true.

Section 1.4: Analysis of a Proof – Divisibility

Definition 5.2.1 (Divisibility). An integer \(m\) divides an integer \(n\), written \(m \mid n\), when there exists an integer \(k\) so that \(n = km\). We call \(m\) a divisor or factor of \(n\), and \(n\) a multiple of \(m\).

Proposition (Transitivity of Divisibility, TD). Let \(a, b, c\) be integers. If \(a \mid b\) and \(b \mid c\), then \(a \mid c\).

Section 1.5: Discovering Proofs

Proposition (Divisibility of Integer Combinations, DIC). Let \(a, b, c\) be integers. If \(a \mid b\) and \(a \mid c\), then for any integers \(x\) and \(y\), \(a \mid (bx + cy)\).

Proposition (Bounds By Divisibility, BBD). Let \(a\) and \(b\) be integers. If \(a \mid b\) and \(b \neq 0\), then \(|a| \leq |b|\).

Chapter 2: Foundations – Sets and Quantifiers

Section 2.1: Introduction to Sets

Definition 7.2.1 (Set, Element). A set is a collection of objects. The objects in a set are called its elements (or members). We write \(x \in S\) if \(x\) is an element of \(S\).

Definition 7.2.2 (Empty Set). The set \(\{\}\) contains no elements and is called the empty set, denoted \(\emptyset\).

\[S = \{x \in U : P(x)\}.\]

The part after the colon is the defining property of the set.

Definition 7.3.1 (Union). \(S \cup T = \{x : (x \in S) \vee (x \in T)\}\).

Definition 7.3.2 (Intersection). \(S \cap T = \{x : (x \in S) \wedge (x \in T)\}\).

Definition 7.3.3 (Set-Difference). \(S \setminus T = \{x : (x \in S) \wedge (x \notin T)\}\).

Definition 7.3.4 (Set Complement). Relative to a universal set \(U\), the complement of \(S \subseteq U\) is \(\overline{S} = U \setminus S\).

Definition 7.4.1 (Cartesian Product). \(S \times T = \{(x,y) : x \in S,\, y \in T\}\). Each element is an ordered pair.

Section 2.2: Subsets, Set Equality, Converse, and If and Only If

Definition 8.2.1 (Disjoint Sets). Sets \(S\) and \(T\) are disjoint when \(S \cap T = \emptyset\).

Definition 8.2.2 (Subset). \(S\) is a subset of \(T\), written \(S \subseteq T\), when every element of \(S\) belongs to \(T\).

Definition 8.2.3 (Proper Subset). \(S \subsetneq T\) means every element of \(S\) belongs to \(T\), and there is at least one element in \(T\) not in \(S\).

Definition 8.3.1 (Set Equality). \(S = T\) when \(S \subseteq T\) and \(T \subseteq S\).

Definition 8.3.2 (Converse). The converse of \(A \Rightarrow B\) is \(B \Rightarrow A\). Note: \(A \Rightarrow B \not\equiv B \Rightarrow A\).

Definition 8.3.3 (If and Only If). \(A \Leftrightarrow B\) is true exactly when \(A\) and \(B\) have the same truth value. It is equivalent to \((A \Rightarrow B) \wedge (B \Rightarrow A)\).

Definition 8.3.4 (Perfect Square). An integer is a perfect square if and only if it equals \(k^2\) for some integer \(k\).

Section 2.3: Quantifiers

\[\neg[\forall x \in S,\, P(x)] \equiv \exists x \in S,\, \neg P(x)\]\[\neg[\exists x \in S,\, P(x)] \equiv \forall x \in S,\, \neg P(x)\]

Definition 9.3.1 (Prime). An integer \(p > 1\) is prime if and only if its only positive divisors are \(1\) and \(p\) itself. Otherwise, \(p\) is composite.

Key proof methods: the Select Method proves \(\forall x \in S, P(x)\) by choosing a representative \(x\); the Construct Method proves \(\exists x \in S, P(x)\) by exhibiting a specific element.

Section 2.4: Nested Quantifiers

Definition 10.4.1 (Function). A function \(f: S \to T\) assigns to each \(s \in S\) a unique element \(f(s) \in T\). The set \(S\) is the domain and \(T\) the codomain.

Definition 10.4.2 (Surjective). \(f: S \to T\) is onto (surjective) if for every \(y \in T\) there exists \(x \in S\) so that \(f(x) = y\).

Chapter 3: More Proof Techniques

Section 3.1: Contrapositives

Definition 11.2.1 (Contrapositive). The contrapositive of \(A \Rightarrow B\) is \(\neg B \Rightarrow \neg A\). We have \((A \Rightarrow B) \equiv (\neg B \Rightarrow \neg A)\).

To prove \(A \Rightarrow B\) by contrapositive, assume \(\neg B\) and deduce \(\neg A\).

Section 3.2: Proofs by Contradiction

Definition 12.2.1 (Contradiction). A contradiction is a statement of the form \(A \wedge (\neg A)\), which is always false.

To prove a statement \(C\) by contradiction, assume \(\neg C\) and derive a contradiction.

Proposition (Prime Factorization, PF). Every integer \(n > 1\) can be expressed as a product of primes.

Proposition (Euclid’s Theorem, ET). The number of primes is infinite.

Section 3.3: Uniqueness, Injections, and the Division Algorithm

Definition 13.5.1 (Injective). A function \(f: S \to T\) is one-to-one (injective) if for every \(x_1, x_2 \in S\), \(f(x_1) = f(x_2)\) implies \(x_1 = x_2\).

\[a = qb + r \quad\text{where } 0 \leq r < b.\]

Section 3.4: Simple Induction

Definition 14.2.1 (Summation Notation). \(\displaystyle\sum_{i=m}^{n} x_i = x_m + x_{m+1} + \cdots + x_n\).

Definition 14.2.2 (Product Notation). \(\displaystyle\prod_{i=m}^{n} x_i = x_m \cdot x_{m+1} \cdots x_n\).

Definition 14.2.3 (Recurrence Relation). A recurrence relation defines a sequence by one or more initial terms and expressions involving prior terms.

Axiom (Principle of Mathematical Induction, POMI). Let \(P(n)\) depend on \(n \in \mathbb{N}\). If (1) \(P(1)\) is true, and (2) \(P(k) \Rightarrow P(k+1)\) for all \(k \in \mathbb{N}\), then \(P(n)\) is true for all \(n \in \mathbb{N}\).

Proposition. For every \(n \in \mathbb{N}\), \(\displaystyle\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}\).

Proposition. The set \(S_n = \{1,2,\ldots,n\}\) has \(2^n\) subsets.

Proposition. For every integer \(n \geq 3\), \(n^2 > 2n + 1\).

Proposition. For every integer \(n \geq 5\), \(2^n > n^2\).

Proposition. A \(2^n \times 2^n\) grid with one square removed can be covered by triominoes.

Section 3.5: Strong Induction

Axiom (Principle of Strong Induction, POSI). Let \(P(n)\) depend on \(n \in \mathbb{N}\). If (1) \(P(1), P(2), \ldots, P(b)\) are true, and (2) \(P(1) \wedge P(2) \wedge \cdots \wedge P(k) \Rightarrow P(k+1)\) for all \(k \in \mathbb{N}\), then \(P(n)\) is true for all \(n \in \mathbb{N}\).

Use strong induction when the general case depends on multiple previous cases.

Proposition. Every integer \(n \geq 9\) can be written as \(3x + 4y\) for non-negative integers \(x\) and \(y\).

Chapter 4: Securing Internet Commerce

Section 4.1: The Greatest Common Divisor

Definition 17.2.1 (Greatest Common Divisor). Let \(a,b\) be integers, not both zero. An integer \(d > 0\) is the greatest common divisor \(\gcd(a,b)\) if and only if:

\(d \mid a\) and \(d \mid b\), and
if \(c \mid a\) and \(c \mid b\), then \(c \leq d\).

We define \(\gcd(0,0) = 0\).

Proposition (GCD With Remainders, GCD WR). If \(a, b, q, r\) are integers such that \(a = qb + r\), then \(\gcd(a,b) = \gcd(b,r)\).

This proposition underlies the Euclidean Algorithm: repeatedly apply the Division Algorithm until the remainder is zero; the last nonzero remainder is the GCD.

Proposition (GCD Characterization Theorem, GCD CT). If \(d\) is a positive common divisor of integers \(a\) and \(b\), and there exist integers \(x\) and \(y\) so that \(ax + by = d\), then \(d = \gcd(a,b)\).

Section 4.2: The Extended Euclidean Algorithm

Definition 18.2.1 (Floor). The floor of \(x\), written \(\lfloor x \rfloor\), is the largest integer less than or equal to \(x\).

The Extended Euclidean Algorithm (EEA) computes \(d = \gcd(a,b)\) together with integers \(x,y\) satisfying \(ax + by = d\).

Proposition (Bezout’s Lemma, BL). If \(a\) and \(b\) are integers, then \(d = \gcd(a,b)\) can be computed and there exist integers \(x\) and \(y\) so that \(ax + by = d\).

Section 4.3: Properties of GCDs

Definition 19.2.1 (Coprime). Two integers \(a\) and \(b\) are coprime if \(\gcd(a,b) = 1\).

Proposition (Coprimeness and Divisibility, CAD). If \(c \mid ab\) and \(\gcd(a,c) = 1\), then \(c \mid b\).

Corollary (Euclid’s Lemma, EL). If \(p\) is a prime and \(p \mid ab\), then \(p \mid a\) or \(p \mid b\).

Proposition (GCD of One, GCD OO). \(\gcd(a,b) = 1\) if and only if there exist integers \(x,y\) with \(ax + by = 1\).

Proposition (Division by the GCD, DB GCD). If \(\gcd(a,b) = d \neq 0\), then \(\gcd\!\left(\dfrac{a}{d}, \dfrac{b}{d}\right) = 1\).

Section 4.4: GCD from Prime Factorization

Theorem (Unique Factorization Theorem, UFT). If \(n > 1\) is an integer, then \(n\) can be written as a product of prime factors and, apart from the order of factors, this factorization is unique.

Also known as the Fundamental Theorem of Arithmetic.

Proposition (Finding a Prime Factor, FPF). An integer \(n > 1\) is either prime or contains a prime factor \(\leq \sqrt{n}\).

Proposition (Divisors From Prime Factorization, DFPF). If \(n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}\) is the unique prime factorization, then \(d\) is a positive divisor of \(n\) if and only if \(d = p_1^{d_1} p_2^{d_2} \cdots p_k^{d_k}\) where \(0 \leq d_i \leq \alpha_i\).

\[\gcd(a,b) = p_1^{d_1} \cdots p_k^{d_k} \quad\text{where } d_i = \min\{\alpha_i, \beta_i\}.\]

Section 4.5: Linear Diophantine Equations – One Solution

Definition 21.2.1 (Diophantine Equation). Equations with integer coefficients for which integer solutions are sought are called Diophantine equations.

Theorem (LDET 1). Let \(d = \gcd(a,b)\). The linear Diophantine equation \(ax + by = c\) has a solution if and only if \(d \mid c\).

Section 4.6: Linear Diophantine Equations – All Solutions

\[x = x_0 + \frac{b}{d}\,n, \quad y = y_0 - \frac{a}{d}\,n, \quad \text{for all } n \in \mathbb{Z}.\]

Section 4.7: Congruence

Definition 23.2.1 (Congruent). Let \(m\) be a fixed positive integer. For \(a,b \in \mathbb{Z}\), we say \(a\) is congruent to \(b\) modulo \(m\), written \(a \equiv b \pmod{m}\), if and only if \(m \mid (a - b)\).

Equivalent formulations: \(a \equiv b \pmod{m}\) iff \(\exists k \in \mathbb{Z}\) such that \(a - b = km\) iff \(a\) and \(b\) have the same remainder when divided by \(m\).

Proposition (Congruence is an Equivalence Relation, CER). For \(a,b,c \in \mathbb{Z}\):

\(a \equiv a \pmod{m}\) (reflexive).
\(a \equiv b \pmod{m} \Rightarrow b \equiv a \pmod{m}\) (symmetric).
\(a \equiv b\) and \(b \equiv c \pmod{m} \Rightarrow a \equiv c \pmod{m}\) (transitive).

Proposition (Properties of Congruence, PC). If \(a \equiv a' \pmod{m}\) and \(b \equiv b' \pmod{m}\), then:

\(a + b \equiv a' + b' \pmod{m}\)
\(a - b \equiv a' - b' \pmod{m}\)
\(ab \equiv a'b' \pmod{m}\)

As a corollary, if \(a \equiv b \pmod{m}\), then \(a^n \equiv b^n \pmod{m}\) for all \(n \in \mathbb{N}\).

Proposition (Congruence Division, CD). If \(ac \equiv bc \pmod{m}\) and \(\gcd(c,m) = 1\), then \(a \equiv b \pmod{m}\).

Section 4.8: Congruence and Remainders

Proposition (Congruent Iff Same Remainder, CISR). \(a \equiv b \pmod{m}\) if and only if \(a\) and \(b\) have the same remainder when divided by \(m\).

Section 4.9: Linear Congruences

Definition 25.2.1 (Linear Congruence). A relation \(ax \equiv c \pmod{m}\) is a linear congruence in \(x\). A solution is an integer \(x_0\) with \(ax_0 \equiv c \pmod{m}\).

\[x \equiv x_0 \pmod{\frac{m}{d}}\]

which gives \(d\) distinct solutions modulo \(m\).

Section 4.10: Modular Arithmetic

\[[a] = \{x \in \mathbb{Z} \mid x \equiv a \pmod{m}\}.\]

Definition 26.2.2 (\(\mathbb{Z}_m\)). \(\mathbb{Z}_m = \{[0],[1],\ldots,[m-1]\}\) with operations \([a]+[b]=[a+b]\) and \([a]\cdot[b]=[a \cdot b]\).

Definition 26.2.3 (Identity). Given a set \(S\) and operation \(\star\), an identity is an element \(e \in S\) such that \(a \star e = a\) for all \(a \in S\).

Definition 26.2.4 (Inverse). The element \(b \in S\) is an inverse of \(a \in S\) if \(a \star b = b \star a = e\).

In \(\mathbb{Z}_m\), the additive identity is \([0]\), the multiplicative identity is \([1]\), and every element has an additive inverse. Multiplicative inverses may not always exist.

Theorem (LCT, Version 2). Let \(d = \gcd(a,m)\). The equation \([a][x] = [c]\) in \(\mathbb{Z}_m\) has a solution iff \(d \mid c\). If \([x_0]\) is one solution, the complete solution consists of \(d\) congruence classes in \(\mathbb{Z}_m\).

Section 4.11: Fermat’s Little Theorem

Theorem (Fermat’s Little Theorem, FlT). If \(p\) is prime and \(p \nmid a\), then \(a^{p-1} \equiv 1 \pmod{p}\).

Corollary. For any integer \(a\) and any prime \(p\), \(a^p \equiv a \pmod{p}\).

Corollary (Existence of Inverses in \(\mathbb{Z}_p\), INV \(\mathbb{Z}_p\)). Let \(p\) be prime. If \([a]\) is any nonzero element in \(\mathbb{Z}_p\), then \([a]^{-1} = [a^{p-2}]\).

Section 4.12: Chinese Remainder Theorem

\[n \equiv a_1 \pmod{m_1}, \quad n \equiv a_2 \pmod{m_2}\]

have a unique solution modulo \(m_1 m_2\).

Theorem (Generalized CRT). If \(m_1, \ldots, m_k\) are pairwise coprime, then the simultaneous system \(n \equiv a_i \pmod{m_i}\) for \(i = 1,\ldots,k\) has a unique solution modulo \(m_1 m_2 \cdots m_k\).

\[x \equiv a \pmod{m_1 m_2} \iff \begin{cases} x \equiv a \pmod{m_1} \\ x \equiv a \pmod{m_2} \end{cases}\]

Section 4.13: The RSA Scheme

RSA setup: choose distinct primes \(p,q\), let \(n = pq\). Choose \(e\) with \(\gcd(e,(p-1)(q-1))=1\). Solve \(ed \equiv 1 \pmod{(p-1)(q-1)}\). Public key: \((e,n)\). Private key: \((d,n)\). Encrypt: \(M^e \equiv C \pmod{n}\). Decrypt: \(C^d \equiv R \pmod{n}\).

Theorem (RSA). If \(p,q\) are distinct primes, \(n = pq\), \(ed \equiv 1 \pmod{(p-1)(q-1)}\), \(0 \leq M < n\), \(M^e \equiv C \pmod{n}\), and \(C^d \equiv R \pmod{n}\) with \(0 \leq R < n\), then \(R = M\).

The proof uses Fermat’s Little Theorem modulo \(p\) and modulo \(q\) separately, then combines via CRT.

Chapter 5: Complex Numbers and Euler’s Formula

Section 5.1: Complex Numbers

Definition 30.3.1 (Complex Number). A complex number in standard form is \(z = x + yi\) where \(x, y \in \mathbb{R}\). The set of all complex numbers is \(\mathbb{C} = \{x + yi : x, y \in \mathbb{R}\}\).

Definition 30.3.2 (Real and Imaginary Parts). For \(z = x + yi\), the real part is \(\operatorname{Re}(z) = x\) and the imaginary part is \(\operatorname{Im}(z) = y\).

Definition 30.3.3 (Equality). \(x + yi = u + vi\) iff \(x = u\) and \(y = v\).

Definition 30.3.4 (Addition). \((a+bi)+(c+di) = (a+c)+(b+d)i\).

Definition 30.3.5 (Multiplication). \((a+bi)(c+di) = (ac-bd)+(ad+bc)i\). In particular, \(i^2 = -1\).

Definition 30.3.7 (Division). \(\displaystyle\frac{a+bi}{c+di} = \frac{ac+bd}{c^2+d^2} + \frac{bc-ad}{c^2+d^2}\,i\).

Proposition (Properties of \(\mathbb{C}\)). Complex numbers satisfy: associativity and commutativity of \(+\) and \(\cdot\); additive identity \(0\); multiplicative identity \(1\); additive inverses; multiplicative inverses for \(z \neq 0\) given by \(z^{-1} = \frac{x - yi}{x^2 + y^2}\); and distributivity.

Section 5.2: Properties of Complex Numbers

Definition 31.2.1 (Conjugate). The conjugate of \(z = x + yi\) is \(\bar{z} = x - yi\).

Proposition (Properties of Conjugates, PCJ). For \(z, w \in \mathbb{C}\):

\(\overline{z+w} = \bar{z}+\bar{w}\)
\(\overline{zw} = \bar{z}\,\bar{w}\)
\(\overline{\bar{z}} = z\)
\(z + \bar{z} = 2\operatorname{Re}(z)\)
\(z - \bar{z} = 2\operatorname{Im}(z)\,i\)

Definition 31.3.1 (Modulus). \(|z| = |x+yi| = \sqrt{x^2+y^2}\).

Proposition (Properties of Modulus, PM).

\(|z| = 0\) iff \(z = 0\)
\(|\bar{z}| = |z|\)
\(z\bar{z} = |z|^2\)
\(|zw| = |z||w|\)
\(|z+w| \leq |z|+|w|\) (triangle inequality)

Section 5.3: Polar Form

Definition 32.4.1 (Polar Form). The polar form of \(z\) is \(z = r(\cos\theta + i\sin\theta)\) where \(r = |z|\) and \(\theta\) is an argument of \(z\).

\[z_1 z_2 = r_1 r_2(\cos(\theta_1+\theta_2) + i\sin(\theta_1+\theta_2)).\]

Section 5.4: De Moivre’s Theorem

\[(\cos\theta + i\sin\theta)^n = \cos(n\theta) + i\sin(n\theta).\]

Corollary. If \(z = r(\cos\theta + i\sin\theta)\) and \(n\) is an integer, then \(z^n = r^n(\cos(n\theta) + i\sin(n\theta))\).

Definition 33.3.1 (Complex Exponential). \(e^{i\theta} = \cos\theta + i\sin\theta\).

Setting \(\theta = \pi\) yields Euler’s identity: \(e^{i\pi} + 1 = 0\).

Proposition (Properties of Complex Exponentials, PCE).

\(e^{i\theta} \cdot e^{i\varphi} = e^{i(\theta+\varphi)}\)
\((e^{i\theta})^n = e^{in\theta}\) for all \(n \in \mathbb{Z}\).

Section 5.5: Roots of Complex Numbers

Definition 34.2.1 (Complex \(n\)-th Roots). The complex numbers solving \(z^n = a\) are the complex \(n\)-th roots of \(a\).

\[\sqrt[n]{r}\left(\cos\frac{\theta+2k\pi}{n} + i\sin\frac{\theta+2k\pi}{n}\right) \quad\text{for } k = 0,1,\ldots,n-1.\]

Every nonzero complex number has exactly \(n\) distinct \(n\)-th roots, uniformly distributed on a circle of radius \(\sqrt[n]{r}\).

Proposition (Quadratic Formula over \(\mathbb{C}\)). For \(a,b,c \in \mathbb{C}\), the solutions to \(ax^2 + bx + c = 0\) are \(\frac{-b \pm w}{2a}\) where \(w^2 = b^2 - 4ac\).

Chapter 6: Factoring Polynomials

Section 6.1: An Introduction to Polynomials

Definition 35.2.1 (Polynomial). A polynomial in \(x\) over the field \(F\) is \(a_n x^n + a_{n-1}x^{n-1} + \cdots + a_1 x + a_0\), where \(x\) is an indeterminate and the \(a_i \in F\) are coefficients. The set of all such polynomials is \(F[x]\).

Definition 35.2.2 (Degree). If \(a_n \neq 0\), the polynomial has degree \(n\). The zero polynomial has undefined degree.

Definition 35.2.3 (Polynomial Equality). \(f(x) = g(x)\) iff \(a_k = b_k\) for all \(k\).

\[f(x) = q(x)g(x) + r(x)\]

where \(r(x)\) is zero or \(\deg r(x) < \deg g(x)\).

Definition 35.3.4 (Divides). \(g(x) \mid f(x)\) iff there exists \(q(x)\) with \(f(x) = q(x)g(x)\).

Section 6.2: Factoring Polynomials

Definition 36.2.1 (Root/Zero). An element \(c \in F\) is a root of \(f(x)\) if \(f(c) = 0\).

Theorem (Fundamental Theorem of Algebra, FTA). Every complex polynomial \(f(z)\) with \(\deg f \geq 1\) has at least one root in \(\mathbb{C}\).

Proposition (Remainder Theorem, RT). The remainder when \(f(x)\) is divided by \((x-c)\) is \(f(c)\).

Corollary (Factor Theorem, FT). \((x-c)\) is a factor of \(f(x)\) if and only if \(f(c) = 0\).

Lemma. If \(h(x) = f(x)g(x)\) in \(F[x]\), then \(\deg h = \deg f + \deg g\).

Proposition. A polynomial of degree \(n \geq 1\) over a field \(F\) has at most \(n\) roots in \(F\).

Definition 36.2.2 (Irreducible). A polynomial of positive degree in \(F[x]\) is irreducible over \(F\) if it cannot be written as the product of two polynomials of positive degree in \(F[x]\). Otherwise it is reducible.

\[f(z) = c(z - c_1)(z - c_2)\cdots(z - c_n).\]

Definition 36.3.1 (Multiplicity). The multiplicity of a root \(c\) is the largest \(k\) such that \((x-c)^k \mid f(x)\).

Theorem (Rational Roots Theorem, RRT). Let \(f(x) = a_n x^n + \cdots + a_0\) have integer coefficients. If \(\frac{p}{q}\) is a rational root with \(\gcd(p,q) = 1\), then \(p \mid a_0\) and \(q \mid a_n\).

Theorem (Conjugate Roots Theorem, CJRT). If \(f(x)\) has real coefficients and \(c \in \mathbb{C}\) is a root, then \(\bar{c}\) is also a root.

Corollary (Real Quadratic Factors, RQF). If \(f(x)\) has real coefficients and \(c\) is a nonreal root, then \(f(x) = g(x)q(x)\) where \(g(x) = x^2 - 2\operatorname{Re}(c)x + |c|^2\) is a real quadratic.

Theorem (Real Factors of Real Polynomials, RFRP). Every real polynomial of degree \(\geq 1\) can be written as a product of real linear and real quadratic factors.

Chapter 7: Bijections, Counting, and Cardinality

Section 7.1: Compositions and Bijections

Definition 37.3.1 (Composition). If \(f: T \to V\) and \(g: S \to T\), then \(f \circ g: S \to V\) is defined by \((f \circ g)(x) = f(g(x))\).

Proposition. The composition of surjections is surjective.

Proposition. The composition of injections is injective.

Definition 37.4.1 (Bijective). A function is bijective if it is both surjective and injective.

Proposition. The composition of bijections is a bijection.

Definition 37.4.2 (Inverse). If \(f: S \to T\) and \(g: T \to S\) satisfy \(g(f(s)) = s\) for all \(s\) and \(f(g(t)) = t\) for all \(t\), then \(g = f^{-1}\).

Theorem (Inverse Theorem). A function has an inverse if and only if it is bijective.

Section 7.2: Counting

Definition 38.3.1 (Same Cardinality). If there exists a bijection between sets \(S\) and \(T\), we write \(|S| = |T|\).

Definition 38.3.2 (Finite and Infinite). If there exists a bijection between \(S\) and \(\{1,2,\ldots,n\}\), then \(|S| = n\) and \(S\) is finite. Otherwise, \(S\) is infinite.

Proposition (Cardinality of Disjoint Sets, CDS). If \(S\) and \(T\) are disjoint finite sets, then \(|S \cup T| = |S| + |T|\).

Proposition (Cardinality of Intersecting Sets, CIS). For any finite sets \(S\) and \(T\), \(|S \cup T| = |S| + |T| - |S \cap T|\).

Proposition (Cardinality of Subsets of Finite Sets, CSFS). If \(S \subsetneq T\) are finite sets, then \(|S| < |T|\).

Section 7.3: Cardinality of Infinite Sets

Proposition. \(|\mathbb{N}| = |2\mathbb{N}|\), where \(2\mathbb{N}\) is the set of even natural numbers. The bijection is \(f(n) = 2n\).

Proposition. \(|\mathbb{N} \times \mathbb{N}| = |\mathbb{N}|\).

The proof uses the bijection \(f(a,b) = 2^{a-1}(2b-1)\) and the Even-Odd Factorization of Natural Numbers.

Proposition. \(|\mathbb{N}| \neq |(0,1)|\). That is, the natural numbers and the open interval of reals do not have the same cardinality.

The proof is Cantor’s diagonal argument: any proposed listing of elements of \((0,1)\) must miss some element constructed to differ from the \(i\)-th listed number in its \(i\)-th decimal digit.