Chapter 4 - Number Theory

4.1 Introduction

TLDR: This chapter introduces number theory, focusing on the properties of integers ($\mathbb{Z}$). It briefly discusses the definition of integers and their importance as a foundation for more advanced mathematical concepts, particularly within computer science applications like cryptography.

4.1.1 Number Theory as a Mathematical Discipline

Number theory is the mathematical study of integers ($\mathbb{Z}=\{\dots ,-2,-1,0,1,2,\dots \}$), their properties, and the relationships between them. It’s a vast field with surprising connections to other areas of mathematics and numerous applications in computer science, especially in cryptography.

Historical Note:

While initially considered a “pure” area of mathematics (with little practical application), number theory’s importance in cryptography and other fields has dramatically increased in recent decades.

Key Areas of Study:

Number theory encompasses many subfields, including:

• Prime Numbers: The study of prime numbers (integers divisible only by 1 and themselves) is fundamental. Questions about their distribution, the infinitude of primes, and efficient primality testing are central topics.

• Divisibility and Congruences: Number theory explores divisibility relationships between integers (e.g., determining the greatest common divisor and least common multiple) and modular arithmetic (arithmetic performed within a finite set of remainders). Congruences are a core tool for studying these relationships.

• Diophantine Equations: These are polynomial equations where only integer solutions are sought. Famous examples include Fermat’s Last Theorem and the Catalan conjecture. Finding efficient solutions or proving the absence of solutions are major challenges in this area.

• Algebraic Number Theory: This area expands the study beyond rational numbers to include algebraic numbers (roots of polynomials with integer coefficients) and their properties. This has profound implications in understanding number systems.

4.1.2 What are the Integers?

Definition:

The integers, denoted by $\mathbb{Z}$, are the set of all whole numbers, including positive, negative, and zero: $\mathbb{Z}=\{...,-3,-2,-1,0,1,2,3,...\}$.

Importance in Mathematics:

The integers form the basis for many areas of mathematics. They are used to build other number systems (rational numbers, real numbers, complex numbers), and they underlie concepts like divisibility, prime factorization, and modular arithmetic.

Axiomatic Treatment:

A rigorous treatment of number theory would start by formally defining the integers through axioms, but this isn’t feasible within the scope of this introductory chapter. This chapter relies on the intuitive understanding of the integers that most readers already possess. Later chapters will explore generalizations that extend concepts from integers to broader algebraic structures (like rings and fields).

Examples:

• Example 4.1 (Goldbach Conjecture): Are there infinitely many prime pairs? (Pairs of prime numbers differing by 2, such as (3, 5), (5, 7), (11, 13), etc.). This is an unsolved problem in number theory.

• Example 4.2 (Pythagorean Triples): Do positive integer solutions exist for $a^2+b^2=c^2$? Yes, many exist ; these form Pythagorean triples, such as (3, 4, 5) or (5, 12, 13).

• Example 4.3 (Fermat’s Last Theorem): Does the equation $a^n+b^n=c^n$ have any positive integer solutions for any $n>2$? No ; this was famously proven by Andrew Wiles in 1994.

• Example 4.4 (Catalan Conjecture): Does the equation $x^m-y^n=1$ have any positive integer solutions besides $3^2-2^3=1$? No, proven by Preda Mihăilescu in 2002.

These examples illustrate the kinds of questions explored in number theory, ranging from relatively straightforward problems to extremely difficult ones that have remained open for centuries. Many of these problems have deep connections to other areas of mathematics and to computer science, especially cryptography.

4.2 Divisors and Division

TLDR: This section formally defines divisors and the division algorithm (with remainders), introduces the concepts of greatest common divisors (GCD) and least common multiples (LCM), and presents the Euclidean algorithm for efficiently computing GCDs.

4.2.1 Divisors

Definition:

An integer $d$ is a divisor of an integer $n$ (denoted $d|n$) if there exists an integer $k$ such that $n=dk$. In this case, $n$ is a multiple of $d$.

Examples:

• Example: $3|12$ because $12=3\times 4$.
• Example: $5|0$ because $0=5\times 0$.
• Example: $-2|6$ because $6=(-2)\times (-3)$.

4.2.2 Division with Remainders

Theorem 4.1 (Division Algorithm):

For any integers $n$ and $d$ with $d>0$, there exist unique integers $q$ (the quotient) and $r$ (the remainder) such that:

$n=qd+r\text{and}0\le r<d$

This theorem states that any integer $n$ can be uniquely expressed as a multiple of $d$ plus a remainder smaller than $d$.

Proof:

1. Existence: Consider the set $S=\{n-kd\mid k\in \mathbb{Z},n-kd\ge 0\}$. This set contains non-negative integers. If $n\ge 0$, then $n\in S$. If $n<0$, then $n-kd\ge 0$ for some $k$ (e.g. $k=n$ if $d>0$ and $k=n/2$ if $d<0$). The Well-Ordering Principle (every non-empty set of non-negative integers contains a smallest element) guarantees that $S$ has a smallest element, which we’ll call $r$.

2. $r<d$: Assume $r\ge d$. Then $r=d+r^{\prime }$ for some non-negative integer $r^{\prime }$. Since $r\in S$, we have $r=n-kd$ for some integer $k$. Substituting, we get $d+r^{\prime }=n-kd$, meaning $r^{\prime }=n-(k+1)d$. Since $r^{\prime }$ is non-negative, this means $r^{\prime }\in S$. However, $r^{\prime }=r-d<r$, which contradicts the fact that $r$ is the smallest element in $S$. Therefore, we must have $r<d$.

3. Uniqueness: Assume there are two pairs of integers $(q,r)$ and $(q^{\prime },r^{\prime })$ that satisfy the conditions. Then $n=qd+r=q^{\prime }d+r^{\prime }$, implying $qd+r=q^{\prime }d+r^{\prime }$. If $r=r^{\prime }$, then $qd=q^{\prime }d$, so $q=q^{\prime }$ (since $d>0$). If $r\ne r^{\prime }$, then without loss of generality, assume $r^{\prime }>r$. Then $qd-q^{\prime }d=r^{\prime }-r$. Since $r^{\prime }-r<d$ and $d|(qd-q^{\prime }d)$, we must have $r^{\prime }-r=0$, meaning $r^{\prime }=r$, a contradiction. Hence, the pair $(q,r)$ is unique.

