Exam 1 Flashcards
What is the Division Algorithm?
Let a and b be integers with b > 0. Then there exists unique integers q and r with the property that a = bq + r, where 0 <= r < b.
gcd
For any non zero integers a and b, there exists integers s and t such that gcd(a,b) = as + bt. Moreover, gcd(a,b) is the smallest positive integer of the for as + bt.
lcm
The least common multiple of two nonzero integers a and b is the smallest positive integer that is multiple of both a and b.
a mod n
Given two positive integers a and n, mod n is the remainder of the Euclidean division of a by n, where a is the dividend and n is the divisor.
group
Let G be a nonempty set and let * be a binary operation on G. We say (G, *) is a group whenever the following properties hold:
1. For all a, b in G, a * b in G. Thus, G is closed under the binary operation, *.
2. For all a, b, c in G, (a * b) * c = a * (b * c). Thus, * is associative.
3. There exists e in G, such that for all a in G, a * e = a and e * a = a. Thus, we have an identity element e.
4. For all a in G, there exists b in G, such that a * b = e and b * a = e. Thus, each element in G has an inverse, which is usually denoted as a^-1 instead of b.
abelian
A group (G, *) is abelian whenever for all a, b in G, a * b = b * a. (Commutativity)
associativity vs commutativity
Commutative property: The order of numbers in an operation can be changed without changing the result.
Associative property: The grouping of numbers in an operation can be changed without changing the result.
Z_n
Z_n = {0, 1, 2,…, n-1}
U(n)
U(n) = {a \in \mathbb{N} | 1 <= a <= n-1, gcd(a,n)=1}
GL(n, \mathbb{R})
GL(n, \mathbb{R}) is the set of all 2 x 2 matrices with real number entries, such that det(a) =/= 0. This is a group under matrix multiplication.
D_n
A dihedral group is a group of symmetries of a regular polygon with n sides, where n is a positive integer. The dihedral group of order 2n, denoted by D_n, is the group of all possible rotations and reflections of the regular polygons.
n rotations: R_(360/n)
n reflections
group properties
In order for a set to be a group, then it must fulfill the following requirements.
- Closed under the specified binary operation, for all a, b in G, then a * b in G.
- Closed under associativity, (a * b) * c = a * (b * c)
- If the group has an identity element, then it is guaranteed that every element in the set has an inverse
order
The order of a group G, denoted |G|, is the number of elements in G.
Let G be a group, and let a \in G. The order of a is the smallest positive integer n, such that a^n=e. If no such n exists, we say the order of a is infinite.
subgroups
Let (G, *) be a group and let H be a nonempty set of G. We say H is a subgroup of G whenever (H, *) is also a group.
Subgroup Test (One-Step)
Let G be a group and H a nonempty subset of G. If ab^-1 is in H whenever a and b are in H, then H is a subgroup of G. (In additive notation, if a-b is in H whenever a and b are in H, then H is a subgroup of G.)
Subgroup Test (Two-Step)
Let G be a group and let H be a nonempty subset of G. If ab is in H whenever a and b are in H (H is closed under the operation), and a^-1 is in H whenever a is in H (H is closed under taking inverses), then H is a subgroup of H.
- If a,b in H, then a*b in H.
- If a in H, then a^-1 in H.
<a></a>
Let G be a group, and let a be any element of G, Then <a> is a subgroup of G.</a>
center Z(G)
The center, Z(G), of a group G is the subset of elements in G that commute with every element of G. In symbols,
Z(G) = {a in G | ax=xa for all x in G}
cyclic groups
A group G is called cyclic if there is an element a in G such that G={a^n | n in Z}. Such an element a is called a generator of G.
generators
Group G is cyclic if there exists a in G, such that the cyclic subgroup generated by a, <a>, equals all of G. That is, G={na | n in Z}, in which case a is called a generator of G.</a>
Fundamental Theorem of Cyclic Groups
- Every subgroup of a cyclic group is cyclic.
- Suppose G is cyclic with |G| = n, and G = <a>. Then for each positive divisor k of n, there is exactly one subgroup of order k, namely <a^(n/k)>. Moreover, these are all subgroups of G.</a>
Theorem 4.1: Criterion for a^i = a^j
Let G be a group, and let a belong to G. If a has infinite order, then a^i = a^j iff i = j. If a has infinite order, say n, then <a> = {e, a, a^2,…, a^(n-1)} and a^i = a^j iff n divides i-j.</a>
Corollary 1: |a| = |<a>|</a>
For any group element a, |a|=|<a>|.</a>
Corollary 2: a^k = e iff |a| divides k
For any group element a, a^k = e iff |a| divides k.
Corollary 3: a^k = e iff k is a multiple of |a|
For any group element a, a^k = e iff k is a multiple of |a|.
Theorem 4.2: <a^k> = <a^(gcd(n,k)> and |a^k| = n/(gcd(n,k))
Let a be an element of order n in a group and let k be a positive integer. Then <a^k> = <a^(gcd(n,k)> and |a^k|=n/(gcd(n,k)).
Corollary 1: Orders of elements in finite cyclic groups
In a finite cyclic group, the order of an element divides the order of the group.
Corollary Subgroups of Z_n
For each positive divisor k of n, the set <n/k> is the unique subgroup of Z_n of order k; moreover, these are the only subgroups of Z_n.
permutation
A permutation of a set A is a function from A to A that is both one-to-one and onto. A permutation group of a set A is a set of permutations of A that forms a group under function composition.
even, odd permutations
A permutation that can be expressed as a product of an even number of 2-cycles is called an even permutation. A permutation that can be expressed as a product of an odd number of 2-cycles is called an odd permutation.
Symmetric group, S_n
Let A={1, 2 ,3,…, n}. Let G be the set of permutations on A. Then G is a group under function compositive, called the symmetric group on A. We denote this group as S_n.
A_n
The group of even permutations of n symbols is denoted by A_n and is called the alternating group of degree n.
For n > 1, A_n has order n!/2.
