In this series, I will introduce the Fundamental Contents in Computer Theory and Algorithms. If you hope to learn more advanced algorithms and techniques, please move to my another series Algorithm Design and Analysis.

In this blog, I try to do some preparation for following contents. I prefer to introduce the algorithms in a more rigorous and strict way. In theoretical computer science and algorithms, we will encounter lot of statements, like the correctness and running time for some specific algorithm. The way to assert a statement is true is Proof, then the statement will become a theorem (or lemma, claim, corollary anyway). Hence, we start from Logic which is very beginning of our story (may not be romantic but must be interesting and attractive).

Another part of this blog is number theory, which is powerful and common tool in our journey. Off course, we hope we can master more math, which are always the enrich toolbox for computer scientists.

Logic

Proposition

First, we will give the definition of Proposition.

Definition: A proposition is a declarative sentence (that is, a sentence that declares a fact) that is either true or false, but not both. So we have true proposition and false proposition.

Definition: The truth value of true proportion is true denote as $T$, and the truth value of false proportion is false denote as $F$.

We can denote proposition variables (or statement variables) by letters $p,q,r,s, \cdots$. The following step we will do is to combine some propositions together, that is compound propositions.

Definition: Let $p$ be a proposition. The negation of $p$, denoted by $\lnot p$ (also denoted by $\bar{p}$). The truth value of the negation of $p,\lnot p$, is the opposite of the truth value of $p$.

Definition: Let $p$ and $q$ be propositions. The conjunction of p and q, denoted by $p \land q$, is the proposition “$p$ and $q$.” The conjunction p ∧ q is true when both p and q are true and is false otherwise.

Definition: Let $p$ and $q$ be propositions. The disjunction of $p$ and $q$, denoted by $p \lor q$, is the proposition “$p$ or $q$.” The disjunction $p \lor q$ is false when both p and q are false and is true otherwise. (Note disjunction is inclusive or, we will introduce exclusive or in the next.)

Definition: Let $p$ and $q$ be propositions. The exclusive or of $p$ and $q$, denoted by $p \oplus q$, is the proposition that is true when exactly one of $p$ and $q$ is true and is false otherwise. (We can also to represent it $(p\land \lnot p) \lor (\lnot p \land p)$ by above denotations).

Conditional Statement

Definition: Let $p$ and $q$ be propositions. The conditional statement $p \rightarrow q$ is the proposition “if $p$, then $q$.” The conditional statement $p \rightarrow q$ is false when $p$ is true and $q$ is false, and true otherwise. (Note: that means if $p$ is false, no matter what $p\rightarrow q$ is true) In the conditional statement $p \rightarrow q$, $p$ is called the hypothesis (or antecedent or premise) and $q$ is called the conclusion (or consequence).

The statement $p \rightarrow q$ is called a conditional statement because $p \rightarrow q$ asserts that $q$ is true on the condition that $p$ holds. A conditional statement is also called an implication.

Converse, Contrapositive, and Inverse

Given a conditional statement $p \rightarrow q$, there are three related conditional statements that occur so often.

Converse: The proposition $q \rightarrow p$ is called the converse of $p \rightarrow q$.

Contrapositive: The contrapositive of $p \rightarrow q$ is the proposition $\lnot q \rightarrow \lnot p$.

Inverse: The proposition $\lnot p \rightarrow \lnot q$ is called the inverse of $p \rightarrow q$.

Claim 1.1: Only the contrapositive always has the same truth value as $p \rightarrow q$.

Proof. First we show that the contrapositive always has the same truth value as original conditional statement. If the contrapositive is false only when $\lnot p$ is false and $\lnot q$ is true, that is, only when $p$ is true and $q$ is false, which implies it has the same truth value with $p \rightarrow q$. $\square$

But the truth value of converse and inverse don’t have relation to original conditional statement.

When two compound propositions always have the same truth value we call them equivalent, so that a conditional statement and its contrapositive are equivalent.

Biconditional

We now introduce another way to combine propositions that expresses that two propositions have the same truth value.

Definition: Let $p$ and $q$ be propositions. The biconditional statement $p \leftrightarrow q$ is the proposition “$p$ if and only if $q$.” The biconditional statement $p \leftrightarrow q$ is true when $p$ and $q$ have the same truth values, and is false otherwise. Biconditional statements are also called bi-implications.

