Unordered Concepts

If $A$ is a set, the collection of all its subsets also forms a set, denoted as $P(A)$ or $2A$, called the power set.

The Cartesian product between $A$ and $B$ is the set consisting of all ordered pairs of elements in $A$ and elements in $B$. We can write this as

Functions

A function or a map $f$ between $A$ and $B$ is a relation between $A$ and $B$, such that for any $a\in A$, there is a unique $b\in B$, such that $(a,b)\in f$ . We denote this $b$ as $f(a)$. We often write such a function as

$A$ is the domain, $B$ is the codomain.

Relation of Functions

• $A$ function $f$ is called an injection if $f(a)=f(b)$ implies $a=b$.

• It is called a surjection if the range equals codomain. $f(a)=B$. Or, for any $b\in B$, $\mathrm{\exists }a\in A$ such that $f(a)=b$.

• It is called a bijection if it is both an injection and a surjection.

identity function

The identity function from A to itself is defined as $i{d}_A:A\to A,a\mapsto a$. AKA, $i{d}_A=\{(a,a):a\in A\}\subseteq A\times A$

If $C=A$, $g\circ f=i{d}_A$, $f\circ g=i{d}_B$, we call $g$ the inverse of $f$,denoted as $g=f^{-1}$, and $f$ to be invertible.

Group

Definition

A group is a pair $(G,\ast )$, where $G$ is a set,$\ast :G\times G\mapsto G$ a map, such that:

• function: $\ast$ is well-defined
• identity: There is an element $e\in G$, such that for any $a\in G$, $\ast (e,a)=\ast (a,e)=a$.
• associative: for any $a,b,c\in G$, $\ast (\ast (a,b),c)=\ast (a,\ast (b,c))$.
• inverse: for any $a\in G$, there is some other element $b\in G$ such that $\ast (a,b)=\ast (b,a)=e$. Later $b$ will be shown to be unique, and we denote it as $a^{-1}$.

$\ast (a,b)$ can also be written as $a\ast b$ or $a\cdot b$ or $ab$. The identity can also be denoted as $0$ or $1$. When $(G,\ast )$ is a group we can also say “$G$ is a group under $\ast$”.

Note: To show a function is well-defined is also proving that the closure of the group. For every pair of elements $a,b$ in the group, the result of the group operation (often denoted as $\cdot$ or $+$) on $a$ and $b$ must also be in the group. i.e. $G\times G\to G$ on $(G,+)$. For any $g,f\in G$ we have $(f+g)(a)=f(a)+g(a)$ since $f(a),g(a)\in G$, $f+g\in G$. So, $+$ is well-defined.

Note. Well-Defined means

1. for some $x,y\in G$ such that $x=y$ implies $f(x)=f(y)$.
2. one-to-one of $f(x)=f(y)$ implies $x=y$.

Abelian Group

If $\ast$ is commutative, i.e. for any $a,b\in G$, $a\ast b=b\ast a$, then we call it a commutative group or abelian group.

$(\{e\},(e,e)\mapsto e)$. This is called the trivial group, often denoted as $0$ or $1$.

Example

For $Q\to Q$ there is a map action (composition action) $f:q\to aq$. Show $Q$ is abelian group.

\begin{proof}
Suppose $f(q)=aq$, $g(q)=bq$ are two elements in group, then for any $q\in Q$,

Hence $f\circ g=g\circ f$ is abelian.
\end{proof}

Permutation Group

$A$ is any non-empty set, ($\{$bijections from $A$ to $A$ $\}$, $\circ$). This is called the permutation group or symmetric group. When $A$ is a finite set of $n$ elements this is denoted as $S_n$. $S_n$ are all finite, and is abelian iff $n\le 2$.

Example

$(12)\circ (14)(23)=(1423)$

Homomorphisms

Definition

If $(G,{\ast }_G)$ and $(H,{\ast }_H)$ are two groups, $f:G\to H$ satisfies that for any $a,b\in G$, $f(a{\ast }_{G}b)=f(a){\ast }_{H}f(b)$, then we call $f$ a homomorphism. If $f$ is bijective then we call $f$ an isomorphism.

