Algebra

Number Theory
- Euler's Totient Function & Modulo Multiplicative Group
- Multiplicative Order & Primitive Root & Index (Discrete Logrithm)
Group
Ring
- Characteristic
- Ideal
Field

Number Theory

Euler's Totient Function and Modulo Multiplicative Group

Modulo Multiplicative Group: $Z_{n}^{*} := {a \in Z_{n} : g cd (a, n) = 1}$ is the set of elements in $Z_{n}$ that has a modular inverse under modulo $n$ .

Euler's Totient Function: $ϕ (n) := ∣ Z_{n}^{*} ∣$ (i.e. the number of elements in $Z_{n}$ that has a modular inverse).

Multiplicative Order and Primitive Root and Index

Multiplicative Order: For any $a \in Z_{n}^{*}$ , the smallest positive integer $k$ that satisfies $a^{k} \equiv 1 (mod n)$ is the multiplicative order. Denoted as $ord_{n} (a)$ .

Primitive Root: Positive interger $g$ that satisfies $ord_{n} (g) = ϕ (n)$ . Primitive roots have the property $g^{ϕ (n)} \equiv 1 (mod n)$ .

Index (Discrete Logrithm): Exists an unique $lo g_{g} (a) := x$ , such that $a \equiv g^{x} (mod n)$ and $g cd (a, n) = 1$ . It is bounded by $0 \leq lo g_{g} (a) < ϕ (n)$ .

$lo g_{g} (ab) \equiv lo g_{g} (a) + lo g_{g} (b) (mod ϕ (n))$
$lo g_{g} (a^{m}) \equiv m lo g_{g} (a) (mod ϕ (n))$
$lo g_{h} (a) \equiv lo g_{h} (g) lo g_{g} (a) (mod ϕ (n))$

Discrete Logrithm Problem: There does not exists an efficient alogrithm that can quickly compute the index.

Group

$(S, \cdot)$ is a group $G$ consists of a non-empty set $S$ and a binary operation $\cdot$ on any 2 elements of $S$ , with the following axioms being satisfied:

Closed: $\forall a, b \in G, a \cdot b \in G$
Associative: $\forall a, b, c \in G, a \cdot b \cdot c = (a \cdot b) \cdot c = a \cdot (b \cdot c)$
Unique Identity: $\exists e \in G, \forall a \in G, a = e \cdot a = a \cdot e$
Unique Inverse: $\forall a \in G, \exists a^{- 1} \in G, e = a \cdot a^{- 1} = a^{- 1} \cdot a$

Subgroup: $H := (U, \cdot)$ is a subgroup of $G$ iff $U ⊊ S$ and $H$ forms a group.

Abelian Group: a group where $\cdot$ is commutative for elements in $S$ (e.g., $(Z, +)$ ).

Coset

For any $a \in G$ ,

$a H := {a \cdot h : h \in H}$ is the "left coset of $H$ in $G$ with the representative $a$ "
$H a := {h \cdot a : h \in H}$ is the "right coset of $H$ in $G$ with the representative $a$ "
$[a]_{H} := a H$ is the "coset of $H$ in $G$ with the representative $a$ " iff $a H = H a$

Coset divides $G$ into subsets based on the relationship between elements in $H$ and any $b \in G$ . All elements of $G$ belongs to some coset, so $G = ⋃_{i = 1}^{n} [a_{i}]_{H}$ .

$a \equiv b (mod H)$ iff $a$ and $b$ have the same relative relationship with $H$ (i.e., $[a]_{H} = [b]_{H}$ ).

For example, let $G = Z$ ,and $H = 3 Z = {0, \pm 3, \pm 6, \dots}$ , all elements $b$ in the congruence class (coset) $[1]_{3 Z}$ all have the same relationship of $b \equiv 1 (mod 3)$ .

Operation on Cosets: $[a]_{H} \cdot [b]_{H} := [a \cdot b]_{H}$

Lagrange's Theorem: For any finite group $G$ with its subgroup $H$ , the cardinality of $H$ divides the cardinality of $G$ (i.e., $∣ H ∣ ∣ ∣ G ∣$ ). Proof: All cosets in $G$ have the same cardinality as $H$ (the ordinary coset), since there exists a bijection mapping between any cosets $[a]_{H}$ and $[b]_{H}$ ; hence, $∣ G ∣ = \sum_{i = 1}^{n} ∣ [a_{i}]_{H} ∣ = \sum_{i = 1}^{n} ∣ H ∣ = n ∣ H ∣$ .

Normal Subgroup: $N$ is a normal subgroup iff $\forall a \in G, a N = N a$

Quotient Group: $G / N := {[a]_{N} : a \in G}$ (e.g., $Z / n Z = {[0], [1], ..., [n - 1]} = Z_{n}$ )

Group Homomorphism and Isomorphism