Simplified Proof Pls… 👉👈

Division Algorithm

For any integers $n$ and $d$ with $d>0$, there exist unique integers $q$ (the quotient) and $r$ (the remainder) such that:

$n=qd+r$ and $0\le r<d$.

Proof:

1. Existence:

We need to show that integers $q$ and $r$ exist.

1. Define a set: Let $S=\{n-kd\mid k\in \mathbb{Z},n-kd\ge 0\}$.

• This set includes all non-negative integers of the form $n-kd$ for $k\in \mathbb{Z}$.

• If $n\ge 0$, then $k=0$ gives $n\in S$.

• If $n<0$, we can pick $k$ such that $n-kd\ge 0$. Hence, $S$ is non-empty.

2. Smallest element: By the Well-Ordering Principle, $S$ has a smallest element, call it $r$.

• By definition, $r=n-qd$ for some integer $q$.
• Therefore, $n=qd+r$ with $r\ge 0$.

2. $r<d$:

We now prove that $r<d$.

1. Assume $r\ge d$. Then $r=d+r^{\prime }$ for some $r^{\prime }\ge 0$.

• Substitute $r=d+r^{\prime }$ into $n=qd+r$, giving $n=qd+(d+r^{\prime })=(q+1)d+r^{\prime }$.

• Rearranging, $r^{\prime }=n-(q+1)d$.

2. Since $r^{\prime }\ge 0$, $r^{\prime }\in S$. However, $r^{\prime }=r-d<r$, contradicting that $r$ is the smallest element of $S$.

3. Hence, $r<d$. Combining this with $r\ge 0$, we get $0\le r<d$.

3. Uniqueness:

Finally, we prove that $(q,r)$ is unique.

1. Suppose two pairs $(q,r)$ and $(q^{\prime },r^{\prime })$ satisfy $n=qd+r$ and $n=q^{\prime }d+r^{\prime }$, where $0\le r,r^{\prime }<d$.

• Subtracting, $(q-q^{\prime })d=r^{\prime }-r$.

2. The left-hand side $(q-q^{\prime })d$ is a multiple of $d$, while $|r^{\prime }-r|<d$.

• The only way this holds is if $r^{\prime }-r=0$, so $r=r^{\prime }$.

3. Substituting $r=r^{\prime }$ into $(q-q^{\prime })d=0$, we get $q=q^{\prime }$.

4. Therefore, the pair $(q,r)$ is unique.

Conclusion:

For any integers $n$ and $d$ with $d>0$, there exist unique integers $q$ and $r$ such that:

$n=qd+r$ and $0\le r<d$.

Examples:

• If $n=13$ and $d=5$, then $13=2(5)+3$, so $q=2$ and $r=3$.
• If $n=-13$ and $d=5$, then $-13=-3(5)+2$, so $q=-3$ and $r=2$.
• If $n=13$ and $d=-5$, then $13=-2(-5)+3$, so $q=-2$ and $r=3$.
• If $n=-13$ and $d=-5$, then $-13=3(-5)+2$, so $q=3$ and $r=2$.

The remainder $r$ is often denoted as $n(\mathrm{mod}d)$.

4.2.3 Greatest Common Divisors (GCD)

Definition:

The greatest common divisor (GCD) of two integers $a$ and $b$, not both zero, denoted $\gcd (a,b)$, is the largest positive integer that divides both $a$ and $b$. If $\gcd (a,b)=1$, $a$ and $b$ are said to be relatively prime.

Lemma 4.2:

For any integers $m$, $n$, and $q$, $\gcd (m,n-qm)=\gcd (m,n)$.

Proof of Lemma 4.2: $\gcd (m,n-qm)=\gcd (m,n)$

We will prove this by showing that any common divisor of $m$ and $n$ is also a common divisor of $m$ and $n-qm$, and vice versa. This will establish that the set of common divisors is identical for both pairs, and therefore their greatest common divisors must be equal.

1. Any common divisor of $m$ and $n$ is a common divisor of $m$ and $n-qm$:

   Let $d$ be a common divisor of $m$ and $n$. This means that $d|m$ and $d|n$. By definition, there exist integers $k_1$ and $k_2$ such that $m=d{k}_1$ and $n=d{k}_2$. Then:

   $n-qm=d{k}_2-q(d{k}_1)=d(k_2-q{k}_1)$.

   Since $(k_2-q{k}_1)$ is an integer, this shows that $d|(n-qm)$. Therefore, $d$ is a common divisor of $m$ and $n-qm$.

2. Any common divisor of $m$ and $n-qm$ is a common divisor of $m$ and $n$:

   Let $d^{\prime }$ be a common divisor of $m$ and $n-qm$. Then $d^{\prime }|m$ and $d^{\prime }|(n-qm)$. This means there exist integers $k_3$ and $k_4$ such that $m=d^{\prime }{k}_3$ and $n-qm=d^{\prime }{k}_4$. Then:

   $n=n-qm+qm=d^{\prime }{k}_4+qm=d^{\prime }{k}_4+q(d^{\prime }{k}_3)=d^{\prime }(k_4+q{k}_3)$.

   Since $(k_4+q{k}_3)$ is an integer, this shows that $d^{\prime }|n$. Therefore, $d^{\prime }$ is a common divisor of $m$ and $n$.

3. Conclusion:

   From steps 1 and 2, we’ve shown that the set of common divisors of $(m,n)$ is identical to the set of common divisors of $(m,n-qm)$. Since the sets of common divisors are the same, their greatest common divisors must also be the same. Therefore: $\gcd (m,n-qm)=\gcd (m,n)$.

The Euclidean Algorithm:

The Euclidean algorithm is an efficient method for computing the GCD of two integers. It relies on repeatedly applying the division algorithm and Lemma 4.2.

Algorithm:

To find $\gcd (a,b)$ where $a,b\in \mathbb{Z}$ and $b>0$:

1. If $b=0$, then return $a$ (as the GCD).
2. Otherwise, let $a=q_{1}b+r_1$ where $0\le r_1<b$ (division algorithm).
3. If $r_1=0$, return $b$ (as the GCD).
4. Otherwise, recursively compute $\gcd (b,r_1)$ using steps 1-3. This process continues until the remainder is 0. The last non-zero remainder is the GCD.

Example:

Find $\gcd (18,12)$:

1. $18=1(12)+6$ ($r_1=6$)
2. $12=2(6)+0$ ($r_2=0$)

Therefore, $\gcd (18,12)=6$.

Ideals in $\mathbb{Z}$:

Definition: For $a,b\in \mathbb{Z}$, the ideal generated by $a$ and $b$, denoted $(a,b)$, is the set $\{ua+vb\mid u,v\in \mathbb{Z}\}$. Similarly, $(a)=\{ua\mid u\in \mathbb{Z}\}$. An ideal is a subset of a ring that’s closed under addition and multiplication by ring elements.

Lemma 4.3: For any $a,b\in \mathbb{Z}$, there exists a $d\in \mathbb{Z}$ such that $(a,b)=(d)$.

• Proof: If $a=b=0$, then $(a,b)=\{0\}=(0)$. Otherwise, the set $(a,b)$ contains positive integers. Let $d$ be the smallest positive integer in $(a,b)$. Clearly, $(d)\subseteq (a,b)$ because any multiple of $d$ is also in $(a,b)$. Now take any $c\in (a,b)$. Then $c=ud+r$ for some integers $u$ and $r$ with $0\le r<d$. Since $c\in (a,b)$ and $d\in (a,b)$, we know that $r=c-ud\in (a,b)$. If $r>0$, we have a contradiction since $d$ was defined as the smallest positive integer. Therefore, $r=0$, which means $c=ud$, so $c\in (d)$. Thus $(a,b)\subseteq (d)$, and therefore $(a,b)=(d)$.

Lemma 4.4: If $(a,b)=(d)$, then $d=\gcd (a,b)$.

• Proof: Since $d\in (a,b)$, $d$ is of the form $ua+vb$ for some $u,v\in \mathbb{Z}$. Therefore, any common divisor of $a$ and $b$ divides $d$. Since $a,b\in (d)$, it follows that $d|a$ and $d|b$. Therefore, $d$ is a common divisor of $a$ and $b$. Since any common divisor of $a$ and $b$ also divides $d$, $d$ must be the greatest common divisor of $a$ and $b$. Therefore $d=\gcd (a,b)$.

• Corollary 4.5: For $a,b\in \mathbb{Z}$ (not both zero), there exist $u,v\in \mathbb{Z}$ such that $\gcd (a,b)=ua+vb$. This is a direct consequence of Lemmas 4.3 and 4.4.

4.2.4 Least Common Multiples (LCM)

Definition:

The least common multiple (LCM) of two positive integers $n$ and $m$, denoted $\text{lcm}(n,m)$, is the smallest positive integer that is a multiple of both $n$ and $m$.

Examples:

• Example 4.4: $\text{lcm}(12,18)=36$. (Multiples of $12$: $12,24,36,\mathrm{48...}$; multiples of $18$: $18,36,\mathrm{54...}$ ; $36$ is the least common multiple).

• Note that $\gcd (a,b)\times \text{lcm}(a,b)=ab$ for any positive integers $a$ and $b$. This provides an alternate method to find LCM.

4.3 Factorization into Primes

TLDR: This chapter focuses on the Fundamental Theorem of Arithmetic, which states that every integer greater than 1 can be uniquely factored into a product of prime numbers. The chapter presents a proof of this theorem using induction and explores related concepts like greatest common divisors (gcd), least common multiples (lcm), and the implications of unique factorization (e.g., proving the irrationality of the square root of a prime). It also includes an interesting digression into the relationship between prime numbers and music theory.

4.3.1 Primes and the Fundamental Theorem of Arithmetic

Definitions:

• Prime Number: A positive integer $p>1$ is prime if its only positive divisors are 1 and $p$ itself.

• Composite Number: A positive integer $n>1$ that is not prime is called composite. This means it has at least one divisor other than 1 and itself.

Fundamental Theorem of Arithmetic:

This theorem states that every integer greater than 1 can be expressed as a unique product of prime numbers. This is a fundamental result in number theory.

4.3.2 Proof of the Fundamental Theorem of Arithmetic

Existence of Prime Factorization

This part demonstrates that every integer greater than 1 can be written as a product of primes. We use proof by contradiction and the principle of well-ordering (every non-empty set of positive integers contains a least element).

Proof:

1. Assumption (for contradiction): Suppose there’s at least one integer greater than 1 that cannot be expressed as a product of primes.

2. Well-ordering principle: Among all such integers, there must be a smallest one; call it $n$.

3. Contradiction: Since $n$ is not prime (otherwise it would trivially be a product of primes—itself), it must be composite. This means that it can be written as a product of two smaller integers, $n=ab$, with $1<a<n$ and $1<b<n$.

4. Inductive argument: Because $a$ and $b$ are smaller than $n$, and $n$ was assumed to be the smallest integer without a prime factorization, both $a$ and $b$ must be expressible as products of primes.

5. Final Contradiction: This means $n$, which is the product $ab$, can also be expressed as a product of primes (the prime factors of a and b combined). This contradicts our initial assumption that $n$ cannot be expressed as a product of primes.

6. Conclusion: The initial assumption must be false, thus every integer greater than 1 can be factored into primes.

Uniqueness of Prime Factorization

This part shows that the prime factorization of any integer greater than 1 is unique, except for the order in which the prime factors are written. We again use proof by contradiction and rely on the following Lemma (proven below).

Proof:

1. Assumption (for contradiction): Suppose there is at least one integer greater than 1 with two distinct prime factorizations.

2. Well-ordering principle: Let $n$ be the smallest such integer. Then we can write:

   $n=p_1^{e_1}{p}_2^{e_2}\cdots p_k^{e_k}=q_1^{f_1}{q}_2^{f_2}\cdots q_l^{f_l}$

   where the $p_i$ and $q_j$ are prime numbers, and the $e_i$ and $f_j$ are positive integers. The two factorizations are assumed to be distinct.

