Written by Luka Kerr on August 2, 2019

Natural Numbers & Integers

$\mathbb{N} = \{ 0, 1, 2, 3, \cdots \} =$ set of natural numbers

$\mathbb{Z} = \{ \cdots, -2, -1, 0, 1, 2, \cdots \} =$ set of integers

$\mathbb{Z^+} = \{ 1, 2, 3, \cdots \} =$ set of positive integers

$\mathbb{Q} = \{ \frac{a}{b} : a, b \in \mathbb{Z}, b \ne 0 \} =$ set of rational numbers

$\mathbb{R} =$ set of real numbers

$\mathbb{C} =$ set of complex numbers

These are related by the inclusions $\mathbb{Z^+} \subseteq \mathbb{N} \subseteq \mathbb{Z} \subseteq \mathbb{Q} \subseteq \mathbb{R} \subseteq \mathbb{C}$.

Commutative Ring

A commutative ring is a non-empty set $R$ with a method of adding ($+$) and multiplying ($\bullet$) elements of $R$, such that, for all $a, b, c \in R$.

  1. $a + b, a \bullet b \in R$ (Closure)
  2. $(a + b) + c = a + (b + c), (a \bullet b) \bullet c = a \bullet (b \bullet c)$ (Associative law)
  3. $a \bullet (b + c) = a \bullet b + a \bullet c$ (Distributive law)
  4. $a + b = b + a, a \bullet b = b \bullet a$ (Commutative law)
  5. There is an element $0 \in R$ with the property that $0 + a = a$
  6. $a + x = 0$ for some $x \in R$ ($x$ is called the negative of $a$)

Field

A commutative ring $\mathbb{F}$ with a $1$, in which every non-zero element has a multiplicative inverse which lies in $\mathbb{F}$ is called a field.

Divisibility

If $a \in \mathbb{N}$ and $b \in \mathbb{Z^+}$ then there exists unique $q, r \in \mathbb{Z}$ such that $a = bq + r$ and $0 \le r < b$.

In general, if $a, b \in \mathbb{Z}$ with $b \ne 0$, then there are unique $q, r \in \mathbb{Z}$ such that $a = bq + r$ and $0 \le r < |b|$.

For $a, b \in \mathbb{Z}$ with $b \ne 0$, if $a$ mod $b = 0$, we say $b$ divides a, or

Let $a \mid b$ denote that $a$ divides $b$, and $a \nmid b$ denote that $a$ does not divide $b$. Then

Greatest Common Divisor

For $a, b \in \mathbb{Z}$, not both zero, the positive integer $d$ such that

  1. $d \mid a$ and $d \mid b$
  2. If $c \mid a$ and $c \mid d$ then $c \le d$, or if $c \mid a$ and $c \mid b$ then $c \mid d$

is called the greatest common divisor of $a$ and $b$, and is written as $d = gcd(a, b)$.

Properties include:

The Euclidean Algorithm

For integers $a \ge b > 0$, we apply the division algorithm repeatedly beginning with $r_0 = a$ and $r_1 = b$ to obtain:

\[\begin{array}{lcl} r_0 = r_1 q_1 + r_2, & & 0 \le r_2 < r_1, \\ r_1 = r_2 q_2 + r_3, & & 0 \le r_3 < r_2, \\ r_2 = r_3 q_3 + r_4, & & 0 \le r_4 < r_3, \\ & \vdots \\ r_{n - 2} = r_{n - 1} q_{n - 1} + r_n, & & 0 \le r_n < r_{n - 1}, \\ r_{n - 1} = r_n q_n + 0 \end{array}\]

Note that if $a$ or $b$ is negative, simply use the Euclidean Algorithm on $|a|$ and $|b|$, and adjust signs at the end.

Eventually, a remainder of zero occurs in the sequence of successive divisions, since the sequence of remainders $a = r_0 > r_1 > r_1 > \cdots \ge 0$ cannot contain more than $a$ terms.

Furthermore, it follows that

\[\begin{array}{lcl} gcd(a, b) & = & gcd(r_0, r_1) = gcd(r_1, r_2) = \cdots \\ & = & gcd(r_{n - 2}, r_{n - 1}) \\ & = & gcd(r_{n - 1}, r_n) \\ & = & gcd(r_n, 0) \\ & = & r_n \end{array}\]

Bezout’s Identity

For $a, b \in \mathbb{Z}$, not both zero, there exists integers $x$ and $y$ such that $gcd(a, b) = xa + yb$.

Prime Numbers

A positive integer $p \ne 1$ is called a prime if its only factors are $\pm 1$ and $\pm p$, that is $x \mid p$ implies $x = \pm 1$ or $x = \pm p$.

