Professor: Benjamin Steinberg
Syllabus
HW must be from 8th edition of textbook.
Set-builder notation.
Empty set is contained in all sets.
A = B, if 
{a,b,c} = {a,a,b,b,c,c,c}
Theorems and Definitions of the text: (variables are generally assumed to be integers unless stated otherwise)
Chapter 1 Fundamentals
Section 1.1 Sets
Section 1.2 Mappings
Section 1.3 Properties of Composite Mappings (Optional)
Section 1.4 Binary Operations
Section 1.5 Permutations and Inverses
Section 1.6 Matrices
Section 1.7 Relations
Chapter 2 The Integers
Section 2.1 Postulates for the Integers (Optional)
Section 2.2 Mathematical Induction
Section 2.3 Divisibility
Section 2.4 Prime Factors and GCD
Definition 2.11 Greatest Common Divisor: gcd(a,b) = d
1. d > 0
2. d|a & d|b
3. c|a & c|b => c|d
Theorem 2.12 Greatest Common Divisor
A method to find gcd: Euclidean Algorithm
Definition 2.13 Relatively Prime Integers: gcd(a,b) = 1
Theorem 2.14 If gcd(a,b) = 1 & a|bc => a|c
Definition 2.15 Prime Integer (p)
1. p > 1
2. the only divisors of p: ± 1 and ±p
Theorem 2.16 Euclid's Lemma
prime p |ab,
=> either p|a or p|b
Corollary 2.17 prime p|
Theorem 2.18 Unique Factorization Theorem = Fundamental Theorem of Arithmetic
n > 0,
=> n=1 or 
..., where 
are unique primes
Terms: 
= multiplicity of 
=> standard form for 
...
Definition 2.19 Least Common Multiple: lcm(a,b) = m where a, b != 0
1. m > 0
2. a|m & b|m
3. a|c & b|c => m|c
Theorem 2.20 Euclid's Theorem: The number of primes is infinite
Section 2.5 Congruence of Integers
Definition 2.21 Congruence modulo n
n > 1, x ≡ y (mod n)
Theorem 2.22 Congruence modulo n is an equivalence relation on Z.
Congruence classes = residue classes
Theorem 2.23 Addition and Multiplication Properties
a ≡ b (mod n),
=> a+x ≡ b+x (mod n) & ax ≡ bx (mod n)
Theorem 2.24 Substitution Properties
a ≡ b (mod n) & c ≡ d (mod n),
=> a+c ≡ b+d (mod n) & ac ≡ bd (mod n)
Theorem 2.25 Cancellation Law
gcd(a,n) = 1 & ax ≡ ay (mod n),
=> x ≡ y (mod n)
Theorem 2.26 Linear Congruences
gcd(a,n) = 1,
∃x =>ax = b (mod n)
=> 
(mod n)
Theorem 2.27 System of Congruences
gcd(m,n) = 1,
∃x => x ≡ a (mod m), x ≡ b (mod n),
=> (mod mn)
Theorem 2.28 Chinese Remainder Theorem
expands theorem 2.27
Section 2.6 Congruence Classes: 
= {[0],[1],...,[n-1]}
Theorem 2.29 Addition in : [a] + [b] = [a+b]
1. Associative & commutative in
2. [0] = additive identity
3. [-a] is additive inverse of [a], where [-a],[a] 
Theorem 2.30 Multiplication in : [a][b] = [ab]
1. Associative & Commutative in
2. [1] = multiplicative identity
3. Theorem 2.31 [a] has multiplicative inverse in IFF gcd(a,n) = 1
Corollary 2.32 [a] in has multiplicative inverse IFF n is a prime
Section 2.7 Introduction to Coding Theory (Optional) - skipped
Section 2.8 Introduction to Cryptography (Optional)
Theorem 2.33 RSA Public Key Cryptosystem
Chapter 3 Groups
Section 3.1 Definition of Group
Definition 3.1 Group, G
1. G is Closed under *
2. * is associative
3. G has identity element e
4. all elements of G has inverses in G
Definition 3.2 Abelian Group (=Commutative group)
Definition 3.3 Finite, Infinite groups, Order of Group (|G|)
Section 3.2 Properties of Group Elements
Theorem 3.4 Properties of Group Elements
1. e in G is unique
2. All inverses of elements in G are in G and unique
3. 
4. 
Reverse order law
5. ax = ay or xa = ya imples x = y: Cancellation law
Theorem 3.5 Equivalent Conditions for a Group
G is nonempty set, closed under associative multiplication.
G is a group IFF ax = b and ya = b s.t. x and y in G, for all a and b in G.
Definition 3.6 Product Notation
for 
Theorem 3.7 Generalized Associative Law
Definition 3.8 Integral Exponents
Compare Multiplicative and Additive Notations
Theorem 3.9 Laws of Exponents
1. 
2. 
3. 
4. 
Can be translated to Laws of Multiples for additive groups.
Section 3.3 Subgroups
Definition 3.10
Theorem 3.11 Subgroup, H 
G is a subgroup IFF:
1.) identity e is in H (H is nonempty)
2.) H is closed under *
3.) 
, closed under inverse
Notation: 
is a subgroup of G
Theorem 3.12 Equivalent Set of Conditions for a Subgroup (Summarized Theorem 3.11)
H is subgroup of IFF:
1. H is nonempty (I think this can be ignored)
2. a, b in H implies 
Definition 3.13 The center of a Group
Z(G) = {
}
Meaning all g which commute with every element of G
Theorem 3.14 The center of a group G is an abelian subgroup of G
Definition 3.15 The Centralizer of a Group Element
Theorem 3.16 The centralizer of a in G is a subgroup of G
Definition 3.17 Cyclic Subgroup
For any a in group G, <a> = subgroup generated by a = 
= H = cyclic subgroup of G. The element a is called a generator of H.
Section 3.4 Cyclic Groups
Definition 3.18 Generator (repeated from last section)
Theorem 3.19 Infinite Cyclic Group
If 
whenever 
and <a> is an infinite cyclic group
Corollary 3.20 If G is a finite group, then 
for some positive integer n.
Theorem 3.21 Finite Cyclic Group
If m is the least positive integer s.t. a^m = e, then
1. <a> has order m
2. 
IFF 
(mod m)
Definition 3.22 Order of an Element: o(a) = |a| = |<a>|
Order of Subgroup of G generated by a in G
Corollary 3.23 Finite Order of an Element
If |a| is finite, then m = |a| is the least positive integer s.t. 
Theorem 3.24 Subgroup of a Cyclic Group
If H is a subgroup of cyclic group G with generator a, then
, where k is the least positive integer s.t. 
Corollary 3.25 Any subgroup of a cyclic group is cyclic
Theorem 3.26 Generators of Subgroups
Subgroup (generated by 
) of cyclic group of order n generated by a = subgroup generated by 
, where d = gcd(m,n)
Corollary 3.27 Distinct Subgroups 
of a Finite Cyclic Group, G
where d is a positive divisor of n.
Theorem 3.28 Generators of a Finite Cyclic Group <a>:
is a generator of <a> of order n IFF gcd(m,n) = 1
Section 3.5 Isomorphisms
Definition 3.29 Isomorphism, Automorphism
is an isomorphism from G to G' if:
1. 
is a bijection from G to G'
2. 
Notation 
Automorphism: An isomorphism from G to G
Theorem 3.30 Images of Identities and Inverses
1. 
and
2. 
Section 3.6 Homomorphisms
Definition 3.31 Groups G,
& G'',
, Homomorphism: 
s.t. 
or
1. Endomorphism: G = G'
2. Epimorphism: is onto, G' is homomorphic image of G.
3. Monomorphism: is one-to-one
Theorem 3.32 Images of Identities and Inverses (
)
1.
2.
Definition 3.33 Kernel: ker 
is a homomorphism from group G to G'
Chapter 4 More on Groups
Section 4.1 Finite Permutation Groups
Definition 4.1 Cycle
This statement is not unique.
Disjoint subsets which define cycles, are called orbits
Theorem 4.2 Partition of A
Definition 4.3 Orbit
Let 
, the orbit of 
The orbits form a partition of {1,...,n}
Note: All permutations can be written as a product of transpositions:
Lemma 4.4 t(P) = (-1)P
t is any transposition (r,s) on {1,2,...,n} and 
Theorem 4.5 Products of Transpositions (Either all even or all odd transpositions)
Definition 4.6 Even Permutation vs. Odd Permutation (based on number of transpositions)
Even Permutation if r in r-cycle is odd
Odd Permutation if r in r-cycle is even
Definition 4.7 Alternating Group 
is the subgroup of 
that consists all even permutations in
Definition 4.8 Conjugate Elements
1. The Conjugate of a by b is the element 
2. c is a conjugate of a IFF 
for some b in G
Section 4.2 Cayley's Theorem
Definition 4.9 Cayley's Theorem
Every group is isomorphic to a group of permutations.
Section 4.4 Cosets of a Subgroup
Definition 4.10 Product of Subsets
Let 
Theorem 4.11 Properties of the Product of Subsets
1. Associative
2. not commutative
3. B = C 
AB = AC & BA = CA
4. AB = AC 
B = C
5. gA = gB A = B
Definition 4.12 Cosets, H < G, 
Left coset of H in G: aH = {
| x = ah for some 
}
Right coset of H in G: Ha
Left & right cosets are never disjoint, but they may be different sets.
Lemma 4.13 Left Coset Partition
The distinct left cosets of H form a partition of G.
Definition 4.14 Index: [G:H]
The total number of distinct left cosets of H in G.
Theorem 4.15 Lagrange's Theorem
If G is a finite group, 
Corollary 4.16 |a| divides |G|
Section 4.5 Normal Subgroups
Definition 4.17 Normal (Invariant) Subgroup
H is a normal subgroup of G if xH = Hx for all x in G (left coset = right coset)
Note that it does not mean xh = hx
Theorem 4.18 A special coset H: hH = Hh = H
Corollary 4.19 The square of a subgroup 
Theorem 4.20 Normal Subgroups and Conjugates
H is a normal subgroup of G IFF 
Definition 4.21 Set Generated by A
Theorem 4.22 Subgroup Generated by A: <A> is a subgroup of G generated by A
Section 4.6 Quotient Groups
Theorem 4.23 Group of Cosets
If H is normal subgroup of G, then cosets of H form a group with respect to the product of subsets
Definition 4.24 Quotient (Factor) Group of G by H
If H is normal subgroup of G, the group G/H consists of the cosets of H in G is the quotient group of G by H
Theorem 4.25 Quotient Group => Homomorphic Image
(a) = aH is an epimorphism from G to G/H
Theorem 4.26 Kernel of a Homomorphism
If f is a homomorphism from G to G', ker f is a normal subgroup of G
Theorem 4.27 Homomorphic Image => Quotient Group
Let G and G' be groups with G' a homomorphic image of G. Then G' is isomorphic to aquotient group of G
Theorem 4.28 Fundamental Theorem of Homomorphisms
If is an epimorphism from the group G to the group G', then G' is isomorphic to G/ker
Skipped
Chapter 5 Rings, Integral Domains and Fields
Section 5.1 Definition of a Ring
Definition 5.1a A set R is a ring it has all 6 properties:
a) closed under + and .
b) associative under + and .
c) commutative under +
d) contains additive identity = zero = 0
e) contains additive inverses = -a = negative (opposite) of a, applies in subtraction
f) two distributive laws hold
Definition 5.1b Alternative Definition of a Ring:
a) R forms an abelian group under +
b) R is closed under associative multiplication
c) two distributive laws hold
Definition 5.2 Subring, analogous to subgroup
Theorem 5.3 Equivalent set of conditions for a subring
a) S is nonempty
b) x, y in S implies x+y and xy are in S
c) x in S implies -x in S
Theorem 5.4 Characterization of a subring
a) S is nonempty
b) x, y in S implies x-y and xy are in S
S = {0} and S = R are trivial subrings
