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 U_{n} 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∈ Z_{n} such that ab = 1. U_{n} = {a ∈ Z_{n}: a is relatively prime to n, a < n} = {a ∈ Z_{n}: gcd(k, n)=1}.
For n = 10, U_{10} = {1, 3, 7, 9}. The Cayley table for U_{10} 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 D_{3} 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 U_{10} 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^{-1}a=e and a^{-1} ≠ a’^{-1}, aa^{-1}=a^{-1}a=e, aa’^{-1}=a’^{-1}a=e
aa^{-1} = a^{-1}a ⇒ a’^{-1}(aa^{-1}) = a’^{-1}(a^{-1}a) ⇒ [Associativity] (a’^{-1}a)a^{-1} = a’^{-1}(a^{-1}a) ⇒ ea^{-1} = a’^{-1}e ⇒ [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^{-1}b (ab) = b^{-1}b = 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^{-1}a^{-1}.
Proof. The first part is just reinterpreting the equation aa^{-1} = a^{-1}a = e.
ab(b^{-1}a^{-1}) = ⇒ [Associativity] a(bb^{-1})a^{-1} = aa^{-1} = e.
(b^{-1}a^{-1})ab = ⇒ [Associativity] b^{-1}(a^{-1}a)b = b^{-1}b = 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^{-1}a)b = (a^{-1}a)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^{-1}b is a solution of ax=b. We leve the proof of xa=b as an exercise.
a(a^{-1}b) = [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 y_{1} and y_{2}.
ay_{1} = b = ay_{2} ⇒ ay_{1} = ay_{2} ⇒ a^{-1}(ay_{1}) = a^{-1}(ay_{2}) ⇒ [by associativity law] (a^{-1}a)y_{1} = (a^{-1}a)y_{2} ⇒ [by definition of inverses, a^{-1}] ey_{1} = ey_{2} ⇒ y_{1} = y_{2}
Notation. Let G be a group and a and element of G, then we define a^{0} = e. For n ∈ ℕ, a^{n} = 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 a^{m}⋅a^{n}=a^{m+n}, (a^{m})^{n}=a^{mn}, and (ab)^{n}=(b^{-1}a^{-1})^{-n}. Futhermore, if G is abelian, then (ab)^{n}=(b^{-1}a^{-1})-n = a^{n}b^{n}
Let’s prove a^{m}⋅a^{n}=a^{m+n} and (a^{m})^{n}=a^{mn}.
a^{m}⋅a^{n} = a·a···a · a·a···a, m and n times respectively = a·a···a, m + n times = a^{m+n}.
(a^{m})^{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) = a^{mn}
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 a^{n} = a + a +… + a (n times), and so on.