Example

Let $p$, $q$, and $r$ be the propositions ¹

$p$ : Grizzly bears have been seen in the area.

$q$ : Hiking is safe on the trail.

$r$ : Berries are ripe along the trail.

Write these propositions using $p$, $q$, and $r$ and logical connectives (including negations).

a) If berries are ripe along the trail, hiking is safe if and only if grizzly bears have not been seen in the area.

$r \rightarrow (q \rightarrow \lnot p)$

b) For hiking on the trail to be safe, it is necessary but not sufficient that berries not be ripe along the trail and for grizzly bears not to have been seen in the area.

$(q \rightarrow (\lnot r \land \lnot p)) \land (\lnot ((\lnot r \land \lnot p) \rightarrow q))$

f ) Hiking is not safe on the trail whenever grizzly bears have been seen in the area and berries are ripe along the trail.

$(p \land r) \rightarrow \lnot q$

Number Theory

Divisibility and Modular Arithmetic

Definition: Given $a$ and $b$ are integers with $a \neq 0$, if $\exists c \in \mathbb{Z}$ such that $b = ac$, we say that $a$ divides $b$ or equivalently, $b/a$ is an integer. (Or $b$ is divisible by $a$).

Definition: When $a$ divides $b$, $a$ is a factor or divisor of $b$, and that $b$ is a multiple of $a$. The notation $a \mid b$ denotes that $a$ divides $b$. We write $a ∤ b$ when $a$ does not divide $a \nmid b$.

Theorem 1.2: Let $a, b$ and $c$ be integers, where $a \neq 0$. Then (i) if $a \mid b$ and $a \mid c$, then $a \mid (b + c)$; (ii) if $a \mid b$, then $a \mid bc$ for all integers $c$; (iii) if $a \mid b$ and $b \mid c$, then $a \mid c$.

The Division Theorem

First, we will give the Division Theorem, it seems right and easy to understand. But its proof is complex than we thought. For preliminary,we will first give Well-Order Axiom, which is truth agreed by default, so we don’t need and cannot prove it. (In fact, this is tooo complex and out of scope here, so we don’t talk it here.)

Well-Order Axiom: every non-empty set of positive integers contains a smallest element (here “small” defined by Peano axioms).

Theorem 1.3 The Division Theorem: Let $a$ be an integer and $d$ a positive integer. Then there are unique integers $q$ and $r$, with $0 \leq r < d$, such that $a = dq + r$.

Proof. Construct set ${S = \{ x \in \mathbb{N} \mid x = a- kd, k\in \mathbb{Z}\}}$. By definition, we know $S \subset \mathbb{N}$. Additionally, if $a \geq 0$, let $k=0$, we have $a \in S$, else $a < 0$, let $k=a$, we have $a-ad = a(1-d) \geq 0$, that implies $a-ad \in S$. So, we know $S$ is a non-empty set of positive integers. Hence, we can have a smallest element, say $r$. We know $r \geq 0$ and denote $r = a-q b, q \in \mathbb{Z}$. Now, we will prove the theorem in two part, existence and uniqueness.

Existence: We already find the $r$ such that $r \geq 0$, we just need to show $r <d$, that can prove the existence. Suppose $r \geq d$, let $r’ = a - (q+1)d$, we have \(r' = a-(qa +1)d = a- q d - d = r - d \geq 0 \Rightarrow r' \in S\) And $r’<r$ which contradicts to $r$ is the smallest number. In the meantime, we find the integer $q$.

Uniqueness: Suppose we have $r_1,r_2,q_1,q_2$ such that $a = dq_1 + r_1, a = dq_2 + r_2$. With out loss generality, we set $r_1 \leq r_2$ Then, we have \(r_2 -r_1 = d (q_1 - q_2)\) We know $0 \leq r_1 \leq r_2 < d$, then we know $0 \leq r_2 - r_1 < d$. Because $q_1 - q_2 \in \mathbb{Z}$, then we have $q_1 = q_2$, and then force $r_2 - r_1 = 0$. $\square$

Definition: By above division theorem, $d$ is called the divisor, $a$ is called the dividend, $q$ is called the quotient, and $r$ is called the remainder. This notation is used to express the quotient and remainder:

Theorem 1.4: Given $a$ is an integer and $d$ is a positive integer, then $a \text{ div } d = \lfloor a/d \rfloor$ and $a \text{ mod } d = a − d \lfloor a/d \rfloor$.

Modular Arithmetic

Definition: If $a$ and $b$ are integers and $m$ is a positive integer, then $a$ is congruent to $b$ modulo $m$ if $m$ divides $a − b$. We use the notation $a \equiv b (\text{mod } m)$ to indicate that $a$ is congruent to $b$ modulo $m$. We say that $a \equiv b (\text{mod } m)$ is a congruence and that $m$ is its modulus (plural moduli). If $a$ and $b$ are not congruent modulo $m$, we write $a \not\equiv b (\text{mod } m)$.

Theorem 1.5: Let $a$ and $b$ be integers, and let $m$ be a positive integer. Then $a \equiv b (\text{mod } m)$ if and only if $a \text{ mod } m = b \text{ mod } m$.

Proof.

$\Rightarrow$: Assume $a \equiv b (\text{mod } m)$, that means $m$ divides $a-b$ or $\exists z \in \mathbb{Z}$ such that $a -b = mz$. Denote $r_1,r_2,q_1,q_2 \in \mathbb{Z}$ such that $a = q_1 m + r_1, b = q_2 m + r_2$ with $0\leq r_1,r_2 < m$. Hence, we have

Denote $t = z - q_1 + q_2 \in \mathbb{Z}$. So $mt = r_1 -r_2$, and $- m < r_1 -r_2 <m$. Thus, $r_1 -r_2$ has to be zero, that means $r_1 = r_2$.

$\Leftarrow$: Assume $a \text{ mod } m = b \text{ mod } m$, then we can denote $r,q_1,q_2 \in \mathbb{Z}$ such that \(a = q_1 m + r, b = q_2 m + r \text{ with } 0\leq r < m\)

Then $a - b = (q_1-q_2)m$, then we know $a -b$ is divisible by $m$. $\square$

Definition: The set of all integers congruent to an integer a modulo $m$ is called the congruence class of a modulo $m$.

Theorem 1.6: Let $m$ be a positive integer. If $a \equiv b (\text{mod } m)$ and $c \equiv d (\text{mod } m)$, then \(a +c \equiv b+d (\text{mod } m)\)

and

Proof. From $a \equiv b (\text{mod } m)$ and $c \equiv d (\text{mod } m)$, we have $\exists z_1,z_2 \in \mathbb{Z}$ such that $a -b = z_1 m, c -d = z_2 m$. Hence, we have

and

Thus, we have $a +c \equiv b+d (\text{mod } m)$ and $ac \equiv bd (\text{mod } m)$. $\square$

In fact, this theorem is more profound than we thought, we will talk it later after give a corollary.

Corollary 1.7: Let $m$ be a positive integer and let $a$ and $b$ be integers. Then \((a + b) \text{ mod } m = ((a \text{ mod } m) + (b \text{ mod } m)) \text{ mod } m\)

and

Proof: We know that $a \equiv (a \text{ mod } m) \text{ mod } m$ and $b \equiv (b \text{ mod } m) \text { mod } m$. Hence, the above Theorem tells us that

and

We prove this corollary. $\square$

Ring of Integers Modulo $m$

We can define arithmetic operations on $\mathbb{Z}_m$, that is ${\{0, 1, …, m - 1\}}$. In particular, we define addition of these integers, denoted by $+_m$ by

where the addition on the right-hand side of this equation is the ordinary addition of integers, and we define multiplication of these integers, denoted by $\cdot_m$ by

where the multiplication on the right-hand side of this equation is the ordinary multiplication of integers. The operations $+_m$ and $\cdot_m$ are called addition and multiplication modulo $m$. The above content defines the “addition” and “multiplication” on set $\mathbb{Z}_m$.

The operations $+_m$ and $\cdot_m$ satisfy following properties:

Note: In abstract algebra, we have the algebra structures called group and ring. Because $\mathbb{Z}_m$ with the operations of addition and multiplication modulo $m$ satisfies the properties listed, $\mathbb{Z}_m$ with modular addition is said to be a commutative group and $\mathbb{Z}_m$ with both of these operations is said to be a commutative ring. ($\mathbb{Z}$ with ordinary addition and multiplication also forms a commutative ring).

Integer Representations and Algorithms

