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 nonempty set $R$ with a method of adding ($+$) and multiplying ($\bullet$) elements of $R$, such that, for all $a, b, c \in R$.
 $a + b, a \bullet b \in R$ (Closure)
 $(a + b) + c = a + (b + c), (a \bullet b) \bullet c = a \bullet (b \bullet c)$ (Associative law)
 $a \bullet (b + c) = a \bullet b + a \bullet c$ (Distributive law)
 $a + b = b + a, a \bullet b = b \bullet a$ (Commutative law)
 There is an element $0 \in R$ with the property that $0 + a = a$
 $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 nonzero 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
 $b$ is a divisor of $a$
 $b$ is a factor of $a$
 $a$ is a multiple of $b$
 $a$ is divisible by $b$
 $a = kb$ for some integer $k$
Let $a \mid b$ denote that $a$ divides $b$, and $a \nmid b$ denote that $a$ does not divide $b$. Then
 $a \mid 0$ for any nonzero $a \in \mathbb{Z}$
 If $a \mid b$ and $a \mid c$ then $a \mid b \pm c$
 If $a \mid b$ and $b \mid c$ then $a \mid c$
Greatest Common Divisor
For $a, b \in \mathbb{Z}$, not both zero, the positive integer $d$ such that
 $d \mid a$ and $d \mid b$
 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:
 $gcd(a, b)$ exists and is unique
 $gcd(a, b)$ is not affected by the signs of $a$ and $b$
 For $a \in \mathbb{Z^+}$, $gcd(a, 0) = a$
 If $a = bq + c$ where $a, b, c, q \in \mathbb{Z}$ then $gcd(a, b) = gcd(b, c)$
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$.

Every integer $a \in \mathbb{N}$ can be uniquely written as $a = a_n b^n + a_{n  1} b^{n  1} + \cdots + a_1 b + a_0$ for some $n \in \mathbb{N}$ with $0 \le a_i < b$ for all $i = 0, 1, \cdots, n$. We write $a = (a_n a_{n  1} \cdots a_1 a_0)_b$ and call $a_i$’s base $b$ digits.

Every $x \in \mathbb{R} : (x > 0)$ can be uniquely written as $\sum^n_{j = \infty} a_j b^j$ where each $a_i$ satisfies $0 \le a_i < b$. We write $x = (a_n a_{n  1} \cdots a_1 a_0 . a_{1} a_{2} a_{3} \cdots)_b$.

$x$ is rational iff the expression $. a_{1} a_{2} a_{3} \cdots$ is eventually periodic (or terminating).
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:
 If $m$ and $n$ are both even, then $gcd(m, n) = gcd(m / 2, n / 2)$
 If $m$ and $n$ are both odd with $m > n$, then $gcd(m, n) = gcd(m  n, n)$
 If one of $m$ and $n$ is even (say $m$), then $gcd(m, n) = gcd(m / 2, n)$
 If $m = n$, then $gcd(m, n) = m$
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
 $(a + c) \equiv (b + d) (\text{mod} \ n)$
 $ac \equiv bd (\text{mod} \ n)$
 $a^m \equiv b^m (\text{mod} \ n)$ for all $m \in \mathbb{N}$
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 nonzero $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 nonempty set whose elements satisfy the following five rules:
 $g_1, g_2 \in G \implies g_1 g_2 \in G$
 $g_1, g_2, g_3 \in G \implies (g_1 g_2) g_3 = g_1 (g_2 g_3)$
 $g_1, g_2 \in G \implies g_1 g_2 = g_2 g_1$
 There exists an element $e \in G$ such that $eg = ge = g$ for all $g \in G$
 $g \in G \implies$ there exists $h \in G$ such that $gh = hg = e$