A positive integer $n \ne 1$ that is not a prime is called a composite.

An important property of primes is that if $p \mid ab$, where $p$ is prime and $a, b \in \mathbb{Z}$, then $p \mid a$ or $p \mid b$.

Coprime Numbers

Two integers $a, b \in \mathbb{Z}$, are said to be coprime or relatively prime if the only positive factor that divides both of them is 1. That is, $gcd(a, b) = gcd(b, a) = 1$.

Fundamental Theorem Of Arithmetic

Every positive integer $n \ne 1$ can be written uniquely as a product of primes in increasing size, i.e. $n = p_1^{m_1} p_2^{m_2} \cdots p_k^{m_k}$, for primes $p_1 < p_2 < \cdots < p_k$, and exponents $m_1, m_2, \cdots, m_k \in \mathbb{Z^+}$.

Representation of Numbers

Base $b$ Representations

Fix $b \in \mathbb{N}$ and $b \ge 2$.

Base $b$ Digit Algorithm

For the integer part of some number $x$, we can convert to base $b$ using repeated application of the division algorithm. Let $a = \lfloor x \rfloor$.

\[\begin{array}{lcl} a = q_1 b + a_0, & & 0 \le a_0 < b, \\ q_1 = q_2 b + a_1, & & 0 \le a_1 < b, \\ q_2 = q_3 b + a_2, & & 0 \le a_2 < b, \\ & \vdots \\ q_{n - 1} = q_n b + a_{n - 1}, & & 0 \le a_{n - 1} < b, \\ q_n = 0b + a_n, & & 0 \le a_n < b \end{array}\]

For the fraction part of $x$, repeatedly apply the floor function. Let $y = x - \lfloor x \rfloor$.

\[\begin{array}{lcl} a_{-1} & = & \lfloor by \rfloor \\ a_{-2} & = & \lfloor b (by - a_{-1}) \rfloor \\ a_{-3} & = & \lfloor b (b (by - a_{-1}) - a_{-2}) \rfloor \\ & \vdots \end{array}\]

Greatest Common Divisor In Binary

Let $m$, $n$ be positive:

Continued Fractions

Continued fractions is a method of representing real numbers more accurately than decimals, and exact for rational numbers.

A continued fraction represented by $a_0 + \dfrac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3}}}$ is denoted by $[ a_0; a_1, a_2, a_3 ]$. The numbers $a_1, a_2, a_3$ are referred to as the partial quotients.

Continued Fraction Algorithm

Associated to $x \in \mathbb{R}$, we construct a sequence $a_0; a_1, a_2, a_3, \cdots$, where

\[\begin{array}{lcl} x = a_0 + \xi_0, & & 0 \le \xi_0 < 1 \\ \frac{1}{\xi_0} = a_1 + \xi_1, & & 0 \le \xi_1 < 1 \\ \frac{1}{\xi_1} = a_2 + \xi_2, & & 0 \le \xi_2 < 1 \\ \frac{1}{\xi_2} = a_3 + \xi_3, & & 0 \le \xi_3 < 1 \\ & \vdots \end{array}\]

If $\xi_n = 0$ for some $n$, then the sequence is terminating and $x$ is rational.

In general, for each $x \in \mathbb{R}$, there are $a_0 \in \mathbb{Z}$ and $a_1, a_2, \cdots \in \mathbb{N}$ such that

\[x = \lim_{n \to \infty} x_n\]

where

\[x_n = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \underset{+ \frac{1}{a_n}}{\cdots}}}}\]

Error Measurement

Continued fractions are the best approximations to real numbers in the sense that if

\[\begin{array}{lcccl} \theta & = & & & [a_0; a_1, a_2, \cdots] \\ c_n & = & \dfrac{p_n}{q_n} & = & [a_0; a_1, a_2, \cdots, a_n] \end{array}\]

then for every rational number $a / b$ with $b < q_n$

\[\left | \theta - \dfrac{p_n}{q_n} \right | < \left | \theta - \dfrac{a}{b} \right |\]

Modular Arithmetic

Congruence Relation

Suppose $n \in \mathbb{Z^+}$. We say that integers $a$ and $b$ are congruent modulo $n$, and write $a \equiv b \ (\text{mod} \ n)$, if $a \ \text{mod} \ n = b \ \text{mod} \ n$.

Suppose $a \equiv b \ \text{mod} \ n$ and $c \equiv d \ \text{mod} \ n$. Then

Integers Modulo $n$