Note: isomorphism: 1. Well-defined, 2. Bijective, Homomorphisms

Note: The two groups $(G,\ast )$ and $(H,+)$ are isomorphic if there exists an isomorphism from one to the other written as

Sometimes write $G=H$

The set of isomorphisms from $G$ to $G$ (called “automorphisms”) is denoted as $Aut(G)$.

For a group $(G,{\ast }_G)$, a mapping $f:G\to G$ is called automorphism if

1. $f$ is one-one.
2. $f$ homomorphic i.e. $f(a{\ast }_{G}b)=f(a){\ast }_{G}f(b)$ for $\mathrm{\forall }a,b\in G$

Note: If $H=G$ and $\ast =+$ then the bijection is an automorphisms.

Property

If $f$ is a homomorphism then:

1. $f$ sends the identity of $G$ to the identity of $H$
2. For any $a\in G$, $(f(a){)}^{-1}=f(a^{-1})$

Isomorphism Theorem of Groups

Let $G$ be a group, $N⊴G$, $f:G\to H$ a group homomorphism.
$p:G\to Q$ a surjective homomorphism such that $N=\ker (p)$. Then:

1. If $N\subseteq \ker (f)$, then there is a unique homomorphism $g:Q\to H$ such that $f=g\circ p$.
2. If $f$ is a surjection, so is $g$.
3. If $N=\ker (f)$ then $g$ is an injection.
4. (Isomorphism Theorem of Group) $f(G)$ is isomorphic to $G/\ker (f)$.

Subgroup

Definition

If $H\subset G$ contains $e_G$ and is also closed under product and inverse (for any $a,b\in H$ ,$ab\in H$ ,$a^{-1}\in H$),then we call $H$ a subgroup of $G$, denoted as $H\le G$.

Example

The group of integers $\mathbb{Z}$ under addition has subgroups of the form $n\mathbb{Z}$ for every integer $n$. For example:

• $2\mathbb{Z}=\{\dots ,-4,-2,0,2,4,\dots \}$ is the subgroup of even integers.
• $3\mathbb{Z}=\{\dots ,-6,-3,0,3,6,\dots \}$ is the subgroup of integers

Image and Kernel

If $f$ is a homomorphism from $G$ to $H$, then:

1. The image (or range) of $f$, denoted as $f(G)$, is a subgroup of $H$.
2. $f^{-1}(\{e_H\})$, denoted as $\text{ker}(f)$, called the kernel of $f$ (and denoted as $\text{ker}(f)$), is a subgroup of $G$.

Note: The kernel is a normal subgroup of $G$.

Example

Let $G=(\mathbb{Z},+)$ and $H=({\mathbb{Z}}_5,+)$ which is modulo $5$ under addition. The elements of $H$ are $\{0,1,2,3,4\}$. Define a map $f:G\to H$ by $f(g)=g\mathrm{mod}5$.

The $\text{ker}f$ is

Interpretation:

• $f(5)=5\mathrm{mod}5=0$
• $f(10)=10\mathrm{mod}5=f(10)=10\mathrm{mod}5=0$
• $f(-5)=(-5)\mathrm{mod}5=f(-5)=(-5)\mathrm{mod}5=0$
• $\dots$

Example 2

A group $\mathbb{Z}$ and a set $\{1,2,3\}$ has one $\mathbb{Z}$ action:

defined as

Then the kernel of $u$ is $2\mathbb{Z}$ since only even number can make $u(n,x)$ to be itself. i.e. $u(2,x)=2+(-1{)}^2(x-2)=x$.

Normal Subgroup

A subgroup $N\le G$ is called a normal subgroup, denoted as $N⊴G$ ,if for any $a\in N$ , any $g\in G$ , $ga{g}^{-1}\in N$.

Group Action

Definition

Let $G$ be a group, $X$ a non-empty set. A left $G$ action is a map $f:G\times X\to X$, such that:

