Number Theory is a vast and fascinating field of mathematics, sometimes called "higher arithmetic," consisting of the study of the properties of whole numbers. Primes and Prime Factorization are especially important in number theory, as are a number of functions including the Totien function. The great difficulty required to prove relatively simple results in number theory prompted Gauss, the "prince of mathematics", to remark that "it is just this which gives the higher arithmetic that magical charm which has made it the favorite science of the greatest mathematicians, not to mention its inexhaustible wealth, wherein it so greatly surpasses other parts of mathematics." See Carl Friedrich Gauss to read more about Gauss.
Cryptography is the process of transferring information securely, in a way that no unwanted third party will be able to understand the message. It has been used for thousand of years. Number theory and Cryptography are inextricably linked, as we shall see in the following lessons.
To begin you will need to acquaint yourself with Cryptography Lesson 2 which includes the concepts of: prime numbers, greatest common divisors, modular arithmetic, etc. To do so, see Cryptography Lesson 2.
How can we find prime numbers? Centuries ago, it was thought that if n is an integer then n2+n+41 is always prime. This happens to be true for n=0,1,2,...38,39 but fails for n=40 and obviously fails for n=41 (there is a factor of 41 in each part of the addition).
Fermat (1601-1665) conjectured that the numbers Fn=22n+1 are primes for all n greater that or equal to 0. He checked this n=0,1,2,3,4. However he stopped there because F5=4,294,967,297. Euler later discovered that 641 divides F5, hence it is not prime. Thus far the only know Fermat primes are the five that Fermat himself originally found. To read more on this see Fermat Number.
Legendre and Gauss conjectured, independently, that the number of primes <=n (denoted Π(n))is approximately
n/(1+1/2+1/3+...+1/n)
This conjecture is now known as the Prime Number Theorem and was proved by Hadamard in 1896. For more exact information on this see Prime Number Theorem.
Problem Set 1 Considering why n2+n+41 does not give us a prime number for n=41, show that no polynomial can give us a prime number for every integer n.
Show that (1+1/2+1/3+...+1/n+...) goes to infinity. What does this tell us about the ratio of primes vs. integers as n gets large (assuming the Prime Number Theorem is true)?End of Problem Set 1[2]
An important property of the integers, which we will find useful is the Well Ordering Principle, which states that every set of positive integers contains a smallest member. Since this property cannot be proved from the usual properties of arithmetic, we will take it as an axiom.
GCD Is a Linear Combination:For any nonzero integers a and b, there exist integers s and t such that gcd(a,b)=as+bt. Moreover, gcd(a,b) is the smallest positive integer of the form as+bt.
Proof: Consider the set S={am+bn | m,n are integers and am+bn>0}. Since S is obviously nonempty (if some choice of m and n makes am+bn<0, then replace m and n by -m and -n), the Well Ordering Principle asserts that S has a smallest member, say, d=as+bt. We claim that d=gcd(a,b). To verify this claim, use the division algorithm to write a=dq+r, where 0<=r0, then r=a-dq=a-(as+bt)q=a-asq-btq=a(1-sq)+b(-tq) which is in S, contradicting the fact that d is the smallest member of S. So, r=0 and d divides a. Analogously (or better yet, by symmetry), d divides b as well. This proves that d is a common divisor of a and b. Now suppose d' is another common divisor of a and b and write a=d'h and b=d'k. Then d=as+bt=(d'h)s+(d'k)t=d'(hs+kt) so that d' is a divisor of d. Thus among all common divisors of a and b, d is the greatest.
Euclid's Lemma:If p is a prime that divides ab, then p divides a or p divides b.
Proof: Suppose p is a prime that divides ab but does not divide a. We must show that p divides b. Since p does not divide a (and p is prime), a and p are relatively prime so gcd(a,p)=1 and by the previous statement there exist integers s and t such that 1=as+pt. Then b=abs+ptb, and since p divides the right side of this equation, p also divides b.
Least Common Multiple: The least common multiple of two nonzero integers a and b is the smallest positive integer that is a multiple of both a and b. We will denote this integer by lcm(a,b).
Problem Set 2 :
For n=8,12,20 and 25, find all positive integers less than n and relatively prime to n.
Find integers s and t so that 1=7s+11t. Show that s and t are not unique.
Show that if a and b are positive integers, then ab=lcm(a,b)*gcd(a,b).
Let a and b be positive integers and let d=gcd(a,b) and m=lcm(a,b). If t divides both a and b, prove that t divides d. If s is a multiple of both a and b, prove that s is a multiple of m.
End of Problem Set 2[1]
References and Further Reading:
[1]Joseph A. Gallian.Contemporary Abstract Algebra 4th Edition Houghton Mifflin Company, 1998, pages 3-22.
[2]Harold M. Stark.An Introduction to Number TheoryMarkham Publishing Company, 1970, pages 1-3.