3. Prime Divisibility: Since $p_1$ divides $n$, and $n=q_1^{f_1}{q}_2^{f_2}\cdots q_l^{f_l}$, $p_1$ must divide at least one of the $q_j$ (by Lemma 4.7). Because the $q_j$ are prime, this means $p_1$ must equal one of the $q_j$. Without loss of generality, let’s assume $p_1=q_1$.

4. Cancellation: We can divide both sides of the equation by $p_1=q_1$, obtaining:

   $p_1^{e_1-1}{p}_2^{e_2}\cdots p_k^{e_k}=q_1^{f_1-1}{q}_2^{f_2}\cdots q_l^{f_l}$

   This gives us a smaller integer with (potentially) two distinct prime factorizations.

5. Contradiction: This contradicts the assumption that $n$ was the smallest integer with two distinct prime factorizations.

6. Conclusion: The assumption must be false; therefore, the prime factorization of any integer greater than 1 is unique (up to ordering).

Lemma 4.7: Euclid’s Lemma

Lemma: If a prime $p$ divides a product $x_1{x}_2\cdots x_n$ of integers, then $p$ divides at least one of the $x_i$.

Proof (by induction): The base case ($n=1$) is trivial: If $p|x_1$, then $p$ divides $x_1$. For the inductive step, assume the lemma holds for products of $n$ integers. Consider a product of $n+1$ integers: $x_1{x}_2\cdots x_{n+1}$. If $p$ divides this product, then either $p$ divides $x_1{x}_2\cdots x_n$ (in which case, by the induction hypothesis, $p$ divides at least one of $x_1,x_2,\dots ,x_n$), or $p$ does not divide $x_1{x}_2\cdots x_n$. In the latter case, $\gcd (p,x_1{x}_2\cdots x_n)=1$, implying $p$ and $x_1{x}_2\cdots x_n$ are relatively prime. This implies that $p$ must divide $x_{n+1}$ (because otherwise, there is no way to get $p$ to divide the product $x_1{x}_2\cdots x_{n+1}$).

4.3.3 Expressing gcd and lcm

The greatest common divisor (gcd) and least common multiple (lcm) of two integers can be efficiently computed using their prime factorizations:

Let $a=p_1^{e_1}{p}_2^{e_2}\cdots p_k^{e_k}$ and $b=p_1^{f_1}{p}_2^{f_2}\cdots p_k^{f_k}$ be the prime factorizations of $a$ and $b$ (where some $e_i$ or $f_i$ might be 0 if a particular prime doesn’t appear in the factorization of $a$ or $b$).

Then:

$\gcd (a,b)=p_1^{\min (e_1,f_1)}{p}_2^{\min (e_2,f_2)}\cdots p_k^{\min (e_k,f_k)}$

$\text{lcm}(a,b)=p_1^{\max (e_1,f_1)}{p}_2^{\max (e_2,f_2)}\cdots p_k^{\max (e_k,f_k)}$

4.3.4 Non-triviality of Unique Factorization *

The unique factorization property doesn’t hold in all algebraic structures. This is why the Fundamental Theorem of Arithmetic is significant; it highlights a specific property that makes the integers unique.

Examples:

• Example 4.5 (Gaussian Integers): The Gaussian integers, $\mathbb{Z}[i]=\{a+bi|a,b\in \mathbb{Z}\}$, where $i=\sqrt{-1}$, do have unique factorization into irreducible elements.

• Example 4.6 (Twisted Gaussian Integers): The ring $\mathbb{Z}[\sqrt{-5}]=\{a+b\sqrt{-5}|a,b\in \mathbb{Z}\}$ does not have unique factorization into irreducible elements. For example: $6=2\times 3=(1+\sqrt{-5})(1-\sqrt{-5})$.

4.3.5 Irrationality of Roots *

Theorem 4.8: Irrationality of Non-Square Roots

Theorem: The square root of a positive integer $n$ is irrational unless $n$ is a perfect square (i.e., $n=c^2$ for some integer $c$).

Proof (by contradiction):

We will prove this theorem using proof by contradiction and the Fundamental Theorem of Arithmetic (unique prime factorization).

1. Assumption: Assume, for the sake of contradiction, that $\sqrt{n}$ is rational and $n$ is not a perfect square. This means we can express $\sqrt{n}$ as a fraction $\frac{a}{b}$, where $a$ and $b$ are integers, $b\ne 0$, and $\gcd (a,b)=1$ (meaning $a$ and $b$ are coprime – they share no common factors other than 1).

2. Squaring and Rearranging: Squaring both sides of the equation $\sqrt{n}=\frac{a}{b}$, we get:

   $n=\frac{a^2}{b^2}$

   Multiplying both sides by $b^2$, we obtain:

   $n{b}^2=a^2$

3. Prime Factorization: By the Fundamental Theorem of Arithmetic, both $a^2$ and $n{b}^2$ have unique prime factorizations. Consider a prime factor $p$ that appears in the prime factorization of $n$. Because $n$ is not a perfect square, the exponent of $p$ in the prime factorization of $n$ must be odd (otherwise $n$ would be a perfect square).

4. Exponent Analysis: Let $e$ be the exponent of $p$ in the prime factorization of $n$. Then the exponent of $p$ in the prime factorization of $n{b}^2$ is $e+2k$, where $k$ is the exponent of $p$ in $b$ (which may be 0). Since $e$ is odd, $e+2k$ is also odd.

   However, the exponent of $p$ in the prime factorization of $a^2$ must be even (because it’s a perfect square). This means that if $p$ is in the prime factorization of $a^2$, its exponent must be an even number.

5. Contradiction: We have arrived at a contradiction. The prime factorization of $n{b}^2$ contains an odd number of factors of $p$, while the prime factorization of $a^2$ contains an even number of factors of $p$. However, $n{b}^2=a^2$, so their prime factorizations must be identical. This contradiction arises from our initial assumption that $\sqrt{n}$ is rational and $n$ is not a perfect square.

