Algebra Flashcards
The Division Algorithm
The Division Algorithm states that for any integers a and b (with b>0), there exist unique integers
q (quotient) and r (remainder) such that:
a = bq +r
and
0<=r<b
This pair(q,r) is unique for given a and b
Definition of Divisibility
An integer a divides another integer b if there exists an integer
c such that b=ac. This relationship is often denoted as a∣b.
What integer can 0 divide?
The only integer that 0 divides is 0 itself.
Definition of Greatest Common Divisor (GCD)
The GCD of two integers
a and b is a non-negative integer
r that divides both a and b and is greater than any other common divisor s of a and b.
Divisibility of the GCD
If r is the greatest common divisor (gcd) of integers a and
b, then s divides r
GCD with Zero
For any non-negative integer
a, the greatest common divisor (gcd) of a and 0 is a
GCD Properties with Sign Changes
The greatest common divisor (gcd) is unaffected by the signs of its arguments
i.e. gcd(a,b) = gcd(-a,-b)
Bézout’s Identity
For any integers a and b, there exist integers r and s such that
ar+bs=gcd(a,b)
Euclid’s Algorithm Foundation
For any integers a and b (where b>0), there exist unique integers
q (quotient) and r (remainder,
0≤r<b) such that a=bq+r.
Then gcd(a, b) = gcd(b,r)
Definition of a Prime Number
A prime number is a positive integer n whose positive integer divisor is 1 or itself.
By Bezout, If n divides the product ab of two integers a and b, then n must divide at least one of a or b.
This is used to prove the FTA
Fundamental Theorem of Arithmetic
Every integer can be expressed uniquely as a product of primes raised to their respective powers, often written as:
(−1) ^r∞ ∏ p^rp
- p represents a prime number,
- rp is the non-negative integer exponent of the prime p.
- r∞ is 0 or 1, indicating the sign (1 for negative numbers, 0 for non-negative numbers).
Equivalence Relations
Let R be a relation on S. For an element a in S, the equivalence class [a] includes all elements b in
S that are related to a under
R, denoted as aRb.
If R is an equivalence relation, then
aRb if and only if [a] = [b]
And Equivalence relation is said to be reflexive, symmetric and transitive.
Bijective Correspondence between Equivalence Relations and Partitions
Given a set S, there exists a bijective correspondence between
* the equivalence relations R on S,
* the partitions P (a set of non-overlapping subsets of S) on S.
Equivalence Relation for Congruence Modulo n
For a positive integer n, the relation R on Z (set of all integers) defined by a≡b(modn) forms an equivalence relation if and only if n divides b − a
Definition of Zn
Let Zn denote the set of equivalence classes [a] with respect to (≡, Z).
Since a ≡ b mod n if and only if
[a] = [b], a lot of equivalence classes may be identified
Operations in Zn and Size of Zn
Size of Zn:|Zn| = n
Addition: [a]+[b]=[a+b]
Subtraction: [a]−[b]=[a−b]
Multiplication: [a][b]=[ab]
Division: Not defined
Equivalence Under Operations: If a≡a′ modn and b≡b′ modn, then
[a]+[b]=[a′]+[b′], [a]−[b]=[a′]−[b′] and [a][b]=[a′][b′]
Multiplicative Inverse in Zn
An element [a] in Zn has a multiplicative inverse if there exists integer b such that [a][b]=[1] (equivalent to ab≡1modn).
Multiplicative inverse of [a] is denoted as [a]^−1
Uniqueness of Multiplicative Inverse in Zn
If [a] in Zn has a multiplicative inverse, it is unique.
Given two elements [b] and [c] such that [a][b]=[1] and [a][c]=[1],
By associativity, c=[c][1] simplifies to ([c][a])[b]=[1][b], showing [c]=[b]
Condition for Multiplicative Inverse in Zn
An element [a] of Zn has a multiplicative inverse if and only if
gcd(a,n)=1.
This is verified using Euclid’s algorithm, which finds integers
b and c such that ab+nc=gcd(a,n)=1.
Thus, ab≡1modn, confirming
[a][b]=[1]
Absence of Multiplicative Inverse Zn
An element [a] of Zn lacks a multiplicative inverse if and only if there is a non-zero b such that ab≡0 modn
Group Definition
A group is a set G equipped with an operation ∗ that satisfies the following axioms:
(G0) Closure: For all a,b in G, the result of a∗b is also in G
(G1) Associativity: For all a,b,c in G,
(a∗b)∗c=a∗(b∗c)
(G2) Identity: There exists an element e in G such that
a∗e=e∗a=a for every a in G
(G3) Inverses: For every element
a in G, there exists an element
b in G such that a∗b=b∗a=e, where
e is the identity element
(G4) Commutativity (For abelian groups): For all a,b in G, a∗b=b∗a
When these five conditions hold, we say (G, ∗) (or simply G if the operation ∗ is clear from the
context) is a commutative/abelian group
Basic Properties of a Group (G, * )
Uniqueness of Identity: The identity element of G is unique
Uniqueness of Inverses: Each element a in G has a unique inverse, denoted as
a^−1
Cancellation Law: If a∗b=a∗c, then b=c. Similarly, b∗a=c∗a, then b=c
Inverse of a Product: For any a,b in G, the inverse of their product is (a∗b)^−1=b^−1∗a^−1
Ring Axioms
A ring R is a set equipped with two operations: addition (+) and multiplication (×), which satisfy the following axioms:
Addition Axioms:
R+0: Closure under addition.
R+1: Associativity of addition.
R+2: Existence of additive identity (0).
R+3: Existence of additive inverses.
R+4: Commutativity of addition.
Multiplication Axioms:
Rx0: Closure under multiplication.
Rx1: Associativity of multiplication
Distributive Axioms:
Rx+: Distributivity of multiplication over addition from the left.
R+x: Distributivity of multiplication over addition from the right.
Abelian Group from Ring Axioms
The Addition axioms say that
(G,*) = (R,+) is an additive (abelian group.
Operations in Groups and Rings
In groups and rings, the operations + and × are conventional symbols for the operations that meet specific conditions.
Notation for Multiplication in Algebra
We often write ab instead of a × b
Definition of a Commutative Ring
A ring R is said to be a commutative ring if a × b = b × a holds for all a, b in R
Additive Properties of a Ring
Unique Zero Element: Every ring
R is equipped with a unique zero element that acts as an additive identity; that is, a+0=0+a=a for any a in R.
Unique Additive Inverse: Each element a in R has a unique additive inverse −a such that
a+(−a)=0
Cancellation Law: If a+b=a+c within R, then b=c.
Zero Product Property in a Ring
Let R be a ring. For every element a of R, we have 0a = a0 = 0
When does a Ring have an Identity and what are they
Ring with Identity: A ring R is said to have an identity if there exists an element 1 in R such that for every a in R, a×1=1×a=a
The additive identity 0 and the multiplicative identity
(if exists) do not have to be distinct
Is Zn as a Commutative Ring?
The set Zn, with addition and multiplication modulo n as defined before, is a
commutative ring with identity [1].
Definition of a Unit in a Ring
Let R be a ring with identity element 1. An element a in R is called a unit if there
is an element b in R such that ab = ba = 1. The element b is called the inverse of a.
What are the Units in a Ring with Identity
{units in R} = {elements in R that have multiplicative inverses}
Notation for Units in a Ring
The notation R^× is used to denote the units of a ring R
Units of Zn
The units of Zn are the equivalence classes [a] where
gcd(a,n)=1
Furthermore, |Zn| = φ(n)= Product (p-1)p^rp-1
Rings with Multiplicative Identities of 1 (units)
The identity element 1 is unique.
If 1 is distinct from the additive identity 0, then 0 is NOT a unit.
1 is a unit and its inverse is 1 itself
Properties of Units in Rings
If a is a unit, the inverse of a is unique.
If a is a unit, then so is a^−1 the inverse of a
If a and b are units, then so is ab; and its inverse is b^−1a^−1
Set of Units R^x
For a ring R with identity, the set
R^× of units forms a group under multiplication
If the ring R is commutative, the group R^× is abelian,
Definition of a Field
A field is a commutative ring
(F, +, ×) satisfying the axioms:
(F, +) is an (abelian) additive group (with identity element 0)
(F −{0}, ×)is a multiplicative group (with identity element 1)
The additive identity ‘0’ (the identity element in the group
(F, +)) is distinct from the
multiplicative identity ‘1’ (the identity element in the group
(F − {0}, ×))
When do we deny a set from becoming a field and why?
If in a ring the multiplicative identity (1) is equal to the additive identity (0), then every element
a in the ring would satisfy 1×a=0×a=0
So the condition 1 /= 0 denies any set with one element {1 = 0} any chance of being a field
Hierarchical Structure of Algebraic Systems
Field ⇒ Ring ⇒ Group
Field Structure of Fp
If p is a prime number, then Fp = Zp is a field
The set of Complex numbers
Complex numbers are defined as elements of the form a+bsqrt(−1)
, where a and b are real numbers. The set of complex numbers is denoted by C
Field Structure of Complex Numbers
The set C is a field
Division Ring
We say that a ring R with identity is called a division ring if it satisfies all the axioms except the commutativity of multiplication (a × b = b × a for all a, b in R)
a field assumes the set of non-zero elements is an abelian group with respect to ×
Cancellation Law in Division Rings
Let R be a division ring and a is non-zero element of R. If ab = ac, then b = c
Definition of Polynomials
A polynomial f in one variable X with coefficients in a ring R is expressed as
f=cnX^n+cn−1X^n−1+⋯+c1X+c, where c n ,cn−1,…,c1 ,c are elements of R, known as the coefficients of f.
The set of all such polynomials is denoted by R[X]
Degree of a Polynomial
For a non-zero polynomial f in one variable X, the degree of f, denoted as deg(f), is the highest power n for which the coefficient
cn of Xn is non-zero
Monic Polynomials
A non-zero polynomial f = cnX^n + cn−1X^n−1 + · · · + c1X + c of degree n is called monic if the leading coefficient cn = 1.
The zero polynomial is defined to be monic
Operations and Properties of Polynomial Rings
Addition: (f + g)(X) = f(X) + g(X) =
SUMn (cn(f) + cn(g))X^n
Multiplication: (fg)(X) = f(X)g(X) = SUMn ( SUMr cr(f)c(n−r)(g)
Properties:
If R is a ring, then so is R[X] in terms of addition
If R is a ring with identity, then so is R[X]
If R is commutative, then so is R[X]
Polynomial Rings and Division
If (R, +, ×) is a ring with identity 1, then R[X] is not a division ring
Units in Polynomial Rings
Let (F, +, ×) be a field. The units F[X]× of F[X] are F× = F − {0}
Division Algorithm for Polynomials
For any polynomials f and g in
F[X] where g is non-zero, there exist polynomials q (quotient) and
r (remainder) in F[X] such that:
f=gq+r
where r=0 or deg(r)<deg(g)
Divisibility Among Polynomials
Let f and g be polynomials in F[X]. We say that g divides f , or g is a factor of f ,if there exists a polynomial q in F[X] such that f = gq
Polynomial Factorization in Fields
Let F be a field. Let f in F[X] and α be an element of F. Then there exists q in F[X] and r in F such that
f = (X − α)q + r
Evaluating Roots and Factors of Polynomials
For any polynomial f in F[X] and any a in the field F, the value
f(a) represents the remainder when f is divided by (X−a)
Fundamental Theorem of Algebra in Complex Polynomials
For any non-zero polynomial of degree n≥1 with coefficients in the complex numbers C, 𝑐𝑛𝑋^𝑛+…+𝑐0
must have at least one root within
C.
The Complex Fundamental Theorem of Algebra in Polynomials with multiplicities
Every non-zero polynomial f(X)=cn
X^n+…+c0 of degree n≥1 with coefficients in the complex numbers C can be completely factored into n roots in C, including their multiplicities.
f(X) = cn(X − αn)(X − αn−1)…(X − α1)
where α1,…,αn are the roots of f(X)
Generalizing GCD for Polynomials
Any two polynomials f and g have a greatest common divisor in F[X].
The gcd of two polynomials in F[X] can be found by Euclid’s algorithm
If gcd(f , g) = γ (a polynomial in F[X]), then there exist p, q in F[X] such that
fp + gq = γ
Ring Structure of 2x2 Matrices
M2(R) is a ring. If R is a ring with identity, then so is M2(R)
Additive and Multiplicative Identities in Matrix Rings
The additive identity in a matrix ring M2(R) is represented by a 2x2 zero matrix
The multiplicative identity, assuming R has an identity element 1, is the 2x2 identity matrix
Non-Commutativity of 2x2 Matrix Rings
M2(R) is never commutative, even if R is commutative
Properties of Non-Trivial Matrix Rings
For a ring R with identity, if for
every elements a, b in R, the product is always ab = 0, then M2(R) is neither commutative nor a division ring.
Permutation of a Set
A permutation of a set S is a function f : S –> S which is bijective (one-to-one and
onto)
Notation for Permutations
The set of permutations on the set {1, . . . , n} is denoted Sn
every element σ in Sn is written as:
f = (1 … n)
(f(1) … f(n))
Size of the set of permutations
|Sn| = n!.
Composition of permutations
If f and g are permutations, we define the composition, denoted
f ◦ g to be that which sends s in S to f(g(s))
Set of the composition of permutations
If f and g are elements of Sn, then so is the composite f ◦ g is in Sn
Inverse of permutations
If f is in Sn, then the inverse function f^−1 exists and is an element of Sn
Order of permutations
Let f be an element of Sn. The order of f is the smallest number of times we compose f with f itself, f ◦ f ◦ f … , to get the identity
Cycles in Permutation Groups
A cycle (y1 ,y2 ,…,yr) in the symmetric group Sn represents a permutation that sends each element yi to yi+1 (with yr mapping back to y1), while all other elements remain unchanged. This transformation maps the sequence as y1→y2
→…→yr→y1, leaving all elements not in {y1 ,…,yr} unchanged.
Disjoint notation of Cycles
Any permutation can be written as a composition of disjoint cycles. The representation is unique, up to the facts that:
The cycles can be written in any order,
Each cycle can be started at any point,
Cycles of length 1 can be left out.
Calculating the order of a permutation
The order of a permutation is the least common multiple of the lengths of the
cycles in the disjoint cycle representation.
Permutations as Groups
(Sn, ◦(composition)) is a group
When is the Group of Permutations abelian
Sn is an abelian group if n 6 2 and is non-abelian if n > 2
Definition of a Subgroup
Let (G, ∗) be a group and Γ be a subset. We say that Γ is a subgroup of G if (Γ, ∗) is a group.
(G0) If a and b are elements of Γ, then a ∗ b is an element of Γ
(G1) If a, b,c are elements of Γ, then (a ∗ b) ∗ c = a ∗ (b ∗ c) holds.
(G2) Γ contains the identity element eΓ. In fact, eΓ = e (the identity element of G)
(G3) Every element of Γ has an inverse. By the uniqueness, this inverse is the inverse we get when
we think of it as an element of G
Lagrange’s Theorem
Let G be a finite group and H be a subgroup. Then |H|
divides |G|
When is Γ a subgroup of (G, *)
A non-empty subset Γ of a group (G, ∗) is a subgroup if and only if, for every g, γ in Γ, g ∗ γ^−1 is in Γ.
Properties of a Partition
∅ is not a part of P
If A and B are distinct parts of P, then A ∩ B = ∅,
The union of all parts of P is S
