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).
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.
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.
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.
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)]$.
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.
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.