6. Conclusion: Therefore, our initial assumption must be false. If $n$ is not a perfect square, then $\sqrt{n}$ must be irrational.

4.3.6 A Digression to Music Theory *

The ratios of frequencies in harmonious musical intervals often involve small integers (e.g., the octave is a 2:1 frequency ratio, a perfect fifth is approximately 3:2). The unique prime factorization of integers plays a significant role in the mathematical analysis and understanding of musical harmony. This is an unexpected and fascinating application of prime numbers.

4.4 Some Basic Facts About Primes *

TLDR: This section discusses the distribution of prime numbers and the computational challenges of primality testing, particularly relevant for cryptography where large prime numbers are crucial.

4.4.1 The Density of Primes

Prime numbers, while infinite, become increasingly sparse as we consider larger integers. Their distribution is a fascinating and complex area of number theory. While there’s no simple formula to predict exactly where the next prime will occur, the Prime Number Theorem provides an asymptotic approximation of their density.

The Prime Number Theorem:

The Prime Number Theorem states that the number of primes less than or equal to $x$, denoted by $\pi (x)$, is approximately $\frac{x}{\ln (x)}$ for large $x$. More precisely:

${\lim }_{x\to \infty }\frac{\pi (x)}{\frac{x}{\ln (x)}}=1$

This means that the probability that a randomly chosen large number is prime decreases as the number increases, although infinitely many prime numbers exist. This theorem is crucial for understanding the probability of finding a large prime for cryptographic applications. There are many other, more refined approximations for $\pi (x)$ available, some of which are quite accurate even for relatively small values of $x$.

Example 4.7:

The largest gap between two consecutive prime numbers below 100 is 8. These primes are 89 and 97. That is, the interval $[90,96]$ contains no primes.

4.4.2 Remarks on Primality Testing

Primality testing is the problem of determining whether a given integer is prime. While simple trial division can decide whether a number is prime, it’s highly inefficient for large numbers.

Efficient Primality Testing Algorithms:

Fortunately, sophisticated and efficient primality testing algorithms exist, particularly for determining whether a given number is composite (not prime). These algorithms are used extensively in areas like cryptography.

Probabilistic Primality Testing:

Probabilistic algorithms offer a tradeoff between speed and certainty. They don’t guarantee correctness but give high probability (with tunable accuracy) results.

Deterministic Primality Testing:

Deterministic algorithms guarantee a correct answer but may be slower than probabilistic ones. A notable result in this area was the proof that primality testing is in the complexity class P; this means there exist algorithms with polynomial runtime, making primality testing computationally feasible for arbitrarily large integers.

The Importance of Primality Testing for Cryptography:

Cryptography heavily relies on the difficulty of factoring large numbers and the relative ease of finding large primes. Cryptographic systems often involve generating large prime numbers, then relying on the computational infeasibility of factoring their product. Therefore, primality testing algorithms are a crucial part of cryptographic systems’ security.

Additional Points:

• The density of primes is a subject of ongoing mathematical research ; more precise and accurate approximations of $\pi (x)$ are constantly being developed.

• Sophisticated primality testing algorithms often leverage probabilistic methods to speed up the testing process, particularly for very large numbers. These algorithms don’t guarantee primality but offer very high probability of being correct.

• Finding large primes efficiently is itself a complex computational problem crucial to many cryptographic systems ; generating provably prime numbers using deterministic algorithms requires more computational effort than probabilistic methods.

4.5 Congruences and Modular Arithmetic

TLDR: This chapter introduces modular arithmetic, a system where we work with remainders after division. Key concepts include modular congruences, modular arithmetic operations, multiplicative inverses, and the powerful Chinese Remainder Theorem.

4.5.1 Modular Congruences

Definition:

Two integers $a$ and $b$ are congruent modulo $m$ (where $m$ is a positive integer), denoted $a\equiv b(\mathrm{mod}m)$, if and only if $m$ divides $(a-b)$. In other words, $a\equiv b(\mathrm{mod}m)$ if and only if $a-b=km$ for some integer $k$.

Examples:

• Example 4.10: $23\equiv 3(\mathrm{mod}5)$ because $23-3=20$, and $5|20$.

• Example 4.10: $54321\equiv 1(\mathrm{mod}10)$ because $54321-1=54320$, and $10|54320$.

• Example 4.12: Consider $n=84877\times 79683-28674\times 43879$. Is $n$ even or odd? We can determine this without computing $n$ directly:

  • $84877$ and $79683$ are odd; their product is odd.
  • $28674$ is even and $43879$ is odd; their product is even.
  • The difference between an odd number and an even number is odd. Therefore, $n$ is odd. Note that we used modular arithmetic ($(\mathrm{mod}2)$) implicitly.

Properties of Modular Congruence:

Modular congruence is an equivalence relation, satisfying:

1. Reflexive: $a\equiv a(\mathrm{mod}m)$ for all $a$. (Any number is congruent to itself.)
2. Symmetric: If $a\equiv b(\mathrm{mod}m)$, then $b\equiv a(\mathrm{mod}m)$. (If $a$ is congruent to $b$, then $b$ is congruent to $a$.)
3. Transitive: If $a\equiv b(\mathrm{mod}m)$ and $b\equiv c(\mathrm{mod}m)$, then $a\equiv c(\mathrm{mod}m)$. (If $a$ is congruent to $b$, and $b$ is congruent to $c$, then $a$ is congruent to $c$.)

This is proven in Lemma 4.13 which requires showing that the definition of congruence modulo m satisfies the definition of an equivalence relation.

Lemma 4.13: Modular Congruence is an Equivalence Relation

Statement: For any positive integer $m$, the relation $\equiv (\mathrm{mod}m)$ is an equivalence relation on the set of integers $\mathbb{Z}$.

Proof: To prove that $\equiv (\mathrm{mod}m)$ is an equivalence relation, we must show it satisfies the three properties of an equivalence relation: reflexivity, symmetry, and transitivity.

1. Reflexivity: We need to show that $a\equiv a(\mathrm{mod}m)$ for all integers $a$. This is trivially true since $a-a=0$, and $m|0$ for any $m$.