In fact, any integer can be expressed using some integer ($> 1$) as base. We commonly use decimal (base 10) in our daily life and binary (base 2), octal (base 8), hexadecimal (base 16) in computer science. In general, given a base $b$ and an integer $n$, we can construct a representation of base $b$ for integer $n$.

Representations of Integers

Theorem 1.8: Let $b$ be an integer greater than $1$. Then given any positive integer $n$, it can be expressed uniquely in the form \(n = a_k b^k + a_{k-1} b^{k-1} + \cdots + a_1 b + a_0\)

where $k$ is a nonnegative integer, $a_0,a_1,\cdots,a_k$ are also nonnegative integers and are less than $b$ and $a_k \neq 0$.

Proof. We will show it by induction.

• Base case: For $n = 1$, it’s trivial to get $a_0 = 1, k = 0$, and it’s unique to represent it.

• Induction Hypothesis: $\forall n < m , m \in \mathbb{Z}$ we can represent $n$ in above form uniquely.
• Inductive Step: For $n = m$, let’s check $m$ can be represented in above form. Let’s denote $q = m \text{ div } b$ and $r = m \text{ mod } b$. That means $m = qb + r$, and we know such pair of $q,r$ satisfying above formula with $0 \leq r < b$ is unique. Besides, we know $q < m$ because $b > 1$. Hence, we know $q$ can be expressed as above form uniquely, let’s denote it as follow

Hence, we know $m$ is \(\begin{aligned} m &= qb + r \\ &= (a_\ell b^\ell + a_{\ell - 1} b^{\ell -1} + \cdots + a_1 b + a_0)b + r \\ &= a_\ell b^{\ell + 1} + a_{\ell - 1}b^\ell + \cdots + a_1 b^2 + a_0 b + r \end{aligned}\) Thus, we represent $m$ as the form we want and we know $q,r$ are unique and the representation of $q$ is unique. So, the above way to express $m$ is unique. We prove the theorem by induction. $\square$

Definition: The representation of $n$ mentioned in Theorem 1.8 is called the base $b$ expansion of $n$, which we denoted as $(a_ka_{k-1}\cdots a_1a_0)_b$. (So, we have decimal expansion, binary expansion, octal expansion, hexadecimal expansion etc.)

By the process of above proof, we can get the following algorithm

1
2
3
4
5
6
7
8
9
10
// Constructing Base b Expansion
Base_b_Expansion (n,b){
	q = n 
	k = 0
	while q != 0
		a[k] = q mod b
		q = q div b
		k = k + 1
	return (a[k],a[k-1],...,a[0])
}

Algorithms for Integer Operations

Alert: In this part, we will talk about the running time of some algorithms. If you’re not familiar with what’s running time and the notation of $\Theta(n),\mathcal{O}(n)$ please check the following blogs of this series or this blog.

In this section, we will focus on the operations (addition, multiplication, mod, div) with integers by binary expansion. Given two integer $a,b$ as below \(a = (a_{n-1}\cdots a_1 a_0), \quad b = (b_{n-1}\cdots b_1 b_0)\) And we call $a$ and $b$ each have $n$ bits.

Addition

To add $a$ and $b$, first add their rightmost bits. We have \(a_0 + b_0 = c_0 \cdot 2 + s_0\) where $0 \leq s_0 < 2$ is the rightmost bit in the binary expansion of $a+b$ and $c_0$ is the carry, which is $0$ or $1$. Then add the next pair of bits and the carry

\(a_1 + b_1 + c_0 = c_1 \cdot 2 + s_1\) where $s_1$ is the next bit and $c_1$ is the carry. (Here you can think about that why each $c_i$ can only be $0$ or $1$.) Following this idea, we can give the algorithm in pseudocode

1
2
3
4
5
6
7
8
9
10
// Add in Binary Expansion
Add(a,b){ // a = a[n-1] ... a[1] a[0], b = b[n-1] ... b[1] b[0]
	c = 0
	for i = 0 to n-1
		q = floor((a[j]+ b[j] + c)/2)
		s[j] = a[j] + b[j] + c - 2q
		c = q
	s[n] = c
	return (s[0] ... s[n])
}

We can get the running time of addition is $\mathcal{O}(n)$.

Multiplication

