Pmath 340 lecture notes 2 PDF

Preview

Summary

Course note...

Description

PMATH 340 Lecture Notes on Elementary Number Theory Anton Mosunov Department of Pure Mathematics University of Waterloo Winter, 2017

Contents 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

17 18 19

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Divisibility. Factorization of Integers. The Fundamental Theorem of Arithmetic . . . . . . . . . . . . . Greatest Common Divisor. Least Common Multiple. B´ezout’s Lemma. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Diophantine Equations. The Linear Diophantine Equation ax + by = c . . . . . . . . . . . Euclidean Algorithm. Extended Euclidean Algorithm . . . . . . . Congruences. The Double-and-Add Algorithm . . . . . . . . . . . . . . . . . . The Ring of Residue Classes Zn . . . . . . . . . . . . . . . . . . Linear Congruences . . . . . . . . . . . . . . . . . . . . . . . . . The Group of Units Zn⋆ . . . . . . . . . . . . . . . . . . . . . . . Euler’s Theorem and Fermat’s Little Theorem . . . . . . . . . . . The Chinese Remainder Theorem . . . . . . . . . . . . . . . . . Polynomial Congruences . . . . . . . . . . . . . . . . . . . . . . The Discrete Logarithm Problem. The Order of Elements in Zn⋆ . . . . . . . . . . . . . . . . . . . . The Primitive Root Theorem . . . . . . . . . . . . . . . . . . . . Big-O Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . Primality Testing . . . . . . . . . . . . . . . . . . . . . . . . . . 16.1 Trial Division . . . . . . . . . . . . . . . . . . . . . . . . 16.2 Fermat’s Primality Test . . . . . . . . . . . . . . . . . . . 16.3 Miller-Rabin Primality Test . . . . . . . . . . . . . . . . Public Key Cryptosystems. The RSA Cryptosystem . . . . . . . . . . . . . . . . . . . . . . . The Diffie-Hellman Key Exchange Protocol . . . . . . . . . . . . Integer Factorization . . . . . . . . . . . . . . . . . . . . . . . . 1

3 5 9 15 18 23 28 31 32 35 38 40 45 50 52 55 56 58 60 62 67 68

20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

19.1 Fermat’s Factorization Method . . . . . . . . . . . . . . . 69 19.2 Dixon’s Factorization Method . . . . . . . . . . . . . . . 72 Quadratic Residues . . . . . . . . . . . . . . . . . . . . . . . . . 74 The Law of Quadratic Reciprocity . . . . . . . . . . . . . . . . . 81 Multiplicative Functions . . . . . . . . . . . . . . . . . . . . . . 85 The M¨obius Inversion . . . . . . . . . . . . . . . . . . . . . . . . 91 The Prime Number Theorem . . . . . . . . . . . . . . . . . . . . 95 The Density of Squarefree Numbers . . . . . . . . . . . . . . . . 96 Perfect Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . 101 Pythagorean Triples . . . . . . . . . . . . . . . . . . . . . . . . . 104 Fermat’s Infinite Descent. Fermat’s Last Theorem . . . . . . . . . . . . . . . . . . . . . . . 105 Gaussian Integers . . . . . . . . . . . . . . . . . . . . . . . . . . 110 Fermat’s Theorem on Sums of Two Squares . . . . . . . . . . . . 120 Continued Fractions . . . . . . . . . . . . . . . . . . . . . . . . . 124 The Pell’s Equation . . . . . . . . . . . . . . . . . . . . . . . . . 134 Algebraic and Transcendental Numbers. Liouville’s Approximation Theorem . . . . . . . . . . . . . . . . 136 Elliptic Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . 140

2