A relation $\sim$ on a set $X$ is called an equivalence relation for all $x, y, x \in X$, $x \sim x, x \sim y \implies y \sim x, x \sim y, y \sim z \implies x \sim z$.

An equivalence relation partitions a set into equivalence classes. Thus, if $a \in X$ then the equivalence class of $a$, written $[a]$ is the set of all elements in $X$ that are equivalent to $a$.

$\mathbb{Z}$ is partitioned into equivalence classes $\{ [a] : 0 \le a < n \}$. Here we label the class by the residue mod $n$.

For $a, b \in \mathbb{Z}_n$, we define $a + b$ to be the number $x \in \mathbb{Z}_n$ with $a + b \equiv c \ (\text{mod} \ n)$, and $ab$ the number $d \in \mathbb{Z}_n$, with $ab \equiv d \ (\text{mod} \ n)$.

In other words,

\[\begin{array}{rcl} a + b & = & (a + b) \ \text{mod} \ n \\ ab & = & ab \ \text{mod} \ n \end{array}\]

Inverses In $\mathbb{Z}$

In general, if $ab \equiv ac \ (\text{mod} \ n)$, you cannot conclude that $b \equiv c \ (\text{mod} \ n)$.

However, if the inverse of $a \in \mathbb{Z}_n$ exists (denoted by $a^{-1} \ (\text{mod} \ n)$), that is, $\exists a’ : a’a = aa’ = 1$ or $aa’ \equiv 1 \ (\text{mod} \ n)$, then

\[ab = ac \in \mathbb{Z}_n \implies a'ab = a'ac \in \mathbb{Z}_n\]

and so $b = c \in \mathbb{Z}_n$.

A non-zero $a \in \mathbb{Z}_n$ has an inverse iff $gcd(a, n) = 1$.

By evaluating the Extended Euclidean Algorithm for $gcd(a, n)$ consisting of columns $(q_n, r_i, s_i, t_i)$, an inverse $a’$ can be found such that $a’(ax) \equiv b \ (\text{mod} \ n)$, where $a’$ is the 2nd last row of $t_i$.

Groups

Let $G$ be a non-empty set whose elements satisfy the following five rules:

This set is called a commutative or Abelian group.

Tests For Divisibility

Solving Linear Equations

Linear Congruence Equations

A linear congruence problem may be phrased as follows:

If $a, b$ and $n$ are integers, can we find an integer $x$ such that

\[ax \equiv b \ (\text{mod} \ n) \text{?} \qquad (*)\]

If $x$ does satisfy this congruence, then all integers of the form $x + kn$ are also solutions. But, among them there is only one in $\mathbb{Z}_n$.

What we want to know is: how many mutually incongruent solutions of the congruence (*) are there? That is, how many solutions of the equation $ax = b$ are there in $\mathbb{Z}_n$?

Suppose $n$ is a positive integer and $d = gcd(a, n)$. Then the equation $ax \equiv b \ (\text{mod} \ n)$ has a solution iff $d \mid b$. That is, $ax = b$ in $\mathbb{Z}_n$ is solvable iff $d \mid b$.

Linear Diophantine Equations

A diophantine equation is an equation where we seek only integer solutions.

Suppose $a, b, c$ etc are integers. If there is one unknown, thus $ax = b$, then an integer solution exists iff $a \mid b$.

Suppose then that there are two unknowns, thus we seek to solve $ax + by = c$, for given $a, b, c \in \mathbb{Z}$. This equation has a solution in $\mathbb{Z}$ iff $d \mid c$, where $d = gcd(a, b)$.

The Chinese Remainder Theorem

Suppose $n_1, n_2, \dots, n_k \in \mathbb{N}$ with $gcd(n_i, n_j) = 1$ for each $i, j$ with $1 \le i < j < k$. Then there is a unique solution modulo $n = n_1 n_2 \dots n_k$ to the simultaneous equations

\[\begin{array}{lcl} x & \equiv & a_1 \ (\text{mod} \ n_1) \\ x & \equiv & a_2 \ (\text{mod} \ n_2) \\ & \vdots & \\ x & \equiv & a_k \ (\text{mod} \ n_k) \end{array}\]

Powers & Roots

For $a \in \mathbb{Z}_n$, we want to see if $x^2 \equiv a \ (\text{mod} \ n)$ has a solution. If so, $a$ is called a quadratic residue mod $n$. Otherwise it is called a quadratic non-residue mod $n$.

Fermat’s Little Theorem

Suppose $p$ is a prime number. Any integer $a$ satisfies $a^p \equiv a \ (\text{mod} \ p)$, and any integer $a$ not divisible by $p$ satisfies $a^{p - 1} \equiv 1 \ (\text{mod} \ p)$.

