4. Number Theory and Crytography

Number theory is the part of mathematics devoted to the study of the integers and their properties.
💡 这些都是初中奥数的知识了，看看英文怎么表达基本上就能搞定。

4.1 Divisibility and Modular Arithmetic

4.1.1 Division

If and are integers with , then **divides** if there exists an integer such that , or equivalently , denoted by . When divides , we say that is a **factor** or **divisor** of and that is a **multiple** of . If does not divide , we write .
📋 Properties of Divisibility
Let , , and be integers, where .

• If and , then whenever ;
• If , then for all integers ;
• If and , then .

📋 Division Algorithm
If is an integer and a positive integer, then there are unique integers and , with , such that . Here is called the **divisor**, is called the **dividend**, is called the **quotient**, is called the **remainder**. The notation is and .
⚠️ Note that the remainder cannot be negative. , .+

4.1.2 Congruence

**Congruence Relation** If and are integers and is a positive integer, then is congruent to modulo if , denoted by . We say that is a **congruence** and that is its **modulus**. If is not congruent to modulo , we write .
📋 Two integers are congruent mod if and only if they have the same remainder when divided by , or equivalently there is an integer such that .
📋 Let and be integers, and let be a positive integer. Then .
⚠️ The use of “mod” in and _ _are different. is a relation on the set of integers, while in , the notation denotes a function.
📋 Congruences of Sums and Products
Let be a positive integer.
If and ,
then and .
Corollary: Let be a positive integer and let and be integers, then


📋 Algebraic Manipulation of Congruences

• Multiplying both sides of a valid congruence by an integer preserves validity.
  • If holds, then , where is any integer, holds by the theorem of congruences of products with .

• Adding an integer to both sides of a valid congruence preserves validity.

  • If holds then , where is any integer, holds by the theorem of congruences of sums with .

    4.1.3 Arithmetic Modulo

    The operation is defined as . This is **addition modulo m**.
    The operation is defined as . This is **multiplication modulo m**.
    Using these operations is said to be doing **arithmetic modulo m**.
    Let be the set of nonnegative integers less than . That is .
    🌰 e.g.
    7 +11 9 = (7 + 9) mod 11 = 5
    9 ·11 7 = (9 · 7) mod 11 = 8
    📋 The operations and satisfy many of the same properties as ordinary addition and multiplication.

• Closure:

• Associativity:
• Commutativity:
• Identity elements: The elements 0 and 1 are identity elements for addition and multiplication modulo , respectively. If belongs to , then and .
• Additive inverses: If belongs to , then (⚠️ not because it is not in ) is the additive inverse of a modulo and 0 is its own additive inverse. and .
• Distributivity: If , then and

⚠️ Multiplicatative inverses have not been included since they do not always exist. For example, there is no multiplicative inverse of 2 modulo 6.

4.2 节没什么知识，跳过了。

4.3 Primes and GCDs

4.3.1 Primes

A positive integer greater than 1 is called **prime** if the only positive factors of are 1 and . A positive integer that is greater than 1 and is not prime is called **composite**.
📋 The Foundamental Theorm of Arithmetic
Every positive 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.
📋 Trial division
Trial division, a very inefficient method of determining if a number n is prime, is to try every integer and see if is divisible by . This is because if an integer is a composite integer, then it has a prime divisor less than or equal to . To see this, note that if , then or .
📋 Infinitude of Primes (proof by Eucluid)
There are infinitely many primes.
Proof:
Assume finitely many primes: .
Let _, _then is a prime not in the list of all the primes.
So there are infinitely many primes.

4.3.2 GCD and LCM

Let and be integers, not both zero. The largest integer such that and also is called the **greatest common divisor (GCD)** of and . The greatest common divisor of and is denoted by .
The **least common multiple (LCM)** of the positive integers and is the smallest positive integer that is divisible by both and . It is denoted by .
The integers and are **relatively prime** if their greatest common divisor is 1. The integers are **pairwise relatively prime** if whenever .
📋 Finding GCDs and LCMs Using Prime Factorizations
Suppose the prime factorizations of and are:

where each exponent is a nonnegative integer, and where all primes occurring in either prime factorization are included in both. Then:


📋 Let and be positive integers. Then .
📋 Euclidean Algorithm（辗转相除法）
The Euclidian algorithm is an efficient method for computing the greatest common divisor of two integers. It is based on the idea that is equal to when and is the remainder when is divided by .
The Euclidean algorithm expressed in pseudocode is:

📋 Bézout’s Theorem（裴蜀定理）
If and are positive integers, then there exist integers and such that . Integers and such that are called **Bézout coefficients** of and . The equation is called **Bézout's identity**（裴蜀恒等式）. To find Bézout coefficients, first use the Euclidian algorithm to find the gcd, and then works backwards to express the gcd as a linear combination of the original two integers.

🌰 e.g.
Express as a linear combination of 252 and 198.

📋 If , , and are positive integers such that and , then .
Proof:
Since , by Bézout’s Theorem there are integers and such that . Multiplying both sides of the equation by , yields .
Since and , we can conclude that .
📋If p is prime and p | a1a2…a__n, then p | a__i for some i.
(Proof uses mathematical induction. It is crucial in the proof of the uniqueness of prime factorizations.)
📋A prime factorization of a positive integer where the primes are in nondecreasing order is unique.

📋Let m be a positive integer and let a, b, and c be integers. If ac ≡ bc (mod m) and gcd(c, m) = 1, then a ≡ b (mod m).
Proof: Since ac ≡ bc (mod m), m | ac − bc = c(a − b) and the fact that gcd(c, m) = 1, it follows that m | a−b. Hence, a ≡ b (mod m).

4.4 Solving Congruences

4.4.1 Linear Congruences

A congruence of the form ax ≡ b (mod m), where m is a positive integer, a and b are integers, and x is a variable, is called a **linear congruence**. The solutions to a linear congruence ax ≡ b(mod m) are all integers x that satisfy the congruence.
An integer ā such that āa ≡ 1(mod m) is said to be an **inverse** of a modulo m.
The Euclidean algorithm and Bézout coefficients gives us a systematic approaches to finding inverses.
📋If a and m are relatively prime integers and m > 1, then an inverse of a modulo m exists. Furthermore, this inverse is unique modulo m. (This means that there is a unique positive integer ā less than m that is an inverse of a modulo m and every other inverse of a modulo m is congruent to ā modulo m.)
Proof:
Since gcd(a, m) = 1, there exist integers s and t such that sa + tm = 1. Hence, sa + tm ≡ 1(mod m). Since tm ≡ 0(mod m), it follows that sa ≡ 1(mod m). Consequently, s is an inverse of a modulo m.
📋Finding Inverses
The Euclidean algorithm and Bézout coefficients gives us a systematic approaches to finding inverses.
🌰e.g.
Find an inverse of 3 modulo 7.
Solution:
3 and 7 are relatively prime, so there exist an inverse of 3 modulo 7. Using the Euclidian algorithm: 7 = 2 × 3 + 1, so -2 and 7 are Bézout coefficients of 3 and 7.
-2 × 3 + 1 × 7 = 1, and -2 × 3 + 1 × 7 ≡ -2 × 3 (mod 7), so -2 is an inverse of 3 modulo 7. And every integer congruent to -2 modulo 7 is an inverse of 3 modulo 7.
📋Solving Congruences Using Inverses
We can solve the congruence ax ≡ b(mod m) by multiplying both sides by ā.
🌰e.g.
What are the solutions of the congruence 3x ≡ 4(mod 7) ?
Solution:
-2 is an inverse of 3 modulo 7, so multiply both sides of the congruence by -2 giving -2 × 3x ≡ -2 × 4(mod 7). _Because −6 ≡ 1 (mod 7) and −8 ≡ 6 (mod 7), it follows that if _x is a solution, then x ≡ −8 ≡ 6 (mod 7).
We need to determine if every x with x ≡ 6 (mod 7) is a solution. Multiply both sides by 3 and get 3x ≡ 18 ≡ 4(mod 7), _which shows that all such _x satisfy the congruence.
📋Solving Systems of Linear Congruences Using Back Substitution
Substitute the value for the variable into another congruence, and continuing the process until we have worked through all the congruences.
🌰e.g.
Use the method of back substitution to find all integers x such that x ≡ 1 (mod 5), x ≡ 2 (mod 6), and x ≡ 3 (mod 7).
Solution:
The first congruence can be rewritten as x = 5t +1, t ∈ ℤ.
Substituting into the second congruence yields 5t +1 ≡ 2 (mod 6). Solving this tells us that t ≡ 5 (mod 6). So t = 6u + 5, u ∈ ℤ. Substituting this back into x = 5t +1, gives x = 5(6u + 5) +1 = 30u + 26.
Inserting this into the third equation gives 30u + 26 ≡ 3 (mod 7). Solving this congruence tells us that u ≡ 6 (mod 7). So u = 7v + 6, v ∈ ℤ. Substituting this expression for u into x = 30u + 26, tells us that x = 30(7v + 6) + 26 = 210u + 206.
Translating this back into a congruence we find the solution x ≡ 206 (mod 210).