1 Introduction This is a course on number theory, undoubtedly the oldest mathematical discipline known to the world. Number theory studies the properties of numbers. These may be integers, like √ −2, 0 or 7, or rational numbers like 1/3 or −7/9, or algebraic numbers like 2 or i, or transcendental numbers like e or π. Though most of the course will be dedicated to Elementary Number Theory, which studies congruences and various divisibility properties of the integers, we will also dedicate several lectures to Analytic Number Theory, Algebraic Number Theory, and other subareas of number theory. There are many interesting questions that one might ask about numbers. In search for answers to these questions mathematicians unravel fascinating properties of numbers, some of which are quite profound. Here are several curious facts about prime numbers: 1. Every odd number exceeding 5 can be expressed as a sum of three primes (Helfgott’s Theorem, 2013); 2. There are infinitely many prime numbers p and q such that |p − q| ≤ 264 (Zhang’s Theorem, 2013. Zhang proved the result for 7 · 106 , and the constant was reduced to 264 by Maynard, Tao, Konyagin and Ford); 3. There always exists a prime between two consecutive perfect cubes (Ingham’s Theorem, 1937); 4. There are infinitely many primes of the form x2 + y4 (Friedlander-Iwaniec Theorem, 1997); 5. Up to x > 1, there are “approximately” x/ logx prime numbers (Prime Number Theorem, 1896); 6. Given a positive integer d, there exist distinct prime numbers p1 , p2 , . . . , pd which form an arithmetic progression (Green-Tao Theorem, 2004). Despite the simplicity of their formulations, all of these results are highly nontrivial and their proofs reside on some deep theories. For example, the Green-Tao Theorem resides on Szemer´edi’s Theorem, which in turn uses the theory of random graphs. There are many number theoretical problems out there that are still open. At the 1912 International Congress of Mathematicians, the German mathematician 3

Edmund Landau listed the following four basic problems about primes that still remain unresolved: 1. Can every even integer greater than 2 be written as a sum of two primes? (Goldbach’s Conjecture, 1742); 2. Are there infinitely many prime numbers p and q such that |p − q| = 2? (Twin Prime Conjecture, 1849); 3. Does there always exist a prime between two consecutive perfect squares? (Legendre’s Conjecture, circa 1800); 4. Are there infinitely many primes of the form n2 + 1? (see Bunyakovsky’s Conjecture, 1857). It is widely believed that the answer to each of the questions above is “yes”. There is a lot of computational evidence towards each of them, and for some of them conjectural asymptotic formulas were established. However, none of them are proved. Aside from being an interesting theoretical subject, number theory also has many practical applications. It is widely used in cryptographic protocols, such as RSA (Rivest-Shamir-Adleman, 1977), the Diffie-Hellman protocol (1976), and ECIES (Elliptic Curve Integrated Encryption Scheme). These protocols rely on certain fundamental properties of finite fields (RSA, D-H) and elliptic curves defined over them (ECIES). For example, consider the Discrete Logarithm Problem: given a prime p and integers c, m, one may ask whether there exists an integer d such that cd − m is divisible by p, and if so, what is its value. We may write this in the form of a congruence cd ≡ m (mod p). When p is extremely large (hundreds of digits) and c, m are chosen properly, this problem is widely believed to be intractable; that is, no modern computer can solve it in a reasonable amount of time (the computation would require billions of years). This property is used in many cryptosystems, including the first two mentioned above. Many cryptosystems, like RSA, can be broken by quantum computers. The construction of protocols infeasible to attacks by quantum computers is a subject of Post Quantum Cryptography and number theory plays a crucial role there (see the Lattice-Based or Isogeny-Based Cryptography). 4

2

Divisibility. Factorization of Integers. The Fundamental Theorem of Arithmetic