Now, we will show how to do multiplication \(\begin{aligned} ab & = a (b_0 2^0 + b_1 2^1 + \cdots + b_{n-1} 2^{n-1}) \\ & = b_0 (a 2^0) + b_1 (a 2^1) + \cdots + b_{n-1} (a 2^{n-1}) \\ \end{aligned}\) So, how to calculate each item? We noticed that $b_i = 0 \text{ or } 1$. It’s trivial to get $b_i(a 2^i) = 0$ when $b_i = 0$. Otherwise, $b_i(a 2^i) = a 2^i$, which can be obtained by left-shifting $i$ bits of $a$. Then, we can call “Add” procedure $n$ times to take the sum of each items.

1
2
3
4
5
6
7
8
9
10
11
12
// Multiply in Binary Expansion
Multiply(a,b){ // a = a[n-1] ... a[1] a[0], b = b[n-1] ... b[1] b[0]
	for i = 0 to n-1
​		if b[i] = 1then c[i] = a << n // left-shift n bits
​		else c[i] = 0

​	s = s[n-1] ... s [1]s[0]

​	for j = 0 to n-1
​		Add(s, c[i])
​	return s
}

In multiplication, we do $n$ times addition so the running time is $\mathcal{O}(n^2)$.

Div and Mod

The idea for solving quotient and reminder is called “brute-force”, that is we deduct dividend $d$ until the integer we get less than $d$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Div and Mod
Divide(a,d){ // a is any integer, d is a positive integer
	q = 0
​	r = |a|

​	while r >= d
​		r = r - d
​		q = q + 1

​	if a< 0 and r > 0 then
​		r = d - r
​		q = -(q+1)

​	return r, q // r = a mod d, q = a div d
}

We know if we want to represent $a$ in binary expansion, we need $\log a$ bits, and we do $q$ times minus that means the total running time is $\mathcal{O}(q \log a)$. In fact, there exists more efficient algorithm that can implement it in $\mathcal{O}(\log d \log a)$, if $a \geq d$, we know it is $\mathcal{O}((\log a)^2)$.

Modular Exponentiation

If we want to solve $b^n \text{ mod } m$, we need $\mathcal{O}(\frac{n b^n}{m} \log a)$, which is a huge number. So, we hope to find a more efficient way to do. First, consider that $n$ can be expressed in binary expansion.

In fact, we don’t need to compute $b^n$ first, because by Corollary 1.7 we can compute each $b^{2^i} \text{ mod } m$ when $a_i = 1$, and multiply each item. What’s more, we can get $b^{2^i} \text{ mod } m$ by $b^{2^{i-1}} \text{ mod } m$. Following is the algorithm in pseudocode.

1
2
3
4
5
6
7
8
9
10
11
// Modular exponentiation
Modular_exponentiation (b,n,m) { // n = a[n-1] ... a[1] a[0], m is a positive integer
	x = 1
	power = b mod m

	for i = 0 to k-1
		if a[i] = 1 then x = (x * power) mod m
		power = (power * power) mod m
	
	return x
}

We now try to analyze running time of above algorithm. We know $k = \log n$, that means we use $k$ bits to represent $n$ which is also the number of loops. In each loop, the multiplication takes $\mathcal{O}((\log m)^2)$ (because $x$ and $power$ are all less than $m$, so we at most use $\log m$ bits to represent them) and “mod” arithmetic takes $ \mathcal{O}((\log m)^2) $ (using some efficient mod algorithm and $x \cdot power$ and $power \cdot power$ with not longer than $2 \log m$ bits).

Primes and Greatest Common Divisors

Definition: An integer $p$ greater than $1$ is called prime if the only positive factors of $p$ are $1$ and $p$. A positive integer that is greater than $1$ and is not prime is called composite.

Theorem 1.9: The Fundamental Theorem of Arithmetic Every integer greater than $1$ can be written uniquely as a prime or as the product of two or more primes where the prime factors are written in order of nondecreasing size. (We will not show proof here.)

Theorem 1.10: If $n$ is a composite integer, then $n$ has a prime divisor less than or equal to $\sqrt{n}$.