• For any $x\in X$, $f(e,x)=x$
• For any $g,h\in G$, any $x\in X$, $f(g,f(h,x))=f(gh,x)$.
  $X$ is called a left $G$-set.

Reminder

In $f(g,f(h,x))=f(gh,x)$, where $gh$ is $g\cdot h$. For example,
For $f:(g,x)\mapsto x\ast g$ , the relation should be

where $gh$ is represent as group action not simply $gh$.

Example

Let $G=\mathbb{Z}$ and $X=\{1,2,3\}$ so, $u:\mathbb{Z}\times \{1,2,3\}\to \{1,2,3\}$ defined as map $u(n,x)=n+x$.
So, for any $g,h\in G$, any $x\in X$, we have

Note: we often write the result of a left $G$ action as $(g,x)\mapsto g\cdot x$ or $gx$.

Let $G$ be a group, then:

• The left action of $G$ on itself is defined as $(g,h)\mapsto gh$.
• The conjugate action of $G$ on itself is defined as $(g,h)\mapsto ghf{g}^{-1}$.

A map $f:X\times G\to X$ is called a right $G$ action iff

• For any $x\in X$, $f(x,e)=x$
• For any $g,h\in G$, $x\in X$, $f(f(x,g),h)=f(x,gh)$

Note

The automorphism of a $G$-set $X$ is a bijective function $f:X\to X$ such that for all $f\in G$ and $x\in X:f(gx)=gf(x)$. Which is also the $G$-equivariant (Math 541#^6f534d)

Permutation Representation

Let $X$ be a left $G$-set, then the corresponding homomorphism $G\to S_X$ is called the permutation representation, its kernel the kernel of the action. In other words, the kernel of a left $G$ action on set $X$ is $\{g\to G:\mathrm{\forall }x\in X,gx=x\}$. If the kernel is $\{e\}$ we call the action to be effective.

Notation

We usually take permutation group as these parts:

• $S_n=\{1,2,3,4,\dots ,n\}$
• the set $S_n$ contains $\{e,(1,2),(1,2,3),\dots \}$ there are $n!$ elements
• $\sigma$ is a permutation in $S_n$. It is also a map from $S_n\to S_n$, so it is important to know its permutation order. i.e.

Which is $(1243)$ .

• $\sigma (n)$ is the image of $n$ by mapped $\sigma$. i.e. for upper $\sigma$ we want to find $1$ which is $\sigma (1)=2$ since from the map we know $1\to 2$.

Caylay's Theorem

Any group $G$ is isomorphic to a subgroup of $S_G$.

Equivariant Maps and invariant subsets

Definition

Let $X,Y$ be two left $G$ sets, $f:X\to Y$ is called $G$ - equivariant iff for any $g\in G$, $x\in X$, $f(gx)=g(f(x))$. This means that if you first act on $x$ by $g$ and then apply $f$, it's the same as first applying $f$ to $x$ and then acting by $g$.

Example

Imagine an arrow on a plane that can point in four cardinal directions: North, East, South, or West. Let's represent these directions as a set $Z=\{N,E,S,W\}$
Let $G$ be the group of $90°$ rotations in the plane.
Consider a function $h:Z\to Z$ that rotates the arrow $90°$ clockwise. This function is $G$-equivariant. If you first rotate the arrow by any multiple of $90°$ and then apply $h$, it's the same as first applying $h$ and then rotating by that same multiple of $90°$.

Let $X$ be a left $G$ set, a subset $Y\subseteq X$ is called an $G$- invariant subset iff for any $g\in G$, any $y\in Y$ , $gy\in Y$.

If $X$ is a left $G$ set, $x\in X$, the set ${\text{Orb}}_G(x)=\{gx:g\in G\}$ is a $G$ invariant subset of $X$, called the $G$ orbit of $x$.

Example

For $G$ is $(\mathbb{Z},+)$ and left $G$-set $X$ the set of even integers. Define a group action $u(n,x)=x+2n$.
Consider any even integer $x$, we have ${\text{Orb}}_G(x)=\{gx:g\in G\}$. For any integer in $G$, they such $x+2n$ is even number in $X$, so the orbit of $x$ is $2\mathbb{Z}$.

Let $X,Y$ be left $G$ sets. If $f:X\to Y$ is an equivariant bijection, then so is $f^{-1}$. We call such maps isomorphisms.

Transitive and Stablizer

A left $G$ action on $X$ is transitive, iff for any $x,y\in X$, there is some $g\in G$ such that $y=gx$.

Let $X$ be a left $G$ set, $x\in X$. The stablizer of $x$, denoted as $G_x$, is $\{g\in G:gx=x\}$. If for every $x\in G$, $G_x=\{e_G\}$, we call the left $G$ action on $X$ to be free.

Example

Given the action:

where $n$ is an integer and $x$ is in the set $\{1,2,3\}$.
Transitivity:
We need to check if for every pair $(x,y)$ in $\{1,2,3\}\times \{1,2,3\}$, there exists an integer $n$ such that $u(n,x)=y$.
For $x=1$:

• $u(0,1)=2+(-1{)}^0(1-2)=3$
• $u(1,1)=2+(-1{)}^1(1-2)=1$
• No $n$ makes $u(n,1)=2$.

Thus, the action is not transitive.

Freeness:
We need to check if for every $x$ in $\{1,2,3\}$ and every non-zero integer $n$, $u(n,x)\ne x$.
For $x=1$:

• $u(1,1)=1$

Thus, the action is not free because for $x=1$ and $n=1$, $u(n,x)=x$.

Orbit decomposition, Lagrange’s Theorem

Any left $G$ set $X$ is a disjoint union of subsets of the form $Gx=\{gx:g\in G\}$ which we call $G$ orbits.

Image of a $G$-orbit under a $G$-equivariant map is a $G$-orbit. A subset is $G$-invariant iff it is union of $G$-orbits.

Orbit's Theorem

Two left $G$ sets $X$ and $Y$ are isomorphic iff there is a bijection $f\prime$ from the set $O_X$ of left $G$ orbits in $X$ to the set $O_Y$ of left $G$ orbits in $Y$, such that for any $O$ in $O_X$, $O$ is isomorphic to $f^{\prime }(O)$.

Lagrange’s Theorem

Let $G$ be a finite group, $H\le G$, then $|H|$ is a factor of $|G|$.

Cycle notation

Let $g\in S_n$, consider the $\mathbb{Z}$ action on $\{1,\dots ,n\}$ defined as $(t,a)\mapsto g^t(a)$. Then the set $\{1,\dots ,n\}$ can be decomposed into disjoint union of $\mathbb{Z}$-orbits. For each $\mathbb{Z}$ orbits, we can enumerate the elements in the order of $c,g(c),g^2(c),\dots$ An element of $g$ can be written down by enumerating the corresponding $\mathbb{Z}$ orbits that has length larger than $1$. For example,

can be written as

This is called the cycle notation for elements of a permutation group.

Isomorphism Theorem of Groups

Left Cosets (Group)

Definition

Given a group $G$ and a subgroup $H\le G$, a left coset of $H$ in $G$ with respect to an element $g\in G$ is the set:

Here, $gH$ represents the set of all products where $g$ is multiplied on the left by each element $h$ in $H$.

Note: So the $H$ is a subgroup of $G$ and $|H|$ tell us how many elements in $H$. Then the $G/H$ tell use the number of distinct cosets (each representing a unique "slice" of $G$). Thus $|H|\times |G/H|=|G|$ can tell us the number of cosets times number of elements of a set is formed the elements of $G$.

Example

Consider the group $\mathbb{Z}$ (integers under addition) and the subgroup $2\mathbb{Z}$ (even integers). The left cosets of $2\mathbb{Z}$ in $\mathbb{Z}$ are $2\mathbb{Z}$ itself and $1+2\mathbb{Z}$ (all odd integers). Here, $2\mathbb{Z}$ is the set of all integers of the form $2n$ for $n\in \mathbb{Z}$, and $1+2\mathbb{Z}$ is the set of all integers of the form $1+2n$ for $n\in \mathbb{Z}$.

Note: Left cosets are a way to "translate" a subgroup across the group, and they play a crucial role in understanding the structure of the group, especially in the development of concepts like normal subgroups and quotient groups.

Rings

Definition of Rings

A triple $(R,+,\times )$ is called a ring, where $+:R\times R\to R$, $\times :R\times R\to R$, if

1. $(R,+)$ is an abelian( or commutative) group. The identity of this group is denoted as $0$.
2. For any $a,b,c\in R$, $(a\times b)\times c=a\times (b\times c)$.
3. (Distribution Law) For any $a,b,c\in R$, $a\times (b+c)=a\times b+a\times c$, $(a+b)\times c=a\times c+b\times c$.

Remark: $a\times b$ can be written as $a\cdot b$ or $ab$. The identity of $(R,+)$ is denoted as $0$. The inverse of an element a under $+$ can be written as $-a$.
Remark: If a ring $R$ has identity, $a,b\in R$, $ab=ba=1$, then we can write $b=a^{-1}$.

Remark: Remember to show Existence of Identity Element:
Define a $1$ (or $id(x)$ for function) as multiplies an element only to itself. The identity element called $1_R$.

Note. There are some steps need to do in first condition:

1. Well-defined: check $+,\times$ if well-define
2. Associative: for $x,y,z\in R$ such that $(x+y)+z=x+(y+z)$
3. Identity: Let $0\in R$ be defined as send identity to itself. For $x\in R$, $x+0=0=0+x$
4. Inverse: For any $x\in R$, let $-x$ be $(-x)=-(x)$, for $x\in R$, $x+(-x)=0=(-x)+x$

Definition of Abelian

A ring $R$ is called abelian if for any $a,b\in R$, $ab=ba$. It has identity if there is some element $1\in R$ such that $1a=a1=a$ for all $a\in R$. It is called a field if $(R\setminus 0,\times )$ is an abelian group.

Quotient Ring

Let $R$ be a ring, $I$ an ideal of $R$, the ring $(R/I,+,{\times }^{\prime })$ as defined in Math 541#Theorem is called the quotient ring.

The elements if $R/I$ are the left cosets of $I$ in $R$: for $a$ is an element of $R$, the coset $a+I$ is an element of $R/I$.

Operations:

1. $(a+I)+(b+I)=(a+b)+I$
2. $(a+I)(b+I)=ab+I$

Example

Consider the ring of integers $\mathbb{Z}$ and the ideal $4\mathbb{Z}$ (multiples of 4). The quotient ring $\mathbb{Z}/4\mathbb{Z}$ consists of the cosets $0+4\mathbb{Z}$, $1+4\mathbb{Z}$, $2+4\mathbb{Z}$, and $3+4\mathbb{Z}$. These cosets are the equivalence classes under the relation of congruence modulo 4.

Quotient Map

and the ring homomorphism $p:R\to R/I$ defined as $r\mapsto r+I$ is called the quotient map.

R - Modules

Let $R$ be a ring. A left $R$-module is an abelian group $(M,+)$ (the identity of which is denoted as $0$) together with a map (called scalar multiplication):

such that:

1. For any $x,y\in M$,$a\in R$,$a(x+y)=ax+ay$.
2. For any $x\in M$, $a,b\in R$, $(a+b)x=ax+bx$.
3. For any $x\in M$, $a,b\in R$, $a(bx)=(ab)x$.
4. If $R$ has identity $1_R$, then for any $x\in M$, $1_{R}x=x$.

Example

Ring $R$ is $(\mathbb{Z},+,\times )$, module is $M=(\mathbb{Z},+)$ under a map. Then the one of submodule is $2\mathbb{Z}$.

Isomorphism Theorem of Module

Let $M$ and $N$ be modules, and let $\phi :M\to N$ be a module homomorphism. Then:

1. The $\mathbf{\text{kernel}}$ of $\phi$ is a submodule of $M$,
2. The $\mathbf{\text{image}}$ of $\phi$ is a submodule of $N$, and
3. The image of $\phi$ is $\mathbf{\text{isomorphic}}$ to the quotient module $M/\ker (\phi )$.

In particular, if $\phi$ is surjective then $N$ is isomorphic to $M/\ker (\phi )$.

Submodule

Let $R$ be a ring, $M$ a $R$ -module, $N$ a subset of $M$. If $N$ is a subgroup of $(M,+)$, and for any $x,y\in N$, $a\in R$, then ($0\in N$ and $-x\in N$)$x+y\in N$ and $ax\in N$, then $N$ is called a submodule.

Example 1

Let's say $M={\mathbb{Z}}^3$ is a module over the ring $\mathbb{Z}$, and you're considering the subset $N=\{(a,b,0)\mid a,b\in \mathbb{Z}\}$.

1. Non-Empty: $N$ contains the zero element $(0,0,0)$, so it's not empty.
2. Addition: If $(a,b,0)$ and $(c,d,0)$ are in $N$, their sum $(a+c,b+d,0)$ is also in $N$.
3. Scalar Multiplication: For any integer $k$ and any element $(a,b,0)$ in $N$, the product $k(a,b,0)=(ka,kb,0)$ is still in $N$.
4. Module Axioms: Addition and scalar multiplication in $N$ are associative, commutative, and distributive, aligning with the module structure of $M$.

Since $N$ satisfies all these criteria, it is indeed a submodule of $M$.

Example 2

Submodule of Polynomials of a Fixed Degree

Module: $R[x]$, polynomials with coefficients from a ring $R$.

Submodule: All polynomials of degree less than or equal to a fixed integer $n$.

Properties:

• Includes polynomials like $a{x}^n+b{x}^{n-1}+\cdots$ (where $a,b,\dots$ are in $R$).
• Closed under addition: Sum of two polynomials of degree $\le n$ is also of degree $\le n$.
• Closed under scalar multiplication: Multiplying by any scalar from $R$ doesn't increase the degree beyond $n$.

Submodule of Polynomials with Specific Coefficients

Module: $R[x]$.

Submodule: Polynomials whose coefficients meet a specific criterion (e.g., all coefficients are even).

Properties:

• An example polynomial could be $2x^3+4x+6$.
• Closed under addition: Adding two such polynomials maintains the criterion.
• Closed under scalar multiplication: Multiplying by scalars from $R$ preserves the coefficient criterion.

Submodule Generated by a Single Polynomial

Module: $R[x]$.

Submodule: All polynomials that are multiples of a given polynomial $p(x)$ in $R[x]$.

Properties:

• Contains polynomials of the form $r(x)p(x)$ where $r(x)$ is any polynomial in $R[x]$.
• Closed under addition: The sum of multiples of $p(x)$ is still a multiple of $p(x)$.
• Closed under scalar multiplication: Multiplying by a scalar from $R$ results in another multiple of $p(x)$.

Cyclic

Suppose $R$ has identity, a left $R$-module $M$ is called cyclic iff there is $a\in M$ (called the generator), for any $b\in M$, there is some $r$ such that $b=ra$.

Cyclic Left $R$-module

If $R$ has identity, $L$ a left $R$-ideal (Math 541#Left ideal), $R/L$ is a cyclic left $R$-module (with generator $a=1+L$)

Example

In the quotient ring $R=\mathbb{Z}/(4)$, we explore the cyclic left $R$-modules. A cyclic module is one that can be generated by a single element. In $R$, the potential generators are the equivalence classes $[0],[1],[2],[3]$. The resulting cyclic modules are:

1. the trivial module $\{[0]\}$,
2. the entire ring $R$ itself (generated by either $[1]$ or $[3]$),
3. and a module comprising $\{[0],[2]\}$ (generated by $[2]$). These examples illustrate the different cyclic modules possible in $R$.
   Those such that for any $m\in M$ and $r\in R$, any $m^{\prime }=r\cdot m\in M$.

Left coset (Rings)

In a ring $R$, a left coset of a subring $S$ with respect to an element $r$ in $R$ is defined as $r+S=\{r+s:s\in S\}$. (This definition uses the addition operation of the ring.)

Example

In the ring of integers $\mathbb{Z}$, consider the subring $4\mathbb{Z}$ (all multiples of 4). The left cosets are $n+4\mathbb{Z}$, where $n$ is an integer. Distinct cosets are created using 0, 1, 2, and 3:

1. $0+4\mathbb{Z}$ (multiples of 4)
2. $1+4\mathbb{Z}$ (numbers 1 more than multiples of 4)
3. $2+4\mathbb{Z}$
4. $3+4\mathbb{Z}$.
   Each coset groups numbers with the same remainder when divided by 4.

Ring Homomorphisms

Let $(R,{+}_R,{\times }_R),(S,{+}_S,{\times }_S)$ be two rings, a map $f:R\to S$ is called a ring homomorphism if for any $a,b\in R$,

1. $f(a){+}_{S}f(b)=f(a{+}_{R}b)$
2. $f(a){\times }_{S}f(b)=f(a{\times }_{R}b)$
3. $f(1_R)=1_S$.

Let $R$ be a ring, $M,N$ be two $R$-modules. A map $f:M\to N$ is called a module homomorphism if for any $a\in R$, $x,y\in M$, $f(ax)=af(x)$, $f(x+y)=f(x)+f(y)$.

Note: $\text{End}(H)$ definition
Let $H$ be an abelian group. Let $\text{End}(H)$ be the set of homomorphisms from $H$ to itself, define $(f+g)(x)=f(x)g(x)$, $(f\times g)(x)=f(g(x))$. Then $(\text{End}(H),+,\times )$ is a group with identity.

Let $R$ be a ring, a subset $S\subseteq R$ is called a subring if $0\in S$, for any $a,b\in S$, $a+b\in S$, $a\times b\in S$, $-a\in S$.

Note. restriction:
Let $f:A\to B$ be a function, $A^{\prime }\subseteq A$, $i$ the inclusion function from $A^{\prime }$ to $A$, then the restriction of $f$ on $A^{\prime }$, denoted as $f{|}_{A^{\prime }}$, is defined as $f\circ i$. Analogy in function Restriction (mathematics) - Wikipedia

Isomorphism Theorem of Rings

Let $R$ and $S$ be rings, and let $\phi :R\to S$ be a ring homomorphism. Then:

1. The $\mathbf{\text{kernel}}$ of $\phi$ is an ideal of $R$,
2. The $\mathbf{\text{image}}$ of $\phi$ is a subring of $S$, and
3. The image of $\phi$ is $\mathbf{\text{isomorphic}}$ to the quotient ring $R/\ker \phi$.

In particular, if $\phi$ is surjective then $S$ is isomorphic to $R/\ker \phi$.

Ideal

Definition of Ideal

Let $R$ be a ring, a subring $S$ of $R$ is called an ideal iff for any $r\in R$, $a,b\in S$, $a+b\in S$, $ar\in S$, $ra\in S$. (Sometimes check inverse and 0 term)

Example

Let $R$ be a ring, $I,J$ two ideals of $R$. Show that the set $\{x+y:x\in I,y\in J\}$ is an ideal of $R$.

\begin{proof} For any $a,b\in J+I$ and $r\in R$, let $a=a_1+a_2$, $b=b_1+b_2$:

1. 0 term: $0=0+0\in J+I$.
2. Addition: $a+b=(a_1+a_2)+(b_1+b_2)\in I+J$.
3. Inverse: $-a=(-a_1)+(-a_2)\in I+J$.
4. Scaler: $ra=r{a}_1+r{a}_2\in I+J$ and $ar=a_{1}r+a_{2}r\in I+J$.
   \end{proof}

Theorem

Let $R$ be a ring, $I$ an ideal of $R$. Then:

1. $I$ is a normal subgroup of $(R,+)$, hence $R/I=\{a+I:a\in R\}$, where $a+I$ is defined as $\{a+h:h\in I\}$, is an abelian group, and the quotient map $p:R\to R/I$ defined as $r\mapsto r+I$ is a group homomorphism from $(R,+)$ to $(R/I,+)$.
2. There is a unique function $\times \prime :R/I\times R/I\to R/I$, such that $(R/I,+,{\times }^{\prime })$ is a ring and $p$ is a ring homomorphism.
3. $\ker (p)=I$

Left ideal

$M$ a left $R$ module, $x\in M$, $Ann(x)=\{r\in R:rx=0\}$ is a submodule of $R$ (seen as left $R$-module), called a left ideal.

Euclid’s Algorithm

Definition (integral domain)

We call a ring $R$ to be a (integral) domain, if it satisfies the following:

1. It is commutative with identity.
2. $ab=0$ implies $a=0$ or $b=0$.

Note. The second condition implies that integral domain does not has zero divisor. That is related to the definition of zero divisor:

In a ring $R$, a non-zero element $a$ is called a zero divisor if there exists another non-zero element $b$ in $R$ such that their product is zero, i.e., $a\cdot b=0$, $a\cdot b=0$ or $b\cdot a=0$, $b\cdot a=0$.

e.g. $\mathbb{Z}/6\mathbb{Z}$ does has zero divisor since $[2]\cdot [3]=[0]$ where $[2],[3]$ are zero divisors.

Definition (PID)

If an integral domain $R$ further satisfies the following:

• Any ideal of $R$ is of the form $(a)=\{ra:r\in R\}$ for some $a\in R$.

It is called a principal ideal domain (PID).

Definition (Euclidean domain)

If $R$ is an integral domain, and there is a function $h:R\setminus 0\to Z\ge 0$ where $\mathbb{Z}\ge 0$ is the set of non negative integers, such that:

1. If $a\ne 0$, $b\ne 0$, then $h(ab)\ge h(a)$.
2. (Division with Remainder) For any $a,b\ne 0$, there is some $q,r\in R$, such that $a=bq+r$, and either $r=0$ or $h(r)<h(b)$.

then $R$ is called an Euclidean domain.

Definition (GCD)

Let $R$ be a PID, $a,b\in R$, the ideal $(a)+(b)=\{ra+sb:r,s\in R\}$ equals some $(m)$, and the number $m$ is called the greatest common divisor of $a$ and $b$, denoted as $m=gcd(a,b)$.

Definition

Euclid’s Algorithm for Bezout’s Problem, which is that:

Given $a,b\in R$, $ab\ne 0$, find $r,s\in R$ such that $ra+sb=gcd(a,b)$.

Extended Euclid's Algorithm

1. Initialization:

   • Start with $r_0=1,s_0=0$ and $r_1=0,s_1=1$.
   • These represent two equations: $r_{0}a+s_{0}b=a$ and $r_{1}a+s_{1}b=b$.

2. Iterative Process:

   • At each step, divide $a$ by $b$ to get a quotient $q$ and a remainder $r$, so $a=bq+r$.
   • Update $a$ and $b$: Set $a=b$ and $b=r$.
   • Update $r_i$ and $s_i$: Set $r_{i+1}=r_{i-1}-q\cdot r_i$ and $s_{i+1}=s_{i-1}-q\cdot s_i$.
   • This process continues until $b$ becomes 0.

3. Result:

   • When $b$ becomes 0, the last non-zero remainder is the GCD, and the corresponding $r$ and $s$ are the coefficients we seek.

Code Example

An example of this algorithm on $\mathbb{Z}$, implemented by Python:

def extended_euclid(a, b):
    """
    Performs the Extended Euclid's Algorithm on integers a and b.
    Returns a tuple (gcd, r, s) such that gcd is the greatest common divisor of a and b,
    and gcd = ra + sb.
    """
    old_r, r = a, b
    old_s, s = 1, 0

    while r != 0:
        quotient = old_r // r
        old_r, r = r, old_r - quotient * r
        old_s, s = s, old_s - quotient * s

    return old_r, old_s, (old_r - old_s * a) // b

# Example usage:
a = 99
b = 78
gcd, r, s = extended_euclid(a, b)
print(f"GCD: {gcd}, r: {r}, s: {s}")