6.042J Lecture Notes - Lecture 1: Perfect Number, Number Theory, Linear Combination
Document Summary
Number theory underlies modern cryptography, which is what makes secure online communication possible. Number theory also provides an excellent environment for us to practice and apply the proof techniques that we developed. We will work out the properties of greatest common divisors (gcd"s) and use them to prove that integers factor uniquely into primes. Then we will introduce modular arithmetic and work out enough of its properties to explain the rsa public key crypto system. Some immediate consequences of that de nition are that for all n: n|0, n|n, and 1|n. De nition: a divides b (notation a | b) iff there is an integer k such that ak = b. The nature of number theory emerges as soon as we consider the divides relation. The pythagoreans said that a number is perfect if it equals the sum of positive integral divisors, including itself.