Proof: If $n$ is composite, by the definition of a composite integer, we know that it has a factor $a$ with $1 < a < n$. Hence, we have $n = ab$, where $b$ is a positive integer greater than $1$. We will show that $a \leq \sqrt{n}$ or $b \leq \sqrt{n}$. If $a > \sqrt{n}$ and $b > \sqrt{n}$, then $ab > \sqrt{n} \cdot \sqrt{n} = n$, which is a contradiction. Consequently, $a \leq \sqrt{n}$ or $b \leq \sqrt{n}$. Because both $a$ and $b$ are divisors of $n$, we see that $n$ has a positive divisor not exceeding $\sqrt{n}$. This divisor is either prime or, by the fundamental theorem of arithmetic, has a prime divisor less than itself. In either case, $n$ has a prime divisor less than or equal to $\sqrt{n}$. $\square$

Theorem 1.11: There are infinitely many primes.

Proof: Suppose there are only finitely many primes, $p_1, p_2, …, p_n$. Let

By the fundamental theorem of arithmetic, $Q$ is prime or else it can be written as the product of two or more primes. For each primes $p_j$, by corollary 1.7, we have \(Q \text{ mod } p_j = ((p_1p_2\cdots p_n) \text{ mod } m + 1 \text{ mod } m) \text{ mod m} = 1\) Hence, there is a prime not in the list $p_1, p_2, …, p_n$. This prime is either $Q$, if it is prime, or a prime factor of $Q$. This is a contradiction because we assumed that we have listed all the primes. Consequently, there are infinitely many primes. $\square$

Greatest Common Divisors and Least Common Multiples

Definition: Let $a$ and $b$ be integers, not both zero. The largest integer $d$ such that $d \mid a$ and $d \mid b$ is called the greatest common divisor of $a$ and $b$. The greatest common divisor of $a$ and $b$ is denoted by $\text{gcd}(a, b) $.

Definition: The integers $a$ and $b$ are relatively prime if $\gcd(a,b)=1$.

Definition: The integers $a_1, a_2, \ldots, a_n$ are pairwise relatively prime if $\text{gcd}(a_i, a_j) = 1$ whenever $1 \leq i < j \leq n$.

A efficient way to find the greatest common divisor of two positive integers is to use the prime factorizations of these integers. Suppose that the prime factorizations of the positive integers $a$ and $b$ are

where each exponent is a nonnegative integer, and where all primes occurring in the prime factorization of either $a$ or $b$ are included in both factorizations, with zero exponents if necessary. Then $\text{gcd}(a, b)$ is given by

where $\min(x, y)$ represents the minimum of the two numbers $x$ and $y$.

Definition: The least common multiple of the positive integers $a$ and $b$ is the smallest positive integer that is divisible by both $a$ and $b$. The least common multiple of $a$ and $b$ is denoted by $\text{lcm}(a, b)$.

Suppose that the prime factorizations of $a$ and $b$ are as before. Then the least common multiple of $a$ and $b$ is given by

where $\max(x, y)$ denotes the maximum of the two numbers $x$ and $y$. This formula is valid because a common multiple of $a$ and $b$ has at least $\max(a_i, b_i)$ factors of $p_i$ in its prime factorization, and each power of prime cannot be decreased.

Theorem 1.11: 5 Let $a$ and $b$ be positive integers. Then \(ab = \gcd (a,b) \cdot \text{lcm} (a,b)\) Proof. Suppose that the prime factorizations of the positive integers $a$ and $b$ are \(a = p_1^{a_1} p_2^{a_2} \ldots p_n^{a_n}, \quad b = p_1^{b_1} p_2^{b_2} \ldots p_n^{b_n}\)

and we know \(\text{gcd}(a, b) = p_1^{\min(a_1,b_1)} p_2^{\min(a_2,b_2)} \ldots p_n^{\min(a_n,b_n)}, \quad \text{lcm}(a, b) = p_1^{\max(a_1,b_1)} p_2^{\max(a_2,b_2)} \ldots p_n^{\max(a_n,b_n)}\) Because $\min(a_i, b_i) + max(a_i, b_i) = a_i + b_i$, the exponent of $p_i$ in the prime factorization of $\gcd (a,b) \cdot \text{lcm} (a,b) $ is the sum of the exponents of $p_i$ in the prime factorizations of $a$ and $b$. $\square$

The Euclidian ALgorithm

gcds as Linear Combinations

Solving Congruences

Linear Congurences

The Chinese Reminder Theorem

Fermat’s Little Theorem

Primitive Roots and Discrete Logarithms

Applications of Congruences

Cryptography