2. Symmetry: We need to show that if $a\equiv b(\mathrm{mod}m)$, then $b\equiv a(\mathrm{mod}m)$. If $a\equiv b(\mathrm{mod}m)$, then $a-b=km$ for some integer $k$. This means $b-a=(-k)m$, so $m|(b-a)$, which implies $b\equiv a(\mathrm{mod}m)$.

3. Transitivity: We need to show that if $a\equiv b(\mathrm{mod}m)$ and $b\equiv c(\mathrm{mod}m)$, then $a\equiv c(\mathrm{mod}m)$. If $a\equiv b(\mathrm{mod}m)$ and $b\equiv c(\mathrm{mod}m)$, then $a-b=km$ and $b-c=lm$ for some integers $k$ and $l$. Adding these equations gives: $(a-b)+(b-c)=a-c=km+lm=(k+l)m$. Therefore, $m|(a-c)$, so $a\equiv c(\mathrm{mod}m)$.

Since the relation $\equiv (\mathrm{mod}m)$ satisfies reflexivity, symmetry, and transitivity, it’s an equivalence relation.

Lemma 4.14: Compatibility of Modular Congruence with Arithmetic Operations

Statement: If $a\equiv b(\mathrm{mod}m)$ and $c\equiv d(\mathrm{mod}m)$, then:

1. $a+c\equiv b+d(\mathrm{mod}m)$
2. $ac\equiv bd(\mathrm{mod}m)$

Proof:

1. Addition: Since $a\equiv b(\mathrm{mod}m)$, we can write $a=b+km$ for some integer $k$. Similarly, $c=d+lm$ for some integer $l$. Adding these equations: $a+c=b+d+km+lm=b+d+m(k+l)$. This shows $m|(a+c-(b+d))$, thus $a+c\equiv b+d(\mathrm{mod}m)$.

2. Multiplication: Using the same expressions for $a$ and $c$ from above, we have: $ac=(b+km)(d+lm)=bd+b(lm)+k(dm)+kl{m}^2=bd+m(bl+kd+klm)$. This demonstrates that $m|(ac-bd)$, thus $ac\equiv bd(\mathrm{mod}m)$.

Corollary 4.15: Modular Arithmetic with Polynomials

Statement: Let $P(x_1,x_2,...,x_k)$ be a multivariate polynomial with integer coefficients. If $a_i\equiv b_i(\mathrm{mod}m)$ for all $i=1,2,...,k$, then $P(a_1,a_2,...,a_k)\equiv P(b_1,b_2,...,b_k)(\mathrm{mod}m)$.

Proof: The proof follows directly from Lemma 4.14. A polynomial is built up from addition and multiplication; because modular congruence preserves both addition and multiplication (Lemma 4.14), the congruence must hold for the entire polynomial.

These lemmas and the corollary formally demonstrate that modular arithmetic behaves predictably with the standard arithmetic operations. This is fundamental to many applications of modular arithmetic in computer science.

4.5.2 Modular Arithmetic

Definition:

Modular arithmetic is a system of arithmetic performed on the set of integers modulo $m$, denoted ${\mathbb{Z}}_m$, where $m$ is a positive integer. ${\mathbb{Z}}_m$ is typically represented as the set of remainders when integers are divided by $m$: ${\mathbb{Z}}_m=\{0,1,2,\dots ,m-1\}$. Arithmetic operations (addition, subtraction, multiplication) are performed, and the result is then reduced modulo $m$ (taking the remainder after division by $m$).

Examples:

• Example 4.13: Compute $7^{100}(\mathrm{mod}24)$. We have $7^2=49\equiv 1(\mathrm{mod}24)$. Therefore, $7^{100}=(7^2{)}^{50}\equiv 1^{50}\equiv 1(\mathrm{mod}24)$.

• Example 4.14: Using modular arithmetic to check calculations. Let’s verify $247\times 3158=780026$ using modulo 9:

  • $R_9(247)=R_9(2+4+7)=13\equiv 4(\mathrm{mod}9)$.
  • $R_9(3158)=R_9(3+1+5+8)=17\equiv 8(\mathrm{mod}9)$.
  • $R_9(247\times 3158)=R_9(4\times 8)=R_9(32)=5(\mathrm{mod}9)$.
  • $R_9(780026)=R_9(7+8+0+0+2+6)=23\equiv 5(\mathrm{mod}9)$.
  • The remainders match, suggesting the calculation is correct (though not guaranteeing it). This is a probabilistic check, not a proof.

Lemma 4.16: Connection Between Modular Congruence and Remainders

For any integers $a,b,m$ with $m\ge 1$:

(i) $a\equiv R_m(a)(\mathrm{mod}m)$ (ii) $a\equiv b(\mathrm{mod}m)⟺R_m(a)=R_m(b)$

Proof:

(i) By definition, $R_m(a)$ is the remainder when $a$ is divided by $m$. This means $a=qm+R_m(a)$ for some integer $q$. Then $a-R_m(a)=qm$, which means $m|(a-R_m(a))$, so $a\equiv R_m(a)(\mathrm{mod}m)$.

(ii) $(⟹)$: If $a\equiv b(\mathrm{mod}m)$, then $m|(a-b)$. Since $a=q_{1}m+R_m(a)$ and $b=q_{2}m+R_m(b)$ for integers $q_1,q_2$, we have $q_{1}m+R_m(a)-(q_{2}m+R_m(b))=(q_1-q_2)m$, so $R_m(a)-R_m(b)=(q_2-q_1)m$. Because both remainders are in $[0,m-1]$, their difference must also be divisible by $m$, which implies $R_m(a)=R_m(b)$.

$(⟸)$: If $R_m(a)=R_m(b)$, then $a=q_{1}m+R_m(a)$ and $b=q_{2}m+R_m(b)$ gives us $a-b=(q_1-q_2)m$, implying $m|(a-b)$. Hence, $a\equiv b(\mathrm{mod}m)$.

Corollary 4.17: Modular Arithmetic with Polynomials