Homomorphism: For groups $(G, \cdot)$ , $(G^{'}, \times)$ , if exists functions $f : G \to G^{'}$ such that $\forall a, b \in G, f (a \cdot b) = f (a) \times f (b)$ , then these two groups are said to be homomorphism.

Homomorphic Image: $Im (f) = f (G) := {f (a) : a \in G}$ . Does not necessarily be the entire $G^{'}$ (i.e. $f$ may be non-surjective).

Homomorphic Kernal: $Ker (f) := {a \in G : f (a) = e^{'}}$ , where $e^{'}$ is the identity in $G^{'}$ . Does not necessarily be ${e}$ (i.e. $f$ may be non-injective).

Isomorphism: Homomorphism but with the constrain that $f$ is bijective (i.e. $f^{- 1}$ exists). Denoted as $G ≅ G^{'}$ .

Isomorphic groups are essentially the same group, and all properties are commonly shared.

Fundamental Homomorphism Theorem (FHT): For any homomorphism of group $G$ with a function $f$ , there always exists an isomorphism relationship, $G / Ker (f) ≅ Im (f)$ .

Cyclic Group

$⟨ g ⟩ := {g^{n} : n \in Z}$ is a cyclic group with a generator of $g$ iff $⟨ g ⟩$ is a group (e.g., $m Z =< m >$ is a cyclic group).

Order of Element: For any group $G$ , $a \in G$ , if $n$ is the minimum positive integer such that $a^{n} = e$ , then $n$ is the order of element $a$ . This is similar to the multiplicative order for $Z_{n}^{*}$ .

$\forall m \in Z, n ∣ m ⟺ a^{m} = e$ .
If the order of a finite cyclic group $⟨ g ⟩ = n$ , then the order of $g = n$ , and $g \neq = g^{2} \neq = \dots \neq = g^{n} = g^{0}$ .
Any order $n$ finite cyclic group, if $d ∣ n$ , then there exists an unique subgroup with order $d$ .
For any $k \in Z$ , the order of the element $g^{k}$ is $\frac{n}{g c d ( n , k )}$ .
Cyclic group with order $n$ has $ϕ (n)$ distinct generators.
$⟨ g ⟩ ≅ Z_{n}$

For integers $m = 1, 2, 4, p^{k}, 2 p^{k}$ , where $p$ is an odd prime and $k$ is a positive integer, there exists a primitive root $g \in Z_{m}^{*}$ . In addition, $Z_{m}^{*} = ⟨ g ⟩$ forms a finite cyclic group, so primitive roots are generators.

Ring

$(R, +, \cdot)$ is a ring when:

$(R, +)$ is an Abelian group
$(R, \cdot)$ is closed: $a, b \in R ⟹ a \cdot b \in R$
$(R, \cdot)$ is associative: $a \cdot b \cdot c = a \cdot (b \cdot c) = (a \cdot b) \cdot c$
Distributative law holds: $\forall a, b, c \in R, a \cdot (b + c) = a \cdot b + a \cdot c$ and $(b + c) \cdot a = b \cdot a + c \cdot a$

Additionally, more restrictions can be placed:

Ring with Identity: contains an multiplicative identity(i.e. $\exists e \in R, \forall a \in R, e \cdot a = a \cdot e = e$ )
Commutative Ring: operation $\cdot$ is commutative(i.e. $\forall a, b \in R, a \cdot b = b \cdot a$ )
Division Ring: $(R ∖ {θ}, \cdot)$ forms a group

Zero Element( $θ$ ): An element $θ \in R$ such that $\forall a \in R, a \cdot θ = θ \cdot a = θ$ . This is also the additive identity (proof: $a \cdot θ = θ ⟺ a \cdot b = a \cdot b + a \cdot θ = a \cdot (b + θ)$ ).

Identity( $e$ ): The multiplicative identity. For any ring with $∣ R ∣ > 1$ , $θ \neq = e$ (proof by contradiction: $e = θ ⟹ \forall a \in R, a = e \cdot a = θ \cdot a = θ$ ).

Zero Divisor: Non zero elements $a, b \in R$ ( $a \neq = θ, b \neq = θ$ ), such that $a \cdot b = θ$ (e.g. $2, 5 \in Z_{10}, 2 \cdot 5 \equiv 0 (mod 10)$ ).

Integral Domain: a commutative ring with identity that there is no zero divisors and $∣ R ∣ > 1$ .

Characteristic

$Char R := m$ , where $m$ is the smallest positive integer such that $\forall a \in R, θ = \sum_{i = 1}^{m} a$ . If such $m$ does not exists, then $m = 0$ .

This is similar to the additive order of a given $a \in R$ , except that the characteristic of a ring is for ALL $a \in R$ .

Ideal

$(R, +, \cdot)$ is a ring, for some $I \subseteq R$ , if

$\emptyset \neq = I$
$(I, +)$ is a subgroup of $(R, +)$
$I$ satisfies any of:
1. $\forall r \in R, \forall a \in I ⟹ r \cdot a \in I$
2. $\forall r \in R, \forall a \in I ⟹ a \cdot r \in I$

, then $I$ is called the "left ideal of $R$ " if (1) is satisfied, the "right ideal of $R$ " if (2) is satisfied, or simply "(two-sided) ideal of $R$ " if both conditions are met.

$(R, +)$ is an Abelian group
$(R ∖ {θ}, \cdot)$ is an Abelian group
Distributative law holds: $\forall a, b, c \in R, a \cdot (b + c) = a \cdot b + a \cdot c$ and $(b + c) \cdot a = b \cdot a + c \cdot a$

All fields are integral domains, but only finite integral domains are fields.

Jianxun's Blog