💡 An operation on a set $S$ is a function $S^n⟶S$, where $n\ge 0$ is called the arity of the operation.

💡 An algebra (or algebraic structure or $\Omega$-algebra) is a pair $⟨S;\Omega ⟩$ where $S$ is a set (the carrier of the algebra) and $\Omega =({\omega }_1,\dots ,{\omega }_n)$ is a list of operations on $S$.

💡 A left [right] neutral element (or identity element) of an algebra $⟨S;\ast ⟩$ is an element $e\in S$ such that $e\ast a=a$ [$a\ast e=a$] for all $a\in S$. If $e\ast a=a\ast e=a$ for all $a\in S$, then $e$ is simply called neutral element.

📌 If $⟨S;\ast ⟩$ has both a left and a right neutral element, then they are equal. In particular $⟨S;\ast ⟩$ can have at most one neutral element.

💡 A binary operation $\ast$ on a set $S$ is associative if $a\ast (b\ast c)=(a\ast b)\ast c$ for all $a,b,c\in S$.

💡 A monoid is an algebra $⟨M;\ast ,e⟩$ where $\ast$ is associative and $e$ is the neutral element.

💡 A left [right] inverse element of an element $a$ in an algebra $⟨S;\ast ,e⟩$ with neutral element $e$ is an element $b\in S$ such that $b\ast a=e$ [$a\ast b=e$]. If $b\ast a=a\ast b=e$, then $b$ is simply called an inverse of $a$.

📌 In a monoid $⟨M;\ast ,e⟩$, if $a\in M$ has a left and a right inverse, then they are equal. In particular, $a$ has at most one inverse.

💡 A group is an algebra $⟨G;\ast ,\hat{},e⟩$ satisfying the following axioms:

1. $\ast$ is associative.
2. $e$ is a neutral element: $a\ast e=e\ast a=a$ for all $a\in G$.
3. Every $a\in G$ has an inverse element $\hat{a}$, i.e., $a\ast \hat{a}=\hat{a}\ast a=e$.

💡 A group $⟨G;\ast ⟩$ (or monoid) is called commutative or abelian if $a\ast b=b\ast a$ for all $a,b\in G$.

📌 For a group $⟨G;\ast ,\hat{},e⟩$, we have for all $a,b,c\in G$:

1. $\widehat{(\hat{a})}=a$.
2. $\widehat{a\ast b}=\hat{b}\ast \hat{a}$.
3. Left cancellation law: $a\ast b=a\ast c⟹b=c$.
4. Right cancellation law: $b\ast a=c\ast a⟹b=c$.
5. The equation $a\ast x=b$ has a unique solution $x$ for any $a$ and $b$, So does the equation $x\ast a=b$.

💡 The direct product of $n$ groups $⟨G_1;{\ast }_1⟩,\dots ,⟨G_n;{\ast }_n⟩$ is the algebra

$$⟨G_1\times \dots \times G_n;\star ⟩,$$

where the operation $\star$ is component-wise:

$$(a_1,\dots ,a_n)\star (b_1,\dots ,b_n)=(a_1{\ast }_1{b}_1,\dots ,a_n{\ast }_n{b}_n).$$

📌 $\ast ⟨G_1\times \dots \times G_n;\star ⟩$ is a group, where the neutral element and the inversion operation are component-wise in the respective groups.*

💡 For two groups $⟨G;\ast ,\hat{},e⟩$ and $⟨H;\star ,\stackrel{~}{},e^{\prime }⟩$, a function $\psi :G⟶H$ is called a group homomorphism if, for all $a$ and $b$,

$$\psi (a\ast b)=\psi (a)\star \psi (b).$$

If $\psi$ is a bijection from $G$ to $H$, then it is called an isomorphism, and we say that $G$ and $H$ are isomorphic and write $G\simeq H$.

📌 A group homomorphism $\psi$ from $⟨G;\ast ,\hat{},e⟩$ to $⟨H;\star ,\stackrel{~}{},e^{\prime }⟩$ satisfies

1. $\psi (e)=e^{\prime }$
2. $\ast \psi (\hat{a})=\widetilde{\psi (a)}$ for all $a$.*

💡 A subset $H\subseteq G$ of a group $⟨G;\ast ,\hat{},e⟩$ is called a subgroup of $G$ if $⟨H;\star ,\stackrel{~}{},e^{\prime }⟩$ is a group, i.e., if $H$ is closed with respect to all operations:

1. $a\ast b\in H$ for all $a,b\in H$
2. $e\in H$
3. $\hat{a}\in H$ for all $a\in H$.

💡 Let $G$ be a group and let $a$ be an element of $G$. The order of $a$, denoted $\text{ord}(a)$, is the least $m\ge 1$ such that $a^m=e$, if such an $m$ exists, and $\text{ord}(a)$ is said to be infinite otherwise, written $\text{ord}(a)=\infty$.

📌 In a finite group $G$, every element has a finite order.

💡 For a finite group $G$, $|G|$ is called the order of $G$.

💡 If $G$ is a group and $a\in G$ has finite order, then for any $m\in \mathbb{Z}$ we have

$$a^m=a^{R_{\text{ord}(a)}(m)}.$$

💡 For a group $G$ and $a\in G$, the group generated by $a$, denoted $⟨a⟩$, is defined as

$$⟨a⟩\stackrel{\mathrm{def}}{=}\{a^n|n\in \mathbb{Z}\}.$$

It is easy to see that $⟨a⟩$ is a group, actually the smallest subgroup of a group $G$ containing the element $a\in G$. For finite groups we have

$$⟨a⟩\stackrel{\mathrm{def}}{=}\{e,a,a^2,\dots ,a^{\text{ord}(a)-1}\}.$$

💡 A group $G=⟨g⟩$ generated by an element $g\in G$ is called cyclic, and $g$ is called a generator of $G$.

💡 Being cyclic is a special property of a group. Not all groups are cyclic. A cyclic group can have many generators. In particular, if $g$ is a generator, then so is $g^{-1}$. Caution: not every element of a cyclic group has to be a generator.

For a finite group $G$, an element $g\in G$ is a generator if and only if $\text{ord}(g)=|G|$.

📖 A cyclic group of order $n$ is isomorphic to $⟨{\mathbb{Z}}_n;\oplus ⟩$ (and hence abelian).

💡 In $⟨{\mathbb{Z}}_n;\oplus ⟩$ the set of generators is given by $S=\{g\in {\mathbb{Z}}_n|\text{gcd}(g,n)=1\}$.

💡 Let $G$ and $H$ be isomorphic cyclic groups. An isomorphism $\psi :G⟶H$ maps generators to generators. Let $\mathcal{G}$ denote the set of generators of $G$. Then the set $\mathcal{H}$ of generators of $H$ is given by

$$\mathcal{H}=\{\psi (g)|g\in \mathcal{G}\}.$$

📖 Lagrange’s Theorem: Let $G$ be a finite group and let $H$ be a subgroup of $G$. Then the order of $H$ divides the order of $G$, i.e., $|H|$ divides $|G|$.

📎 For a finite group $G$, the order of every element divides the group order, i.e., $\text{ord}(a)$ divides $|G|$ for every $a\in G$.

📎 Let $G$ be a finite group. Then $a^{|G|}=e$ for every $a\in G$.

📎 Every group of prime order is cyclic, and in such a group every element except the neutral element is a generator.

💡 ${\mathbb{Z}}_m^{\ast }\stackrel{\mathrm{def}}{=}\{a\in {\mathbb{Z}}_m|\text{gcd}(a,m)=1\}$.

💡 The Euler function $\phi :{\mathbb{Z}}^{+}⟶\mathbb{Z}$ is defined as the cardinality of ${\mathbb{Z}}_m^{\ast }$ (known as Euler’s totient function or Euler’s phi function):

$$\phi (m)=|{\mathbb{Z}}_m^{\ast }|.$$

📌 If the prime factorization of $m$ is $m={\prod }_{i=1}^r{p}_i^{e_i}$, then

$$\phi (m)=\prod _{i=1}^r(p_i-1)p_i^{e_i-1}.$$

📖 $\ast ⟨{\mathbb{Z}}_m^{\ast },\odot {,}^{-1},1⟩$ is a group.*

📎 Fermat, Euler: For all $m\ge 2$ and all $a$ with $\text{gcd}(a,m)=1$,

$$a^{\phi (m)}{\equiv }_{m}1.$$

In particular, for every prime $p$ and every $a$ not divisible by $p$,

$$a^{p-1}{\equiv }_{p}1.$$

📖 The group ${\mathbb{Z}}_m^{\ast }$ is cyclic if and only if $m=2$, $m=4$, $m=p^e$, or $m=2p^e$, where $p$ is an odd prime and $e\ge 1$.