Let $f(x_1,\dots ,x_k)$ be a multivariate polynomial with integer coefficients and $m\ge 1$. Then:

$R_m(f(a_1,\dots ,a_k))=R_m(f(R_m(a_1),\dots ,R_m(a_k)))$

Proof:

This follows directly from Lemma 4.14 and Lemma 4.16. Since polynomial evaluation involves only addition and multiplication, the congruence modulo $m$ is preserved at each step, reducing the complexity of the calculation.

4.5.3 Multiplicative Inverses

Definition:

The multiplicative inverse of an integer $a$ modulo $m$, denoted $a^{-1}(\mathrm{mod}m)$, is an integer $x$ such that $ax\equiv 1(\mathrm{mod}m)$.

Existence:

A multiplicative inverse exists if and only if $gcd(a,m)=1$ (Lemma 4.18).

Proof (of Lemma 4.18):

1. $(⟹)$: If $ax\equiv 1(\mathrm{mod}m)$ has a solution, then there exists an integer $k$ such that $ax=1+km$. Any common divisor of $a$ and $m$ would have to divide 1, hence $gcd(a,m)=1$.

2. $(⟸)$: If $gcd(a,m)=1$, then by Corollary 4.5, there exist integers $u$ and $v$ such that $ua+vm=1$. This implies $ua\equiv 1(\mathrm{mod}m)$. Therefore, $x\equiv u(\mathrm{mod}m)$ is a solution. Uniqueness is proven by considering another potential solution $x^{\prime }$ and showing it must be congruent to $x$ modulo $m$.

Example:

• Example 4.17: The multiplicative inverse of 5 modulo 13 is 8 since $5\times 8=40\equiv 1(\mathrm{mod}13)$.

4.5.4 The Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT) provides a way to solve systems of simultaneous congruences when the moduli are pairwise relatively prime.

Theorem 4.19 (Chinese Remainder Theorem):

Let $m_1,m_2,\dots ,m_r$ be pairwise relatively prime positive integers (meaning $\gcd (m_i,m_j)=1$ for all $i\ne j$), and let $M={\prod }_{i=1}^r{m}_i$. For any integers $a_1,a_2,\dots ,a_r$ such that $0\le a_i<m_i$ for all $i$, there exists a unique solution $x$, with $0\le x<M$, to the system of congruences:

$x\equiv a_1(\mathrm{mod}{m}_1)$ $x\equiv a_2(\mathrm{mod}{m}_2)$ $\dots$ $x\equiv a_r(\mathrm{mod}{m}_r)$

The Chinese Remainder Theorem (CRT) solves systems of simultaneous congruences where the moduli are pairwise relatively prime. Let’s break down the theorem and its proof step-by-step:

Proof:

The proof is constructive; it shows how to build the solution and then proves its uniqueness.

1. Construction of a Solution:

• (a) Define $M_i$: For each $i=1,\dots ,r$, let $M_i=M/m_i$. This represents the product of all moduli except $m_i$.

• (b) Find Multiplicative Inverses $N_i$: Since $\gcd (m_i,m_j)=1$ for all $i\ne j$, we have $\gcd (M_i,m_i)=1$. This ensures that $M_i$ has a multiplicative inverse modulo $m_i$. For each $i$, find an integer $N_i$ such that $M_i{N}_i\equiv 1(\mathrm{mod}{m}_i)$. This can be done efficiently using the Extended Euclidean Algorithm.

• (c) Construct the Solution: The solution $x$ is given by:

  $x={\sum }_{i=1}^r{a}_i{M}_i{N}_i$

  This formula is the core of the CRT. Each term in the sum contributes to the congruence modulo a specific $m_i$.

2. Verification (Showing the constructed $x$ is a solution):

We need to show that the $x$ constructed in step 1 satisfies all the given congruences. Let’s consider the congruence modulo $m_k$ for an arbitrary $k$:

$x={\sum }_{i=1}^r{a}_i{M}_i{N}_i\equiv a_k{M}_k{N}_k(\mathrm{mod}{m}_k)$

This congruence holds because for all $i\ne k$, $M_i$ contains $m_k$ as a factor, so $M_i\equiv 0(\mathrm{mod}{m}_k)$. Therefore, only the term $a_k{M}_k{N}_k$ remains in the sum. Since $M_k{N}_k\equiv 1(\mathrm{mod}{m}_k)$ (by construction), we have $x\equiv a_k(\mathrm{mod}{m}_k)$. This confirms that the constructed $x$ satisfies all the congruences.

3. Uniqueness of the Solution:

Let’s assume there are two solutions, $x$ and $x^{\prime }$, both satisfying $0\le x,x^{\prime }<M$ and the system of congruences. Then:

$x\equiv a_i(\mathrm{mod}{m}_i)$ and $x^{\prime }\equiv a_i(\mathrm{mod}{m}_i)$ for all $i=1,\dots ,r$.

This means that $m_i|(x-x^{\prime })$ for all $i$. Because the $m_i$ are pairwise relatively prime, their least common multiple is their product $M$. Thus, $M|(x-x^{\prime })$, which means $x\equiv x^{\prime }(\mathrm{mod}M)$. Since both $x$ and $x^{\prime }$ are in the range $[0,M-1)$, this implies $x=x^{\prime }$. This proves the uniqueness of the solution.

Examples:

Example 4.18: Find $x$ such that

Find $x$ such that:

• $x\equiv 1(\mathrm{mod}3)$
• $x\equiv 2(\mathrm{mod}4)$
• $x\equiv 4(\mathrm{mod}5)$

1. $M=3\times 4\times 5=60$
2. $M_1=60/3=20$, $M_2=60/4=15$, $M_3=60/5=12$
3. Find $N_i$:
   • $20N_1\equiv 1(\mathrm{mod}3)⟹2N_1\equiv 1(\mathrm{mod}3)⟹N_1\equiv 2(\mathrm{mod}3)$
   • $15N_2\equiv 1(\mathrm{mod}4)⟹3N_2\equiv 1(\mathrm{mod}4)⟹N_2\equiv 3(\mathrm{mod}4)$
   • $12N_3\equiv 1(\mathrm{mod}5)⟹2N_3\equiv 1(\mathrm{mod}5)⟹N_3\equiv 3(\mathrm{mod}5)$