Note that for $p$ prime, if $gcd(n, p - 1) = 1$, $x^n \equiv a \ (\text{mod} \ p)$ has a solution for all $a$.

Euler’s Phi Function

For any integer $n$, $\mathbb{Z}^\ast_n$ consists of all invertible elements in $\mathbb{Z}_n$. $\mathbb{Z}^\ast_n$ can be defined as $\mathbb{Z}^\ast_n = \{ a : 0 \le a < n, gcd(a, n) = 1 \}$, that is, the set containing all integers between $1$ and $n$ that are coprime to $n$.

If $n = p$ is prime then $\mathbb{Z}^\ast_n \ \{ 1, 2, \dots, p - 1 \}$.

We define Euler’s $\phi$-function by

\[\begin{array}{lcl} \phi(n) & = & \left | \{ a : 0 \le a < n, gcd(a, n) = 1 \} \right | \\ & = & \left | \mathbb{Z}^\ast_n \right | \end{array}\]

for all $n \in \mathbb{Z}^+$.

Some properties for Euler’s $\phi$-function are

  1. $\phi(p^m) = p^{m - 1}(p - 1) = p^m(1 - \frac{1}{p})$
  2. If $gcd(m, n) = 1$ then $\phi(mn) = \phi(m) \phi(n)$
  3. For distinct primes $p, q$, $\phi(pq) = (p - 1)(q - 1)$
  4. Let $p_1, \dots, p_r$ be the distinct prime factors of $n$, then $\phi(n) = n \prod^r_{i = 1} (1 - \frac{1}{p_i})$

Euler Generalisation Of Fermat’s Little Theorem

For $a \in \mathbb{Z}$ and $n \in \mathbb{Z}^+$, if $gcd(a, n) = 1$, then $a^{\phi(n)} \equiv 1 \ (\text{mod} \ n)$. Equivalently, for each $x \in \mathbb{Z}^\ast_n$, $x^{\phi(n)} = 1$ (in $\mathbb{Z}^\ast_n$).

Orders & Primitive Elements

The order of an element $a \in \mathbb{Z}^\ast_n$ is the smallest positive integer $o_n(a) = o_{\mathbb{Z}^\ast_n}(a)$ such that $a^{o_n(a)} = 1$ (in $\mathbb{Z}^\ast_n$). That is, $a^{o_n(a)} \equiv 1 \ (\text{mod} \ n)$.

We will also write $o_n(a)$ as $|a|$ where the context will supply the appropriate value of $n$.

If $|a| = |\mathbb{Z}^\ast_n|$, $a$ is called a primitive element (or a primitive root) mod $n$ (or of $\mathbb{Z}^\ast_n$).

Thus, if $p$ is prime, a primitive root mod $p$ has order $p - 1$ and more generally a primitive root mod $n$ (if one exists) has order $\phi(n)$.

Note that if $a$ is positive, then $\mathbb{Z}^\ast_n = \{ a, a^2, \dots, a^{o_n(a)} \}$, so that a primitive root generates the whole set.

Properties include

In general, $\mathbb{Z}_n$ has a primitive root iff $n = 1, 2, 4, p^a, 2p^a$ where $p$ is an odd prime and $a \ge 1$.

Quadratic Residues

Suppose $p$ is prime. A number $a \in \mathbb{Z}_p$ is called a square or quadratic residue if $a = b^2$ for some $b \in \mathbb{Z}_p$ and otherwise it is called a quadratic non-residue.

Since every non-zero element in $\mathbb{Z}_p$ is a power of a primitive root $g \in \mathbb{Z}_p$, every quadratic residue arises from an even power of $g$ and every quadratic non-residue arises from an odd power of $g$.

This also shows that no quadratic residue can be a primitive root. Since exactly half of the elements in $\mathbb{Z}^\ast_p$ are quadratic non-residues, there exist elements in $\mathbb{Z}_p$ that are quadratic non-residues, but not primitive roots.

Applications

Arithmetic Of Large Numbers

Primality Testing

Let $P = \{ 2, 3, 5, 7, \cdots \}$ be the set of all positive prime numbers. There are many tests for primality, that is, for deciding if a given number is a prime.

Test 1. Every composite number $n$ has a prime factor $p$, with $p \le \sqrt{n}$. Hence if $n$ has no prime factor $p \le \sqrt{n}$ then $n$ is prime.

Test 2 (Fermat’s Test). If $a^{n - 1} \not\equiv 1 \ (\text{mod} \ n)$, then $n$ is not prime. On the other hand, if $2^{n - 1} \equiv 1 \ (\text{mod} \ n)$, then there is a very high probability that $n$ is a prime.