4.4.2 The Chinese Remainder Theorem

It is a different method to solve a system of linear congruences.
📋The Chinese Remainder Theorem
Let m1, m2, … , m__n be pairwise relatively prime positive integers greater than 1 and a1, a2, … , a__n arbitrary integers. Then the system:

has a unique solution modulo m = m1 × m2 × … × m__n. (That is, there is a solution x with 0 ≤ x < m and all other solutions are congruent modulo m to this solution.)
Proof:
It is a constructive proof.
First let Mk = m/m__k for k = 1, 2, … , n. Since gcd(mk, Mk) = 1, there is an integer y__k, an inverse of M__k modulo m__k, such that Mkyk ≡ 1 (mod mk). Form the sum x = a1M1y1 + a2M2y2 + … + anMny__n. Note that because Mj ≡ 0 (mod mk) whenever j ≠ k, all terms except the k-th term in this sum are congruent to 0 modulo m__k. Because Mkyk ≡ 1(mod mk), we see that x ≡ akMkyk ≡ ak(mod mk), for k = 1, 2, … , n. Hence, x is a simultaneous solution to the n congruences.

🌰e.g.
有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？（《孙子算经》）
Solution:
x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7).
m = 3×5×7 = 105, M1 = m/3 = 35, M2 = m/5 = 21, M3 = m/7 = 15.
2 is an inverse of M1 modulo 3, 1 is an inverse of M2 modulo 5, 1 is an inverse of M3 modulo 7.
Hence, x = a1M1y1 + a2M2y2 + a3M3y3 = 2×_35×2 + 3×21×1 + 2×15×_1 = 233 ≡ 23 (mod 105). So 23 is the smallest positive integer that is a simultaneous solution.
⚙️It is important to solve systems of linear congruences. Computers sometime store big integers in the form of theirs remainders and moduli.

4.4.3 Fermat’s Little Theorem

📋Fermat’s Little Theorem
If p is prime and a is an integer not divisible by p, then ap-1 ≡ 1 (mod p). Furthermore, for every integer a, no matter if it is divisible by p, we have ap ≡ a (mod p).
Proof:

⚙️Fermat’s little theorem is useful in computing the remainders modulo p of large powers of integers.
🌰e.g.
Find 7222 mod 11.
Solution:
By Fermat’s little theorem, we know that 710 ≡ 1 (mod 11), and so (710)k ≡1 (mod 11), for every positive integer k. Therefore, 7222 = 722∙10 + 2 = (710)22×72 ≡ (1)22×49 ≡ 5 (mod 11). Hence, 7222 mod 11 = 5.
A number p not satisfying Fermat’s Little Theorem must be a composite, but not every p satisfying Fermat’s Little Theorem is a prime. Let b be a positive integer. If n is a composite integer, and bn-1 ≡ 1 (mod n), then n is called a **pseudoprime** to the **base** b. Among the positive integers not exceeding a positive real number x, compared to primes, there are relatively few pseudoprimes to the base b.
🌰e.g.
Show that 341 is a pseudoprime to the base 2.
Proof:
341 = 11 ∙ 31, so 341 is a composite. 2340 ≡ 1 (mod 341), so it is a pseudoprime.
We can replace 2 by any integer b ≥ 2 as well.
There are composite integers n that pass all tests with bases b such that gcd(b, n) = 1. A composite integer n that satisfies the congruence bn-1 ≡ 1 (mod n) for all positive integers b with gcd(b, n) = 1 is called a **Carmichael number**.
🌰e.g.
Show that 561 is a Carmichael number.
Proof:
561 is composite, since 561 = 3 ∙ 11 ∙ 13.
If gcd(b, 561) = 1, then gcd(b, 3) = gcd(b, 11) = gcd(b, 17) = 1.
Using Fermat’s Little Theorem: b2 ≡ 1 (mod 3), b10 ≡ 1 (mod 11), b16 ≡ 1 (mod17).
Then

It follows that b560 ≡ 1 (mod 561) for all positive integers b with gcd(b,561) = 1. Hence, 561 is a Carmichael number.