# Groups.

Bézout’s identity. Let a and b be integers with greatest common divisor d. Then there exist integers x and y such that ax + by = d.

Consider that ab mod n is the unique integer r such that a·b = nq + r, where 0 ≤ r, n and a·b is ordinary multiplication.

A binary operation on a set G is a method, function, or correspondence that assigns to each ordered pair of elements of the set G a uniquely determined element of the set.For example, addition and multiplications are binary operation on ℕ, ℤ, and ℚ. On the other hand, division of integers is not a binary operation on ℤ.

A binary operation is simply a formula or method of combining the elements of a set, two at a time, in such a way that their combination is also a member of the set. This condition is called closure.

A division is not a binary operation on the set of natural ℕ, integer ℤ, rational ℚ, real ℝ and complex numbers ℂ.

For a binary set, a binary operation can be defined by a table using the following rule, (ith entry on the left)*(jth entry on the top) = (entry in the ith row and jth column of the table). Figure 1.c.

Let M(ℝ) be the set of all matrices with real entries. Matrix addition is not a binary operation on M(ℝ) when the matrices do not have same dimension.

Let ∗ be a binary operation on S, H a subset of S (H ⊂ S). The subset H is closed under ∗ if ∀a, b ∈ H, we also have a ∗ b ∈ H. Examples: ℝ* (ℝ* ⊂ ℝ) is not closed under +: 3 + (-3) = 0 and 0 ∉ ℝ*; F(ℝ, ℝ), the set of all real-valued functions f having ℝ as domain, is closed under the binary operations +, -, ·, and ◦ (composition).

# Group

A group is a set G together with a binary operation on G, denoted as ◦, ·, or simply omitted, such that the following three requirements or axioms are satisfied.

1. Associativity. The operation is associative; that is, (ab)c = a(bc) for all a, b, c in G.
2. Identity. There exist an element e (called the identity) in G such that, for every a in G, ae = ea = a for all a in G.
3. Inverses. For each element a in G, there exists an element b in G such that ab = ba = e. It is called the inverse of a andd is commonly denoted a-1.

The definition of a group does not require that ab=ba for every pairs of elements a and b. If this additional condition holds, then the operation is said to be commutative, and the group is called an Abelian group.

# Examples

• ℤ, ℚ, and ℝ are all groups under addition. The identity is 0 and -a is the inverse of a. (ℝ*, ·) is a group. The identity is 1 and 1/a is the inverse.
• (ℤ, ·) is not a group because the only integers with inverses under multiplication are 1 and -1. As not all integers have inverses, e.g., 2 or 3, it follows that (ℤ, ·) is not a group.
• (ℚ+, ·). The identity is 0 and 1a is the inverse of a.
• Irrational numbers under multiplication is not a group, e.g., $\sqrt{2}·\sqrt{2} = 2$, so it is not closed under multiplication.
• Zn = {0, 1, 2, … n-1} is a group under addition modulo n. For j=0, the inverse is itself; for any j>0 in Zn, the inverse of j is n-j.
• You can multiply elements of Zn, but you do not obtain a group, e.g., 0 does not have a multiplicative inverse. An integer has a multiplicative inverse modulo n if and only if a and n are relative prime. Figure 1.b.

Let n be an integer, suppose i is coprime to n, then αi + βn = 1 for some α, β ∈ Z by Bézout’s identity ⇒ αi = 1 - βn ⇒ αi≡1(mod n) and i is invertible.

Suppose that i is invertible, and i is not coprime to n, then i = da, n = db, for some d > 1 and αi = 1 + βn for some α, β ∈ Z ⇒ αda = 1 + βnb ⇒ d(αa -βb) = 1 ⇒ d = ±1 which is impossible since d > 1.

For each n > 1, we define Un to be the set of all positive integers less than n that have a multiplicative inverse modulo n, that is, there is an element b∈ Zn such that ab = 1. Un = {a ∈ Zn: a is relatively prime to n, a < n} = {a ∈ Zn: gcd(k, n)=1}.

For n = 10, U10 = {1, 3, 7, 9}. The Cayley table for U10 is (Figure 1.a.)

It is a group under multiplication modulo n, called the multiplicative group of integers modulo n.

Let’s prove it.

1. a, b ∈ Un, (ab)-1=b-1a-1 because (ab)(b-1a-1)=a(bb-1)a-1 = aa-1 = 1
2. 1 is the identity.
3. Associativity is inherited from Zn.
4. Inverses works by definition.
• The dihedral group D3 is the symmetry group of the equilateral triangle.

• Let V be a vector space over a field F. An automorphism is a bijective homomorphism that maps V to itself. The set of all automorphisms of V is denoted by Aut(V). Aut(V) = {φ:V→V: φ is lineal and bijective} is a group where the group operation is the composition. φ is a mapping that preserves the operations of vector addiction and scalar multiplication, that is, (λφ)(αv + βw) = α(λφ)v + β(λφ)w and (φ + φ’)(αv + βw) = α(φ + φ’)v +β(φ + φ’)w.

• $GL(2, ℝ) = \bigl\{ {{[\bigl(\begin{smallmatrix}a & b\\ c & d\end{smallmatrix}\bigr)]: a, b, c, d ∈ ℝ, ad - bc ≠ 0}} \bigr\}$ is the group of invertible 2 x 2 matrices with entries in ℝ and non-zero determinant.

The operation is defined as $[\bigl(\begin{smallmatrix}a_1 & b_1\\ c_1 & d_1\end{smallmatrix}\bigr)][\bigl(\begin{smallmatrix}a_2 & b_2\\ c_2 & d_2\end{smallmatrix}\bigr)]=[\bigl(\begin{smallmatrix}a_1a_2+b_1c_2 & a_1b_2+b1d_2\\ c_1a_2+d_1c_2 & c_1b_2+d_1d_2\end{smallmatrix}\bigr)]$