Test 3 (Lucas’ test). A positive number $n$ is prime if there exists an integer $1 < a < n$ such that $a^{n - 1} \equiv 1 \ (\text{mod} \ n)$ and for every prime factor $p$ of $n - 1$, $a^{\frac{n - 1}{p}} \not\equiv 1 \ (\text{mod} \ n)$.

Cryptography

Let $\mathcal{P}$ be the set of all plaintext message units, and $\mathcal{C}$ the set of all ciphertext message units. A cryptosystem consists of $\mathcal{P}, \mathcal{C}$ and two functions:

$E : \mathcal{P} \to \mathcal{C}$ called the ENCODER, and

$D : \mathcal{C} \to \mathcal{P}$ called the DECODER,

with the property that $D(E(M)) = M$ for all message units $M \in \mathcal{P}$. We can represent the situation schematically by the diagram

\[\mathcal{P} \overset{E}{\to} \mathcal{C} \overset{D}{\to} \mathcal{P}.\]

If knowledge of $E$ does not allow easy determination of $D$, then the pair $(D, E)$ forms the basis of a Public Key Cryptosystem.

The functions $E$, $D$ are inverses of each other. A function which is easy to compute, but which has an inverse that, although it exists, is very hard to find, is called a trap door function

RSA Codes

Given an encoding function $E : m \to m^s \ (\text{mod} \ r)$ and a decoding function $D : m \to m^t \ (\text{mod} \ r)$, the value of $t$ can be found by evaluating the Extended Euclidean Algorithm to solve for $t$ in the congruence $ts \equiv 1 \ (\text{mod} \ \phi(r))$.

Error Correcting Codes

Parity Check Code

In a message $m$ containing 7 bits, the 8’th bit is set to the number of 1’s in $m$, that is, the parity of $m$. By checking if the parity of the received message is the same as the parity of $m$, we can check for errors and ask for retransmission if needed.

Triple Repetition Code

Each bit in an encoded message $m$ is repeated three times, such that $0 \to 000$ and $1 \to 111$. A majority vote can be used to correct errors.

Hamming $(7, 4)$ Code

Recall the set $\mathbb{Z}_2 = \{ 0, 1 \}$ and that

Let

\[H = \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{pmatrix} \quad \text{over} \ \mathbb{Z}_2.\]

The $i$’th column of this matrix is simply the number $i$ written in binary.

Encoding

Break the message into blocks of 4 bits $(a, b, c, d)$ and encode as

\[\mathbf{c} = (x, y, a, z, b, c, d)\]

where

Decoding

Let

\[\mathbf{r} = (r_1, r_2, r_3, r_4, r_5, r_6, r_7)\]

be the received message, then $\mathbf{r} = \mathbf{c} + \mathbf{e}$, where $\mathbf{e}$ is the error introduced during transmission.

To correct $r_i$ simply apply $\neg$ to $r_i$, that is, negate it.

Polynomials

A polynomial is defined as

\[f(x) = a_n x^n + \cdots + a_1 x + a_0\]

where all $a_i$ are called ‘coefficients’ and $x$ is an “indeterminate”.

Let $R[x]$ denote the set of all polynomials over $R$, and introduce for $f(x) = \sum_{i = 0}^n a_i x^i$ and $g(x) = \sum_{j = 0}^m b_j x^j$.

Arithmetic

Addition

$f(x) + g(x) = \sum_{i = 0}^{\max(n, m)} (a_i + b_i) x^i$

Multiplication

$f(x) g(x) = \sum_{r = 0}^{m + n} (\sum_{i + j = r} a_i b_j) x^r$

Note that if $R$ has zero-divisors ($0 \ne a \in R$ is called a zero divisor, if $\exists b \ne 0$ such that $ab = 0$), then $R[x]$ has zero-divisors.

Division Theorem

Let $F$ be a field. If $f(x), g(x) \in F[x]$ and $g(x)$ is a non-zero polynomial, then there are polynomials $q(x), r(x), \in F[x]$ (of unique degree) such that $f(x) = g(x) q(x) + r(x)$, where $0 \le \deg r(x) < \deg g(x)$.

If $r(x) = 0$, then we say that $g(x)$ divides $f(x)$, and write $g(x) \mid f(x)$.

Greatest Common Divisor

For $f(x), g(x) \in F[x]$, not zero, the polynomial $d(x)$ such that

  1. $d(x) \mid f(x)$ and $d(x) \mid g(x)$
  2. if $c(x) \mid f(x)$ and $c(x) \mid g(x)$ then $c(x) \mid d(x)$

