E-Book Content
A GENTLE INTRODUCTION TO NUMBER THEORY AND CRYPTOGRAPHY [NOTES FOR THE PROJECT GRAD 2009]
LU´IS FINOTTI
Contents 1.
Important Sets
1
2.
Long Division
3
3.
A Useful Theorem and Some Semantics
7
4.
Simple Divisibility Criteria
11
5.
GCD and LCM
13
6.
The Extended Euclidean Algorithm
16
7.
Prime Numbers
20
8.
GCD and LCM Again
26
9.
Some Problems in Number Theory
29
10.
So, What’s Number Theory Good For?
39
11.
Integers Modulo n
41
12.
Exponents and Divisions in Z/nZ
45
13.
The RSA Cryptosystem
51
14.
Solutions
56
Index
60
1. Important Sets Before we start with the main topics, we need to review some notation: Definition 1.1.
(1) A set is just a collection of elements. We usually denote a set by enclosing
its elements in braces “{
}”. [So, {1, 2, 3, 4} is a set whose elements are the numbers 1, 2,
3, and 4.] Sets don’t need to have numbers as elements, but they likely will in this course. Note that the order that we write the elements of the set does not matter, all that matters is the content, i.e., what elements it has. (2) An element of a set is said to belong to the set. We use the symbol “∈” for “belongs to” and “6∈” for “does not belong to”, such as in: 1 ∈ {0, 1, 2}
and 1
3 6∈ {0, 1, 2}.
2
PROJECT GRAD 2009
(3) We have that N = {0, 1, 2, 3, 4, . . .}, denotes the set of natural numbers. [The ellipsis here means “continues in the same way”.] Careful: Some authors exclude zero from the set of natural numbers. We will use instead N∗ = {1, 2, 3, 4, . . .}, and refer to N∗ as the set of positive integers. [Note that zero is neither positive nor negative!] (4) We define the set of integers as Z = {. . . , −3, −2, −1, 0, 1, 2, 3, . . .}. (5) We define the set of rationals as p : p ∈ Z and q ∈ N∗ . Q= q [The colon “ : ” above reads as “such that”. So, we read the set above as “the set of all [fractions] p/q such that p is in Z and q is in N∗ ”.] This set includes then all fractions of integers, such as 21 , − 73 ,
7636524628 8745834838388 ,
etc. [Remember, we can never divide by zero!]
(6) The set of real numbers, which is studied in [pre]calculus is denoted by R. It contains Q √ and all irrational numbers [which cannot be expressed as fractions of integers], such as 2, √ 17 31, π, e, etc. Loosely speaking, [classical] number theory, the subject of this course, is the study of integers. Sometimes, sets that are “similar” to the integers are also studied. But, for purists, the study of those sets are only relevant if it yields results or ideas of importance to the integers. It is then not very surprising that the rational numbers often show up in number theory, and it is also often considered to have its own interest in the field. Although it would seem that the set of real numbers is not very relevant to the study of integers, it does show up often. Even more, the set of complex numbers [for those who have heard of them], which is usually denoted by C, is quite important to number theory. [We will not deal with C in this course.] Problems. 1.1) Decide if each statement below is true or false: √ (a) 2 ∈ Q. (f) 2 ∈ R. √ (b) −2/3 ∈ Z. (g) 2 + 1 ∈ Q. (c) π ∈ Q.
(h) e ∈ Z.
(d) 0 ∈ N.
(i) −5 ∈ N.
(e) 0 ∈ N∗ .
(j) 5/4 ∈ Q.
A GENTLE INTRO. TO N. THEORY AND CRYPTO.
3
2. Long Division We will deal mostly with integers in this course, as it is the main object of study of number theo