Before we proceed, let us invoke a little bit of notation: N = {1, 2, 3, . . .} — the natural numbers; Z = {0, ±1, ±2, . . .} —the ring of integers; Q = nm : m ∈ Z, n ∈ N — the field of fractions; R — the field of real numbers; C = {a + bi : a, b ∈ R, i2 = −1} — the field of complex numbers. We call Z a ring because 0, 1 ∈ Z and a, b ∈ Z implies a ± b ∈ Z and a · b ∈ Z. In other words, Z is closed under addition, subtraction and multiplication. Note, however, that a, b ∈ Z with b 6= 0 does not imply that a/b ∈ Z, so it is not closed under division. A collection that is closed under addition, subtraction, multiplication and division by a non-zero element is called a field. According to this definition, every field is also a ring. Exercise 2.1. Demonstrate the proper inclusions in N ( Z ( Q ( R ( C. No proofs are required. Definition 2.2. Let a, b ∈ Z. We say that a divides b, or that a is a factor of b, when b = ak for some k ∈ Z. We write a | b if this is the case, and a ∤ b otherwise. Example 2.3. 3 | 12 because 12 = 3 · 4; 3 ∤ 13; −1 | 7 because 7 = (−1) · (−7); 0 ∤ 3. Proposition 2.4.

1

Let a, b, c, x, y ∈ Z.

1. If a | b and b | c, then a | c; 2. If c | a and c | b, then c | ax ± by; 3. If c | a and c ∤ b, then c ∤ a ± b; 4. If a | b and b 6= 0, then |a| ≤ |b|; 5. If a | b and b | a, then a = ±b; 1 Proposition

1.2 in Frank Zorzitto, A Taste of Number Theory.

5

6. If a | b, then ±a | ±b; 7. 1 | a for all a ∈ Z; 8. a | 0 for all a ∈ Z; 9. 0 | a if and only if a = 0. Proof. Exercise. Definition 2.5. Let p ≥ 2 be a natural number. Then p is called prime if the only positive integers that divide p are 1 and p itself. It is called composite otherwise. We remark that 1 is neither prime nor composite. We will also use the above terminology only with respect to integers exceeding 1 (so according to this convention −3 is not prime and −6 is not composite). Exercise 2.6. Among the collection −5, 1, 5, 6, which numbers are prime? Theorem 2.7. For each integer n ≥ 2 there exists a prime p such that p | n. Proof. We will prove this result using strong induction on n. Base case. For n = 2 we have 2 | n. Since 2 is prime, the theorem holds. Induction hypothesis. Suppose that the theorem is true for n = 2, 3, . . . , k. Induction step. We will show that the theorem is true for n = k + 1. If n is prime the result holds. Otherwise there exists a positive integer d such that d | n, d 6= 1 and d 6= n. By property 4 of Proposition 2.4 we have d ≤ n, and since d 6= 1 and d 6= n we conclude that 2 ≤ d ≤ n − 1 = k. Thus d satisfies the induction hypothesis, so there exists a prime p such that p | d. Since p | d and d | n, by property 1 of Proposition 2.4 we conclude that p | n. Theorem 2.8. (Euclid’s Theorem, circa 300BC) There are infinitely many prime numbers. Proof. Suppose not, and there are only finitely many prime numbers, say p1 , p2 , . . . , pk . Consider the number q = p1 p2 · · · pk + 1. Since q ≥ 2, by Theorem 2.7 there exists some prime, say pi , which divides q. On the other hand, since pi | p1 p2 · · · pk and pi ∤ 1, by property 3 of Proposition 2.4 it is the case that pi ∤ q. This leads us to a contradiction. Hence there are infinitely many prime numbers. 6

os, There are many alternative proofs of this fact, suggested by Euler, Erd˝ Furstenberg, and other mathematicians (see the wikipedia page for Euclid’s Theorem). At the end of this section, we will see the proof given by Euler. We will now turn our attention to the Fundamental Theorem of Arithmetic, which states that any integer greater than 1 can be written uniquely (up to reordering) as the product of primes. Example 2.9. Number 60 can be written as 60 = 22 · 3 · 5. In order to prove the theorem, we will utilize the following tools: 1. Well-Ordering Principle. Let S be a non-empty subset of the natural numbers N. Then S contains the smallest element. To spell it out, there exists x ∈ S such that the inequality x ≤ y holds for any y ∈ S. 2. Generalized Euclid’s Lemma.2 Let p be a prime number and a1 , a2 , . . . , ak be integers. If p | a1 a2 · · · ak , then there exists an index i, 1 ≤ i ≤ k, such that p | ai . Theorem 2.10. (The Fundamental Theorem of Arithmetic) Any integer greater than 1 can be written uniquely (up to reordering) as the product of primes. Proof. We will start by proving that every positive integer greater than 1 can be written as a product of primes. Let S denote the collection of all positive integers greater than 1 that cannot be written as a product of primes. Suppose that S is not empty. Since S ( N and N is well-ordered, we conclude that S contains the smallest element, say n. Clearly, n is not a prime. Thus there exists a positive integer d such that d | n, d 6= 1 and d 6= n. Thus both d and n/d are strictly less than n and greater than 1. Furthermore, either d or n/d cannot be written as a product of primes, for the converse would imply that n is a product of primes. Thus either d or n/d is in S, which contradicts the fact that n is the smallest element in S. This means that S is empty, so every integer greater than 1 is a product of primes. To prove uniqueness, consider two prime power decompositions a

b

n = p1a1 p22 · · · pak k = qb11 q2 2 · · · qbℓℓ . We will show that they are in fact the same.3 Without loss of generality, we may assume that p1 < p2 < . . . < pk and q1 < q2 < . . . < qℓ . Pick some index i such 2 We will prove this result in Corollary 3.15 once we will introduce the notion of a greatest common divisor. 3 Note that this is not the proof by contradiction, for we do not assume that these prime power decompositions are distinct.

7

that 1 ≤ i ≤ k. Since pi | n = qb11 qb22 · · · qbℓ ℓ , by Generalized Euclid’s Lemma there exists some index j(i), 1 ≤ j(i) ≤ ℓ, such that b

j(i) . pi | q j(i)

Now apply Generalized Euclid’s Lemma once again to deduce that pi | q j(i) . Since q j(i) is prime, its only divisors are 1 and q j(i) , which means that pi = q j(i) . Since p1 < p2 < . . . < pk , we see that j(i1 ) 6= j(i2 ) whenever i1 6= i2 . From above we conclude that for each i such that 1 ≤ i ≤ k we can put in correspondence some element j(i) — and each j(i) arises from unique i — such that 1 ≤ j(i) ≤ ℓ, which means that there are at least as many j’s as there are i’s, so k ≤ ℓ. Apply Generalized Euclid’s Lemma once again, but with the roles of pi and q j reversed, thus observing that for each j such that 1 ≤ j ≤ ℓ we can put in correspondence some element i( j) — and each i( j) arises from unique j — such that 1 ≤ i( j) ≤ ℓ, so ℓ ≤ k. Since k ≤ ℓ and ℓ ≤ k, it is the case that k = ℓ. From here we deduce that piai | qibi and qibi | piai. By property 5 of Proposition 2.4, we have piai = qbi i . Since pi = qi , it is the case that ai = bi . The fact that the prime factorization is unique was utilized by Euler to provide an alternative proof of Euclid’s Theorem. Theorem 2.9. (Euclid’s Theorem, circa 300BC) There are infinitely many prime numbers. Proof. (Euler’s proof, 1700’s) Consider the harmonic series ∞

1

1

1

∑ n = 1 + 2 + 3 + ....

n=1

It is widely known that this series is divergent. Now let p > 1 and recall the formula for the infinite geometric series: ∞

∑ k=0

1 1 1 1 = 1 + + 2 +... = . k p 1 − 1/p p p

Using this formula, we observe that   ∞ 1 1 1 1 ∏ 1 − 1/p = ∏ 1 + p + p2 + . . . = ∑ n , n=1 p prime p prime 8

where the last equality holds by the Fundamental Theorem of Arithmetic. If there would be only finitely many primes, the product on the left hand side would be finite, which contradicts the fact that the series on the right hand side is divergent.

3

Greatest Common Divisor. Least Common Multiple. B´ezout’s Lemma.

When divisibility fails, we speak of quotients and remainders. Theorem 3.1. (The Remainder Theorem)4 Let a, b be integers, a > 0. Then there exist unique integers q and r such that b = aq + r, where 0 ≤ r < a. Proof. Recall that every real number x “sits” in between two consecutive integers; that is, there exists some unique integer q such that q ≤ x < q + 1. Now set x = b/a. Then from above inequality it follows that aq ≤ b < aq + a. But then 0 ≤ b − aq < a. If we now put r = b − aq, then b = aq + r and r satisfies 0 ≤ r < a. From the above construction it is also evident that q and r are unique, so the result follows. Definition 3.2. Let a, b be integers, a > 0. Write b = aq + r, where 0 ≤ r < a. Then a is called the modulus, b is called the dividend, q is called the quotient and r is called the remainder. 4 Proposition

1.3 in Frank Zorzitto, A Taste of Number Theory.

9

Note that for a > 0 the expression a | b simply means that in b = aq + r the remainder r is equal to zero. Given a and b, one can easily compute q and r using the calculator. First, compute a/b, and the integer part of this expression is precisely your q. Then compute r with the formula r = b − aq. Definition 3.3. Let a and b be integers. An integer d such that d | a and d | b is called a common divisor of a and b. When at least one of a and b is not zero, the largest integer with such a property is called the greatest common divisor of a and b and is denoted by gcd(a, b). When a = b = 0, we define gcd(a, b) := 0. The greatest common divisor of a and b possesses many interesting properties. Let us demonstrate several of them. Proposition 3.4. Let f

e

f

a = pe11 p22 · · · pekk and b = p1f 1 p 22 · · · p kk , where p1 , p2 , . . . , pk are distinct prime numbers and e1 , e2 , . . . , ek , f1 , f2 , . . . , fk are integers ≥ 0. Then min{e1 , f 1 } min{e2 , f 2 } min{e , f } p2 ··· pk k k .

gcd(a, b) = p1

(1)

Further, any common divisor c of a and b must also divide gcd(a, b). Proof. Note that min{ek , f k } min{e1 , f 1 } min{e2 , f 2 } p2 · · · pk

g = p1

divides both a and b. Also, any integer g

g

c = pg11 p2 2 · · · p kk such that gi > min{ai , bi } for some i fails to divide either a or b. Hence any common divisor c satisfies gi ≤ min{ai , bi } for all i, 1 ≤ i ≤ k. Hence c divides g. Maximizing the inequality for each index we get that g is in fact the greatest common divisor. Note that Proposition 3.4 suggests one formula for the computation of gcd(a, b). First, one has to factor a and b by writing them in the form f

e

f

a = pe11 p22 · · · pekk and b = p1f 1 p 22 · · · p kk , 10

where the indices ei and f j are allowed to be 0 (convince yourself that any two numbers can be written in this form). Then one might simply utilize the formula (1). This approach works fine when the numbers are small and easily factorable, but unfortunately as the numbers get really large the efficient factorization is infeasible for modern electronic computers (but feasible for quantum computers, see Shor’s Algorithm). In fact, the security of the RSA public key cryptosystem is based on the difficulty of factorization. Example 3.5. Let us compute the greatest common divisor of 440 and 300. The prime factorizations are 440 = 23 · 5 · 11 and 300 = 22 · 3 · 52 . We see that 440 = 23 · 30 · 51 · 111 and 300 = 22 · 31 · 52 · 110 .

Thus gcd(440, 300) = 2min{3,2} · 3min{0,1} · 5min{1,2} · 11min{1,0} = 22 · 30 · 51 · 110 = 20. Exercise 3.6. Let a and b be integers. An integer ℓ is called a common multiple of a and b if it satisfies a | ℓ and b | ℓ. The smallest non-negative integer with such a property is called the least common multiple of a and b and is denoted by lcm(a, b). Given the statement as in Proposition 3.4, prove that max{e1 , f 1 } max{e2 , f 2 } max{ek , f k } p2 · · · pk

lcm(a, b) = p1

(2)

and that every common multiple c of a and b is divisible by lcm(a, b). That is, if a | c and b | c, then lcm(a, b) | c. Exercise 3.7. Let a and b be non-negative integers. Prove that ab = gcd(a, b) lcm(a, b).

(3)

Exercise 3.8. Compute lcm(440, 300) using formulas (2) and (3). We will now address the following question: which integers c can be written in the form ax + by, where x and y are integers? Speaking in fancy mathematical language, the identity c = ax + by means that c is an integer (linear) combination of a and b. Let us play around a little bit with the quantity ax + by. Clearly, a can be written in this form, since a = a · 1 + b· 0. Same applies to b, since b = a · 0 + b· 1. The number 0 can always be represented in this form, since 0 = a · 0 + b · 0. Note that, when at least one of a ...