is called a greatest common divisor of $f(x)$ and $g(x)$.

To find a GCD of $f(x)$ and $g(x)$, we use a polynomial version of the Euclidean Algorithm. Put $r_0(x) = f(x)$ and $r_1(x) = g(x)$ and repeatedly apply the Division Algorithm:

\[\begin{array}{rcl} r_0(x) & = & r_1(x) q_1(x) + r_2(x) \\ r_1(x) & = & r_2(x) q_2(x) + r_3(x) \\ r_2(x) & = & r_3(x) q_3(x) + r_4(x) \\ & \vdots & \\ r_{n - 2}(x) & = & r_{n - 1}(x) q_{n - 1}(x) + r_n(x) \\ r_{n - 1}(x) & = & r_n(x) q_n(x) + 0 \\ \end{array}\]

where $\deg g = \deg r_1 > \deg r_2 > \deg r_3 \cdots$. Then $d(x) = r_n(x)$.

Bezout’s Identity

Let $f(x), g(x) \in F[x]$ with $d(x) = gcd(f(x), g(x))$. Then there are polynomials $a(x), b(x) \in F[x]$ such that

\[d(x) = a(x) f(x) + b(x) g(x).\]

A polynomial is irreducible in a polynomial ring $R[x]$ it cannot be factored as the product of two polynomials of smaller degree.

Polynomial Congruences

Let $m(x) \in F[x]$ (and assume $\deg m(x) > 0$). For $f(x), g(x) \in F[x]$, we say that $f(x)$ is congruent to $g(x)$ modulo $m(x)$, and write $f(x) \equiv g(x) \ \text{mod} \ m(x) \ \text{iff} \ m(x) \mid f(x) - g(x)$.

If $f_1(x) \equiv f_2(x)(\text{mod} \ m(x))$ and $g_1(x) \equiv g_2(x)(\text{mod} \ m(x))$, then

We define

\[\begin{array}{rcl} F[x]/\langle m(x) \rangle & = & \text{set of equivalence classes} \\ & = & \{ f(x) : f(x) \in F[x] \} \\ & = & \{ f(x) \ \text{mod} \ m(x) : f(x) \in F[x] \} \end{array}\]

and introduce addition and multiplication:

$\forall r_i(x) \in F[x] / \langle m(x) \rangle,$ \(\begin{array}{rcl} \overline{r_1(x)} + \overline{r_2(x)} & := & \overline{r_1(x) + r_2(x)} \\ \\ \overline{r_1(x)} \: \overline{r_2(x)} & := & \overline{r_1(x) r_2(x)}. \end{array}\)

Let $F$ be a field.

  1. $F[x] / \langle m(x) \rangle$ is a commutative ring with identity
  2. $r(x) \in F[x] / \langle m(x) \rangle$ is invertible, iff $gcd(r(x), m(x)) = 1$
  3. $F[x] / \langle m(x) \rangle$ is a field iff $m(x)$ is irreducible

Solving Polynomial Congruences

In general, for given $a(x), b(x), m(x) \in F[x]$, let $d(x) = gcd(a(x), m(x))$ and consider the equation

\[(*) \qquad a(x) f(x) \equiv b(x) \quad (\text{mod} \ m(x)).\]
  1. The equation $(*)$ has a solution iff $d(x) \mid b(x)$
  2. If $d(x) \mid b(x)$, write $a_1(x) = a(x) / d(x), m_1(x) = m(x) \ d(x)$ and $b_1(x) = b(x) / d(x)$. Then the solutions to $(*)$ may be found by dividing $b_1(x)$ by $a_1(x)$ in $F[x] / \langle m_1(x) \rangle$: $f(x) \equiv a_1(x)^{-1} b_1(x)(\text{mod} \ m_1(x))$
  3. The equation $(*)$ has a unique solution iff $gcd(a(x), m(x)) = 1$

Chinese Remainder Theorem

Let $F$ be a field, $m_1(x), m_1(x), \dots m_k(x) \in F[x]$, with $gcd(m_i(x), m_j(x)) = 1$ for each $i, j$ with $1 \le i < j \le k$, then there is a unique solution modulo $m(x) = m_1(x) m_2(x) \dots m_k(x)$ to the simultaneous equations

\[\begin{array}{lcl} f(x) & \equiv & a_1(x) \ (\text{mod} \ m_1(x)) \\ f(x) & \equiv & a_2(x) \ (\text{mod} \ m_2(x)) \\ & \vdots & \\ f(x) & \equiv & a_k(x) \ (\text{mod} \ m_k(x)) \end{array}\]

Factorising Polynomials