∀A, B ∈ GL(2, ℝ), det(AB)=det(A)*det(B)≠ 0, so AB∈ GL(2, ℝ), and therefore, it is closed under matrix multiplication. The identity is $[\bigl(\begin{smallmatrix}1 & 0\\ 0 & 1\end{smallmatrix}\bigr)]$; the inverse of $[\bigl(\begin{smallmatrix}a_1 & b_1\\ c_1 & d_1\end{smallmatrix}\bigr)]$ is $[\bigl(\begin{smallmatrix}\frac{d}{ad-bc} & \frac{-b}{ad-bc}\\ \frac{-c}{ad-bc} & \frac{a}{ad-bc}\end{smallmatrix}\bigr)]$.

• ℂ* = {a + bi : a, b ∈ R, a ≠ 0}, is the set of nonzero complex numbers. ℂ* under the operation of multiplication forms a group. Its identity is 1, and $z^{-1}=\frac{a-bi}{a^{2}+b^{2}}$

Real numbers can be represented as point on a one-dimensional number line. Complex numbers, with their real and imaginary components, require a two dimensional complex-number plane. This complex number plane can also be represented with polar coordinates, so z = x + iy = r(cosθ + isenθ). r = |z| = $\sqrt{x^{2}+y^{2}}$, x = r cosθ, and y = rsinθ.

Definition. A group is finite if it has a finite number of elements. Otherwise, it is said to be infinite. The number of elements in a group G is called the order of the group, and is denoted by |G|, e.g., ℤ10 and U10 are finite group of orders 10 and 4 respectively; ℤ is an infinite group under addition.

# Properties of Groups

Uniqueness of the identity. Let (G, ◦) be a group, then there is exactly one neutral element or identity e ∈ G such that eg = ge = g ∀g∈ G.

Proof. Let e, e’∈ G be neutral elements. Thus, ∀a ∈ G, we have ae = ea = a (i), ae’ = e’a = a (ii)
e’∈ G, e’e = ee’ = e’ (i)
e ∈ G, ee’ = e’e = e (ii). Thus, e = ee’ = e'.

Uniqueness of Inverses. Let (G, ◦) be a group, then there is a unique element b in G such that ab = ba = 2.

Proof. Let a ∈ G, a-1, a’-1 be inverses of a, a-1 ≠ a’-1, aa-1=a-1a=e and a-1 ≠ a’-1, aa-1=a-1a=e, aa’-1=a’-1a=e

aa-1 = a-1a ⇒ a’-1(aa-1) = a’-1(a-1a) ⇒ [Associativity] (a’-1a)a-1 = a’-1(a-1a) ⇒ ea-1 = a’-1e ⇒ [Identity] a-1 = a’-1.

Proposition 2. Let (G, ◦) be a semigroup (it is closed and associative) with an identity such that, ba = e that is, every element of S has a left inverse with respect to its identity. Then ab = e, that is, b is also a right inverse.

Proof. ba = e ⇒ (ba)b = eb ⇒ [Associativity & Identity] b(ab) = b ⇒ [b has a left inverse, b-1] b-1b (ab) = b-1b = e ⇒ ab = e.

Proposition. The inverse of the inverse of a group element is the element itself, that is (a-1)-1 = a and (ab)-1 = b-1a-1.

Proof. The first part is just reinterpreting the equation aa-1 = a-1a = e.

ab(b-1a-1) = ⇒ [Associativity] a(bb-1)a-1 = aa-1 = e.

(b-1a-1)ab = ⇒ [Associativity] b-1(a-1a)b = b-1b = e.

Cancellation property. Let G be a group, a, b, and c ∈ G. Then, the following hold:
Left cancellation law. If ab = ac ⇒ b = c.
Right cancellation law. If ba = ca ⇒ b = c.

Proof. ab = ac ⇒ a-1(ab) = a-1 (ac) ⇒ [Associativity] (a-1a)b = (a-1a)c ⇒ b = c.

The proof of the right cancellation law is analogous.

Proposition. Let G be a group and a and be any two elements in G. Then, the equations ax = b and xa = b have unique solutions in G.

Proof: First, let’s show the existence of at least one solution. a-1b is a solution of ax=b. We leve the proof of xa=b as an exercise.

a(a-1b) = [by associativity law] (aa-1)b = [by definition of inverses, a-1] eb = b.

To show uniqueness, let’s assume that we have two solutions y1 and y2.

ay1 = b = ay2 ⇒ ay1 = ay2 ⇒ a-1(ay1) = a-1(ay2) ⇒ [by associativity law] (a-1a)y1 = (a-1a)y2 ⇒ [by definition of inverses, a-1] ey1 = ey2 ⇒ y1 = y2

Notation. Let G be a group and a and element of G, then we define a0 = e. For n ∈ ℕ, an = a·a···a, n times, and a-n = a-1·a-1···a-1, n times.

The Laws of exponent for groups. Let (G,⋅) be a group and let a ∈ G. If m and n are integers, then am⋅an=am+n, (am)n=amn, and (ab)n=(b-1a-1)-n. Futhermore, if G is abelian, then (ab)n=(b-1a-1)-n = anbn

Let’s prove am⋅an=am+n and (am)n=amn.

am⋅an = a·a···a · a·a···a, m and n times respectively = a·a···a, m + n times = am+n.

(am)n= a·a···a (m times) · a·a···a (m times) ··· a·a···a (m times), n copies of a·a···a = a·a···a (mn times) = amn

Notation. When a group is Abelian, addition notation is often used, e.g., a+b, 0 as e, -a is the inverse of a, na instead of an = a + a +… + a (n times), and so on.

Bitcoin donation