📖 $e$-th Roots in a Group: Let $G$ be some finite group (multiplicatively written), and let $e\in \mathbb{Z}$ be relatively prime to $|G|$ (i.e., $\text{gcd}(e,|G|)=1$). The function $x⟼x^e$ is a bijection and the (unique) $e$-th root of $y\in G$, namely $x\in G$ satisfying $x^e=y$, is

$$x=y^d$$

where $d$ is the multiplicative inverse of $e$ modulo $|G|$, i.e.,

$$ed{\equiv }_{|G|}1.$$

💡 A ring $⟨R;+,-,0,\cdot ,1⟩$ is an algebra for which

1. $⟨R;+,-,0⟩$ is a commutative group.
2. $⟨R;\cdot ,1⟩$ is a monoid
3. $a(b+c)=(ab)+(ac)$ and $(b+c)a=(ba)+(ca)$ for all $a,b,c\in R$ (left and right distributive laws).

A ring is called commutative if multiplication is commutative ($ab=ba$).

📌 For any ring $⟨R;+,-,0,\cdot ,1⟩$, and for all $a,b\in R$,

1. $0a=a0=0$.
2. $(-a)b=-(ab)$.
3. $(-a)(-b)=ab$.
4. If $R$ is non-trivial (i.e., if it has more than one element), then $1\ne 0$.

💡 The characteristic of a ring is the order of 1 in the additive group if it is finite, and otherwise the characteristic is defined to be 0 (not infinite).

💡 For $a,b\in R$ with $a\ne 0$ we say that $a$ divides $b$, denoted $a|b$, if there exists $c\in R$ such that $b=ac$. In this case, $a$ is called a divisor of $b$ and $b$ is called a multiple of $a$.

📌 In any commutative ring,

1. If $a|b$ and $b|c$, then $a|c$, i.e., the relation $|$ is transitive.
2. If $a|b$, then $a|bc$ for all $c$.
3. If $a|b$ and $a|c$, then $a|(b+c)$.

💡 For ring elements $a$ and $b$ (not both 0), a ring element $d$ is called a greatest common divisor of $a$ and $b$ if $d$ divides both $a$ and $b$ and if every common divisor of $a$ and $b$ divides $d$, i.e., if

$$d|a\wedge d|b\wedge \forall c((c|a\wedge c|b)\to c|d).$$

💡 An element $u$ of a (commutative) ring $R$ is called a unit if $u$ is invertible, i.e., $uv=vu=1$ for some $v\in R$. (we write $v=u^{-1}$.) The set of units of $R$ is denoted by $R^{\ast }$.

📌 For a ring $R$, $R^{\ast }$ is a multiplicative group (the group of units of $R$).

💡 An element $a\ne 0$ of a commutative ring $R$ is called a zerodivisor if $ab=0$ for some $b\ne 0$ in $R$.

💡 An integral domain is a (nontrivial) commutative ring without zerodivisors: $\forall a\forall b(ab=0\to a=0\vee b=0)$.

📌 In an integral domain, if $a|b$, then $c$ with $b=ac$ is unique (and is denoted by $c=\frac{b}{a}$ or $c=b/a$ and called quotient).

💡 A polynomial $a(x)$ over a ring $R$ in the indeterminate $x$ is a formal expression of the form

$$a(x)=a_d{x}^d+a_{d-1}{x}^{d-1}+\dots +a_{1}x+a_0=\sum _{i=0}^d{a}_i{x}^i.$$

for some non-negative integer $d$, with $a_i\in R$. The degree of $a(x)$, denoted $\text{deg}(a(x))$, is the greatest $i$ for which $a_i\ne 0$. The special polynomial 0 (i.e., all the $a_i$ are 0) is defined to have degree “minus infinity”. Let $R[x]$ denote the set of polynomials (in $x$) over $R$.

📖 For any ring $R$, $R[x]$ is a ring.

📌 1. *If $D$ is an integral domain, then so is $D[x]$.

1. The units of $D[x]$ are the constant polynomials that are units of $D$: $D[x{]}^{\ast }=D^{\ast }$.*

💡 A field is a nontrivial commutative ring $F$ in which every nonzero element is a unit, i.e., $F^{\ast }=F\setminus \{0\}$ (in other words, $⟨F\setminus \{0\};\cdot {,}^{-1},1⟩$ is an abelian group).

📖 $\ast {\mathbb{Z}}_p$ is a field if and only if $p$ is prime.*

💡 In the following we denote the field with $p$ elements by $\text{GF}(p)$ rather than ${\mathbb{Z}}_p$. “GF” stands for Galois Field.