Formal Derivative

For $f(x) = a_n x^n + \cdots + a_1 x + a_0$, the polynomial

\[f^{\prime}(x) = n a_n x^{n - 1} + \cdots + 2 a_2 x + a_1\]

is called the derivative of $f(x)$. The following properties hold:

  1. $(f \pm g)^{\prime} = f^{\prime} \pm g^{\prime}$
  2. $(fg)^{\prime} = f^{\prime}g + f g^{\prime}$

Let $F$ be a field and $f(x) \in F[x]$. If $u(x)$ is an irreducible factor of $f(x)$ with $u^{\prime} \ne 0$ then

\[\begin{array}{rcl} u(x)^2 \mid f(x) & \text{iff} & u(x) \mid f^{\prime}(x) \\ & \text{iff} & u(x) \mid gcd(f(x), f^{\prime}(x)) \end{array}\]

Irreducible Polynomials

The determination of irreducible polynomials depends on the field $F$.

(I) $F = \mathbb{C}$

The irreducible polynomials in $\mathbb{C}[x]$ are the linear polynomials. Therefore, every polynomial in $\mathbb{C}[x]$ can be factorised as a product of linear polynomials.

(II) $F = \mathbb{R}$

If $m(x) \in \mathbb{R}[x]$ is irreducible and monic, then $m(x) \in \mathbb{C}[x]$ and so $m(\alpha) = 0$ for some $\alpha \in \mathbb{C}$. If $\alpha$ is real, then $m(x) = x - \alpha$. Otherwise, $m(\bar{\alpha}) = 0$ and so $m(x)$ has a factor $(x - \alpha)(x - \bar{\alpha}) = x^2 - (\alpha - \bar{\alpha})x + |\alpha|^2 \in \mathbb{R}[x]$.

Therefore, $m(x) = x^2 - (\alpha + \bar{\alpha})x + |\alpha|^2$.

Every irreducible polynomial in $\mathbb{R}[x]$ is either linear or quadratic.

(III) $F = \mathbb{Q}, F = \mathbb{Z}$

A primitive polynomial is a polynomial in $\mathbb{Z}[x]$ in which the greatest common divisor of the coefficients is $1$.

Gauss’ Lemma: The product of two primitive polynomials is a primitive polynomial.

Eisenstein’s Criterion: Suppose there is a prime number $p$ which divides each coefficient $a_i$ of $f(x)$ except the leading coefficient $a_n$ and such that $p^2$ does not divide $a_0$. Then $f(x)$ is irreducible.

Cohn’s Irreducibility Criterion

Take any prime number $p$ written in decimal form as

\[p = a_n \times 10^n + \cdots + a_1 \times 10 + a_0\]

then the polynomial $f(x) = a_n x^n + \cdots + a_1 x + a_0$ is irreducible over $\mathbb{Q}$.

Finite Fields

If $m(x) \in F[x]$ is irreducible, then $F[x] / \langle m(x) \rangle$ is a field.

Characteristic Of A Field

The characteristic of a field $F$ is the smallest $n \in \mathbb{Z}^+$ such that

\[\overbrace{1 + 1 + \cdots + 1 = 0}^{n \ \text{times}}.\]

If there is no such $n$, we define the characteristic to be $0$.

If $F$ is any field of characteristic $n$, then $n$ is prime. Thus, a finite field $F$ of characteristic $p$ ($p$ necessarily prime) contains $\mathbb{Z}_p$ as a subfield.

Suppose $F$ is a finite field. Then $|F| = q = p^k$ for some prime $p$ and some positive integer $k$.

Irreducible Polynomials In $\mathbb{Z}_p[x]$

Let $F$ be a finite field containing $q = p^k$ elements, where $p$ is prime and $k > 0$. Then $x^{q - 1} = 0$ for all $x \in F^\ast$.

Every irreducible polynomial in $\mathbb{Z}_p[x]$ of degree $n$ is a factor of $x^{p^n} - x$.

Constructing All Finite Fields

Moore’s Theorem
  1. For every prime $p$ and integer $k > 0$, there is a finite field $F$ with $p^k$ elements
  2. Every finite field $F$ with $p^k$ elements is isomorphic to $\dfrac{\mathbb{Z}_p[x]}{\langle m(x) \rangle}$ for some irreducible polynomial $m(x)$

We will denote a field with $q = p^k$ elements by $GF(q)$, the Galois Field of $q$ elements.

Primitive Elements

The order of an element $\alpha \in F^\ast$ is the smallest positive power $k = O(\alpha)$ such that $a^k = 1$.

