Field

Field is a Set# $S$, together with two operations $+$ and $*$, which has the following properties including those in #Group, #Abelian Group, #Ring, #Communicative Ring, and #Integral Domain:

Multiplicative inverse, which means If $a \in S$ and $a \not = 0$, $\exist a^{-1} \in S, aa^{-1} = a^{-1}a = 1$

In Modular Arithmetic#, the find the multiplicative inverse of a number $a$ is by the equation, where $a$ is relatively prime to $n$:

$$ \begin{align} a * x &\equiv 1 (\mod n) \text{ , or} \\ ax + bn &= 1 \end{align} $$

From here, we could also know that:

$$ a \equiv x^{-1} (\mod n) $$

Thus found the inverse of $a$ in modular sense. To do that, we utilises the Euclidean Algorithm# and extends its steps on $a \mod n$ as follows:

Do one round of Euclidean Algorithm on the modulo.
Apply the properties $a = qn + b$, transform it to $b = a - qn$.
If $b$ is 0, we can conclude that $a$ is not relatively prime to $n$, which means there is no solution for it. Otherwise, continue.
If $b$ is 1, substitutes accordingly using the equations generated in step 2.
Utilise the property where $n \mod n = 0$, produce an equation resembles $1 = a * x (\mod n)$.
Reconstruct the equation to $a^{-1} = x (\mod n)$ which is identical to $a = x^{-1} (\mod n)$, thus found the solution.

Note: If $n$ is a prime number, then every number from $1$ to $n - 1$ is relatively prime to $n$ and has an exactly one inverse modulo $n$ in the range.

Note: We could check the answer by determining whether $xa^{-1} \mod n = 1$. If yes, then the answer is correct.

Or we could instead use multiplicative table# or trial and error by using the formulae $a^{-1} \times x = 1 \mod 5$ to find out the answer.

Links to this page

Greatest Common Divisor (GCD)

To find $GCD(a, b)$, one could use Euclidean Algorithm# using the theorem $GCD(a, b) = GCD(b, a \mod b); a > b$ to find the largest #Divisor that could divide both $a$ and $b$. If the GCD between the two numbers is 1, then we could say that $a$ and $b$ are relatively prime to each other and a multiplicative inverse# could be found. There are several rules to know:
Galois Field

Galois Field is a finite #Field, meaning it contains a finite number of elements which mathematical operations are defined and satisfy certain basic rules. We can do addition, subtraction, multiplication, and division without leaving the field. The total number of elements in Galois Field must be $p^n$ where $p$ is a prime number. It is denoted as $GF(p^n)$.

Note: Notice the #multiplicative inverse nature of the Galois Field.

Note: The #inverse of the $a$ could be found in the table by finding the matched row or column with value 1. For example, in the column $4$, the value 1 appear in the row $2$, thus $2$ is the inverse of $4$ in modulo 7.
El Gamal Encryption

To decrypt, apply the formula $M = c_2/c_1^x \mod p = c_2 (c_1^x)^{-1} \mod p$ or $M = c_2 c_1^{p-1-x} \mod p$ to avoid the calculation of multiplicative inverse#.
Chinese Remainder Theorem (CRT)

List a set of linear congruences using $M_i b_i = 1 (\mod m_i) \rightarrow r_i b_i$ where $r_i$ is $M_i \mod m_i$ and find out the inverse# $r_i^{-1}$ which is $b_i$ at the same time
Algebraic Structure

Field#