This set is called a commutative or Abelian group.
Tests For Divisibility
 A number is divisible by 2 iff its last digit is divisible by 2
 A number is divisible by 4 iff the last 2 digits form a number which is divisible by 4
 A number is divisible by $5^a$ iff its last $a$ digits is divisible by $5^a$
 A number is divisibly by 7 iff the number formed by doubling the last digit and subtracting it from the remaining truncated number is divisble by 7
 A number is divisible by 9,3 iff the sum of its digits is divisible by 9,3 respectively
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 nonresidue 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
 $\phi(p^m) = p^{m  1}(p  1) = p^m(1  \frac{1}{p})$
 If $gcd(m, n) = 1$ then $\phi(mn) = \phi(m) \phi(n)$
 For distinct primes $p, q$, $\phi(pq) = (p  1)(q  1)$
 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
 $a \mid \phi(n)$
 For a prime $p$
 A primitive element mod $p$ exists
 If $a$ is a primitive root mod $p$ then so is $a^k$, where $gcd(k, p  1) = 1$
 There are $\phi(p  1)$ primitive roots mod $p$
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 nonresidue.
Since every nonzero 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 nonresidue 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 nonresidues, there exist elements in $\mathbb{Z}_p$ that are quadratic nonresidues, 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
 $0 \oplus 0 = 0$
 $1 \oplus 0 = 1$
 $0 \oplus 1 = 1$
 $1 \oplus 1 = 0$
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
 $x = a \oplus b \oplus d$,
 $y = a \oplus c \oplus d,$
 $z = b \oplus c \oplus d$
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.
 If the received message $\mathbf{r}$ is correct, then $H\mathbf{r} = \vec{0}$
 If there is one error $\mathbf{r}$, then $H\mathbf{r} \ne \vec{0}$, and $H\mathbf{r}$ will be the $i$’th column in $H$ corresponding to some $r_i$ in $\mathbf{r}$ denoting that $r_i$ is incorrect
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”.
 If all $a_i \in R$, a given commutative ring (with $1$), $f(x)$ is called a polynomial defined over $R$
 If all $a_i = 0$, then it is called a zeropolynomial, denoted by $0$
 If $a_n \ne 0$, then $n$ is called the degree of $f(x)$, denoted by $\deg{f(x)}$, and $a_n$ is called the leading coefficient
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 zerodivisors ($0 \ne a \in R$ is called a zero divisor, if $\exists b \ne 0$ such that $ab = 0$), then $R[x]$ has zerodivisors.
Division Theorem
Let $F$ be a field. If $f(x), g(x) \in F[x]$ and $g(x)$ is a nonzero 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
 $d(x) \mid f(x)$ and $d(x) \mid g(x)$
 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
 $f_1(x) \pm g_1(x) \equiv f_2(x) \pm g_2(x)(\text{mod} \ m(x))$
 $f_1(x) g_1(x) \equiv f_2(x) g_2(x)(\text{mod} \ m(x))$
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.
 $F[x] / \langle m(x) \rangle$ is a commutative ring with identity
 $r(x) \in F[x] / \langle m(x) \rangle$ is invertible, iff $gcd(r(x), m(x)) = 1$
 $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)).\] The equation $(*)$ has a solution iff $d(x) \mid b(x)$
 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))$
 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:
 $(f \pm g)^{\prime} = f^{\prime} \pm g^{\prime}$
 $(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$.
 If $f(x)$ is primitive and reducible, then it has a factor of degree less than or equal to $n/2$.
 If $f(\frac{r}{s}) = 0$ where $gcd(r, s) = 1$, then $s \mid a_n$ and $r \mid a_0$. For all $r, s, \in \mathbb{Z}$ with $s \mid a_n$ and $r \mid a_0$, if $f(\frac{r}{s}) \ne 0$, then $f(x)$ has no linear factor in $\mathbb{Z}[x]$.
 $f(x)$ is irreducible iff $g(x) = f(x + a) \ (a \in \mathbb{Z})$ is irreducible
 If $f(x)$ modulo $n$ is irreducible in $\mathbb{Z}_n[x]$, then $f(x)$ is irreducible in $\mathbb{Z}[x]$ and so in $\mathbb{Q}[x]$
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
 For every prime $p$ and integer $k > 0$, there is a finite field $F$ with $p^k$ elements
 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
 $F$ has a primitive element $\alpha$ such that $O(\alpha) = q  1$
 Every element of $F^\ast$ is a power of $\alpha$ and has order a factor of $q  1$
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
 $O(\beta) = (q  1) / d$
 $\beta$ is also a primitive element iff $d = 1$
 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$.
 The minimal polynomial of $\beta$ is unique
 If $f(x)$ is irreducible and $f(\beta) = 0$ then $f$ is the minimal polynomial for $\beta$
Take any nonzero 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 nonzero 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:
 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]$
 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
 $R(\alpha) = 0$ then there were no errors
 $R(\alpha) = \alpha^i, R(\alpha^3) = \alpha^{3i}$ then there was one error at position corresponding to $\alpha^i$
 $R(\alpha^3) \ne (R(\alpha))^3$ then there were two errors and we proceed as above to locate them