An element of order $q - 1$ in $GF(q), q = p^k$, is called a primitive element.

Let $F$ be a field with $q = p^k$ elements. Then

Suppose $\alpha$ is a primitive element of $F$ with $q = p^k$ elements and $\beta = \alpha^\ell$ is an element of $F$. Let $d = gcd(\ell, q - 1)$, then

  1. $O(\beta) = (q - 1) / d$
  2. $\beta$ is also a primitive element iff $d = 1$
  3. There are $\phi(q - 1)$ primitive elements in $F$

Minimal Polynomials

Let $F$ be a finite field extension of $\mathbb{Z}_p$ and suppose that $\beta \in F$. Then the minimal polynomial $m(x)$ for $\beta$ is the monic polynomial of smallest degree such that $m(\beta) = 0$.

Take any non-zero element $\alpha$ in $GF(p^k)$, then the minimum polynomial for $\alpha$ is given by

\[(x - \alpha)(x - \alpha^p)(x - \alpha^{p^2}) \dots\]

where the product stops before the term $\alpha^{p^k} = \alpha$.

Error Correcting Codes

Hamming $(n, n - r)$ Code

Let $r \in \mathbb{Z}$ and $n = 2^r - 1$. Then a Hamming $(n, n - r)$ code is the kernel of an $r \times n$ matrix $H$ whose columns are all the non-zero elements of the vectorspace $(\mathbb{Z}_2)^r$.

Thus, $\mathbf{c}$ is a code word iff $H \mathbf{c} = \mathbf{0}$.

General Codes

In general, if $n = 2^r - 1$, the Hamming $(n, n - r)$ code may be thought of as follows:

  1. Take the Galois Field $GF(2^r)$, which is obtained from $\dfrac{\mathbb{Z}_2[x]}{\langle m(x) \rangle}$, where $m(x)$ is an irreducible polynomial of degree $r$ in $\mathbb{Z}_2[x]$
  2. To encode the message $(c_{n - 1}, c_{n - 2}, \dots, c_r) \in \mathbb{Z}_2^{(n - r)}$, we write \(C_I(x) = c_{n - 1} x^{n - 1} + c_{n - 2} x^{n - 2} + \cdots + c_r x^r\) and send \(C(x) = (c_{n - 1} x^{n - 1} + c_{n - 2} x^{n - 2} + \cdots +c_r x^r) + (c_{r - 1} x^{r - 1} + \cdots + c_0) = C_I + D(x)\) where $D(x)$ is chosen (uniquely, since $\deg m(x) = r > \deg D(x)$), so that $m(x) \mid C(x)$

Error Detecting

Suppose that there is at most one error during transmission. If there were exactly one error in the $i$th digit, we would receive $R(x) = C(x) + x^i$.

But then $R(\alpha) = C(\alpha) + \alpha^i = \alpha^i$ and so the calculation of $R(\alpha)$ gives the position of the incorrect digit. If $R(\alpha) = 0$ then there were no errors.

Double Error Correction

Suppose we receive a message with at most two errors, i.e. $R(x) = C(x) + x^i + x^j$ (with $i \ne j$).

Then $R(\alpha) = C(\alpha) + \alpha^i + \alpha^j = \alpha^i + \alpha^j$ and $R(\alpha^3) = C(\alpha^3) + \alpha^{3i} + \alpha^{3j} = \alpha^{3i} + \alpha^{3j}$. Write $\beta_1 = \alpha^i, \beta_2 = \alpha^j$. We seek to recover $\alpha^i$ and $\alpha^j$ seperately from these equations.

Note that $\alpha^{3i} + \alpha^{3j} = \beta_1^3 + \beta_2^3 = (\beta_1 + \beta_2)(\beta_1^2 + \beta_2^2 - \beta_1 \beta_2) = (\beta_1 + \beta_2)((\beta_1 + \beta_2)^2 + \beta_1 \beta_2)$. Hence we have

\[\beta_1 + \beta_2 = R(\alpha) \quad \text{and} \quad R(\alpha^3) = R(\alpha)((R(\alpha))^2 + \beta_1 \beta_2)\]

from which we can obtain the sum and product of the $\beta$’s. We can therefore write down a quadratic whose roots are the $\beta$’s and (usually by trial and error) solve it.

In summary, assuming at most two errors, we receive $R(x)$ and if

  1. $R(\alpha) = 0$ then there were no errors
  2. $R(\alpha) = \alpha^i, R(\alpha^3) = \alpha^{3i}$ then there was one error at position corresponding to $\alpha^i$
  3. $R(\alpha^3) \ne (R(\alpha))^3$ then there were two errors and we proceed as above to locate them