4. $x=(1)(20)(2)+(2)(15)(3)+(4)(12)(3)=40+90+144=274$
5. $x\equiv 274\equiv 34(\mathrm{mod}60)$ (because $274=4(60)+34$)

Verification:

• $34\equiv 1(\mathrm{mod}3)$
• $34\equiv 2(\mathrm{mod}4)$
• $34\equiv 4(\mathrm{mod}5)$

The solution $x=34$ is unique in the range $[0,59]$.

Example 4.19: Evaluate

Compute $R_{35}(2^{1000})$. We can compute this modulo 5 and modulo 7 separately.

Since $2^4\equiv 1(\mathrm{mod}5)$, $2^{1000}=(2^4{)}^{250}\equiv 1^{250}\equiv 1(\mathrm{mod}5)$.

Since $2^3\equiv 1(\mathrm{mod}7)$, $2^{1000}=(2^3{)}^{333}\times 2\equiv 1^{333}\times 2\equiv 2(\mathrm{mod}7)$.

Using the Chinese Remainder Theorem with $m_1=5$ and $m_2=7$, we find $x\equiv 16(\mathrm{mod}35)$ because 16 is the unique integer in $[0,34]$ such that $x\equiv 1(\mathrm{mod}5)$ and $x\equiv 2(\mathrm{mod}7)$. Therefore, $R_{35}(2^{1000})=16$.

Example: Find $x$ such that

• $x\equiv 2(\mathrm{mod}3)$
• $x\equiv 3(\mathrm{mod}5)$
• $x\equiv 4(\mathrm{mod}7)$

1. $M=3\times 5\times 7=105$
2. $M_1=35$, $M_2=21$, $M_3=15$
3. $35N_1\equiv 1(\mathrm{mod}3)⟹2N_1\equiv 1(\mathrm{mod}3)⟹N_1\equiv 2(\mathrm{mod}3)$
4. $21N_2\equiv 1(\mathrm{mod}5)⟹N_2\equiv 1(\mathrm{mod}5)$
5. $15N_3\equiv 1(\mathrm{mod}7)⟹N_3\equiv 1(\mathrm{mod}7)$

$x\equiv (2)(35)(2)+(3)(21)(1)+(4)(15)(1)=140+63+60=263(\mathrm{mod}105)$

$x\equiv 263-2(105)\equiv 53(\mathrm{mod}105)$

Verify:

• $53=17(3)+2\equiv 2(\mathrm{mod}3)$
• $53=10(5)+3\equiv 3(\mathrm{mod}5)$
• $53=7(7)+4\equiv 4(\mathrm{mod}7)$

4.6 Application: Diffie-Hellman Key-Agreement

TLDR: The Diffie-Hellman key exchange is a cryptographic protocol enabling two parties to securely establish a shared secret key over an insecure channel, leveraging modular arithmetic and the computational difficulty of the discrete logarithm problem.

The Diffie-Hellman key agreement is a revolutionary cryptographic protocol that allows two parties (let’s call them Alice and Bob) to establish a shared secret key over an insecure channel, like the internet. Its security relies on the computational difficulty of the discrete logarithm problem.

The Protocol:

The protocol uses the following components:

1. A large prime number $p$: This is publicly known.

2. A generator $g$: An integer $g$ such that $g^x(\mathrm{mod}p)$ generates many values as $x$ ranges from 0 to $p-2$ (Technically, $g$ is a generator of the multiplicative group of integers modulo $p$, denoted as ${\mathbb{Z}}_p^{\ast }$.) This is also publicly known. This group is a cyclic group with order $p-1$.

3. Alice’s secret key $x_A$: A randomly chosen integer $x_A$ in the range $[0,p-2]$. This is private to Alice.

4. Bob’s secret key $x_B$: A randomly chosen integer $x_B$ in the range $[0,p-2]$. This is private to Bob.

Steps:

1. Alice computes: $y_A=g^{x_A}(\mathrm{mod}p)$. This is Alice’s public key.

2. Bob computes: $y_B=g^{x_B}(\mathrm{mod}p)$. This is Bob’s public key.

3. Alice and Bob exchange their public keys: They send $y_A$ and $y_B$ to each other over the insecure channel.

4. Alice computes: $k_{AB}=y_B^{x_A}(\mathrm{mod}p)$. This is the shared secret key.

5. Bob computes: $k_{BA}=y_A^{x_B}(\mathrm{mod}p)$. This is also the shared secret key.

Proof of Key Agreement:

The magic of Diffie-Hellman is that $k_{AB}$ and $k_{BA}$ are identical, even though the calculation of the shared secret uses the private keys only locally, on each side. We show that $k_{AB}=k_{BA}(\mathrm{mod}p)$:

$k_{AB}\equiv y_B^{x_A}\equiv (g^{x_B}{)}^{x_A}\equiv g^{x_A{x}_B}(\mathrm{mod}p)$.

$k_{BA}\equiv y_A^{x_B}\equiv (g^{x_A}{)}^{x_B}\equiv g^{x_A{x}_B}(\mathrm{mod}p)$.

Therefore, $k_{AB}\equiv k_{BA}(\mathrm{mod}p)$.

Security:

The security of Diffie-Hellman relies on the difficulty of solving the discrete logarithm problem—given $p$, $g$, and $y_A$ (or $y_B$), it’s computationally infeasible to find $x_A$ (or $x_B$) if the prime $p$ is sufficiently large. An eavesdropper can see the exchanged public keys ($y_A$ and $y_B$), but calculating the shared secret key $k$ requires solving the discrete logarithm problem, which is computationally intractable.

Mechanical Analogy:

Imagine two padlocks. Alice and Bob each have a padlock with a unique key. They send their locked padlocks to each other, each person keeping their key secret. Alice uses Bob’s lock to secure a shared box. Bob uses Alice’s lock to secure the same shared box, using his own private key. An eavesdropper can observe the padlocks (public keys), but without the corresponding keys, cannot open the box (access the shared secret).