📖 A field is an integral domain.

💡 A polynomial $a(x)\in F[x]$ is called monic if the leading coefficient is 1.

💡 A polynomial $a(x)\in F[x]$ with a degree at least 1 is called irreducible if it is divisible only by constant polynomials and by constant multiples of $a(x)$.

💡 The monic polynomial $g(x)$ of largest degree such that $g(x)|a(x)$ and $g(x)|b(x)$ is called the greatest common divisor of $a(x)$ and $b(x)$, denoted $\text{gcd}(a(x),b(x))$.

📖 Let $F$ be a field. For any $a(x)$ and $b(x)\ne 0$ in $F[x]$ there exist a unique $q(x)$ (the quotient) and a unique $r(x)$ (the remainder) such that

$$a(x)=b(x)\cdot q(x)+r(x)\text{and}\text{deg}(r(x))<\text{deg}(b(x)).$$

💡 In an integral domain, $a$ and $b$ are called associates, denoted $a\sim b$, if $a=ub$ for some unit $u$.

💡 In an integral domain, a non-unit $p\in D\setminus \{0\}$ is irreducible if, whenever $p=ab$, then either $a$ or $b$ is a unit.

📌 $a\sim b⟺a|b\wedge b|a$.

💡 A Euclidean domain is an integral domain $D$ together with a so-called degree function $d:D\setminus \{0\}⟶\mathbb{N}$ such that

1. For every $a$ and $b\ne 0$ in $D$ there exist $q$ and $r$ such that $a=bq+r$ and $d(r)<d(b)$ or $r=0$.
2. For all nonzero $a$ and $b$ in $D$, $d(a)\le d(ab)$.

📖 In a Euclidean domain every element can be factored uniquely (up to taking associates) into irreducible elements.

💡 Let $a(x)\in R[x]$. An element $\alpha \in R$ for which $a(\alpha )=0$ is called a root of $a(x)$.

📌 For a field $F$, $\alpha \in F$ is a root of $a(x)$ if and only if $x-\alpha$ divides $a(x)$.

📎 A polynomial $a(x)$ of degree 2 or 3 over a field $F$ is irreducible if and only if it has no root.

💡 If $\alpha$ is a root of $a(x)$, then its multiplicity is the highest power of $x-\alpha$ dividing $a(x)$.

📖 For a field $F$, a nonzero polynomial $a(x)\in F[x]$ of degree $d$ has at most $d$ roots, counting multiplicities.

📌 A polynomial $a(x)\in F[x]$ of degree at most $d$ is uniquely determined by any $d+1$ values of $a(x)$, i.e., by $a({\alpha }_1),\dots ,a({\alpha }_{d+1})$ for any distinct ${\alpha }_1,\dots ,{\alpha }_{d+1}\in F$.

📌 Congruence modulo $m(x)$ is an equivalence relation on $F[x]$, and each equivalence class has a unique representative of degree less than $\text{deg}(m(x))$.

💡 Let $m(x)$ be a polynomial of degree $d$ over $F$. Then

$$F[x{]}_{m(x)}\stackrel{\mathrm{def}}{=}\{a(x)\in F[x]|\text{deg}(a(x))<d\}.$$

📌 Let $F$ be a finite field with $q$ elements and let $m(x)$ be a polynomial of degree $d$ over $F$. Then $|F[x{]}_{m(x)}|=q^d$.

📌 $\ast F[x{]}_{m(x)}$ is a ring with respect to addition and multiplication modulo $m(x)$.*

📌 The congruence equation

$$a(x)b(x){\equiv }_{m(x)}1$$

(for a given $a(x)$) has a solution $b(x)\in F[x{]}_{m(x)}$ if and only if $\text{gcd}(a(x),m(x))=1$. The solution is unique. In other words,

$$F[x{]}_{m(x)}^{\ast }=\{a(x)\in F[x{]}_{m(x)}|\text{gcd}(a(x),m(x))=1\}.$$

📖 The ring $F[x{]}_{m(x)}$ is a field if and only if $m(x)$ is irreducible.

📖 For every prime $p$ and every $d\ge 1$ there exists an irreducible polynomial of degree $d$ in $\text{GF}(p)[x]$. In particular, there exists a finite field with $p^d$ elements.

📖 There exists a finite field with $q$ elements if and only if $q$ is a power of a prime. Moreover, any two finite fields of the same size $q$ are isomorphic.

📖 The multiplicative group of every finite field $\text{GF}(q)$ is cyclic.