Definitions/Theorems
If we can write an integer a as a = qb + r and r = 0, then we can say this about a and b.
What is b divides a, or b|a?
If G = Z/12, compute 93
93 = (9 + 9 + 9) (mod 12) = 3
Compute (120, 84) using the Euclidean Algorithm.
(120, 84) = 12
The following are equivalent to "b divides a":
1. a has a remainder of 0 when divided by b
2. We can write a=bk, for some int. k
3. ?
What is a = 0 (mod b)?
True/False: when performing group element exponentiation, (ab)n=anbn.
False. This is only true when ab=ba.
Compute 122019 as an element of Z/15Z.
122019 = 3 (mod 15)
Two integers a and b are coprime if and only if we can write them in this linear combination.
What is as + bt = 1?
What is the order of 7 as an element of U(15)?
o(7) = 4
Compute 82018 as an element of U(15)
82018 = 4 (mod 15)
The GCD of integers a and b is the largest integer satisfying these TWO additional properties.
What is,
1. A divisor of a, and
2. A divisor of b ?
(or it must divide both a and b)
Which of the following are NOT a group, and why?
1. Z/nZ: set of integers (mod n) under +(mod n)
2. Z: the set of all integers under *
3. U(n): set of integers (mod n) coprime to n under *(mod n)
2. Z: the set of all integers under *
It does not satisfy inverses.
(Note: Z is a group under +)
Determine f -1 for f = 6x + 5 in Z/12Z[x] (polynomials with coefficients in Z/12Z)
f -1 = -6x - 5 (mod 12)
f -1 = 6x + 7
The Quotient-Remainder Theorem states: given any integer a and positive integer b, there exist unique integers q and r with these TWO properties.
What is,
1. 0 <= r < b, and
2. a = qb + r ?
Let G be a set and let * be an operation on G. Give the 4 conditions for G to be a group.
1. * is a binary operation
2. * is associative: a*(b*c) = (a*b)*c
3. There is an identity element, e, of G: a*e = e*a = a
4. There is an inverse of every element: a*b = b*a = e
Determine ( 11 3 ) ^(-1)
( 6 2 ) in GL(2, Z/13Z).
( 7 9 )
( 5 6 )