WIXLIB

1. INTRODUCTION5says the analytic continuation of the zeta function for Re(s) 0 has all its roots on theline Re(s) 1/2.] An “elementary” proof in number theory means that it does not usecomplex analysis. An elementary proof may be very difficult. An elementary proof of PNTwas discovered in 1949 by Selberg and Erdös. It is much harder than the non-elementaryproof.Statement 4 is not very interesting, although the Pythagoreans knew it but were afraidto leak the knowledge, fearing catastrophe if it got out. It did. They were apparentlyright. To prove this, we need:Theorem 1.3. (The Fundamental Theorem of Arithmetic) Every integer n 1 is aproduct of positive primes unique up to order, i.e., there exist unique primes 1 p1 · · · pr and unique integers e1 , . . . , er 0 such that(*)n pe11 · · · perr .We call (*) the standard representation or standard factorization of n. We show Statement4 assuming that this theorem is true. [Euclid knew its proof and we shall prove it inTheorem 4.16.] If 2 is rational, then 2 mfor some integers m, n with n 6 0. This means that wen2have an equation of integers 2n m2 . But the prime two occurs on the left hand side toan odd power and on the right hand side to an even power, contradicting the uniquenesspart of the Fundamental Theorem of Arithmetic. Thus 2 is irrational, i.e., a complexnumber that is not rational.Statement 5 was proven by Lindemann in 1882. This is historically interesting as itsolves the famous Greek construction problem, “squaring the circle”, which asks whetherone can construct a circle with the same area as a given square using only a straightedge and compass (according to specific rules). Its proof is not easy. One must reducethis geometric problem to an algebraic one in field theory, which is then proven usinganalysis. A proof is given in Section 72. It is easier to show that the real number e istranscendental.P (Cf.1 Section 70.) The first real number shown to be transcendental wasthe number n 1 10n! shown to be transcendental by Liouville [cf. Section 69]. [That it istranscendental is essentially due to the fact that this series converges much too rapidly.]An even deeper result, solved independently by Gelfond and Schneider [which we do notprove], isTheorem 1.4. (Hilbert’s Seventh Problem) Let α and β be algebraicover Q with α 6 0, 1 2and β irrational. Then αβ is transcendental. In particular 2 is transcendental. This theorem also proves that eπ is transcendental, since eπ (e 1π ) 1 ( 1) 1 .It is unknown whether π e is transcendental.Lindemann actually proved thatif α is algebraic andnonzero, then eα is not algebraic. Since Euler showed that 1 e 1π , it follows that 1π is not algebraic; and from thisit follows that π is transcendental, using the fact that the product of algebraic numbersis algebraic, which we prove in Theorem 47.20.Statement 6 is not as interesting as Statement 5 for the word “transcendental” is amisnomer. However, the proof of this by Cantor changed mathematics and caused much

6philosophical distress. Indeed, Cantor showed that there were “many more” reals thanrationals. What does this mean?Let A and B be two sets. [What is a set?] We say that A and B have the samecardinality and write A B if there exists a one-to-one and onto function, i.e., abijection, f : A B. We call such an f a bijective function. Recall that a function ormap f : A B is one-to-one or injective iff (a1 ) f (a2 ) a1 a2(where means implies). Let f (A) : {f (a) a A} denote the image of A. Then fis one-to-one is if and only iff 1 : f (A) A given by f (a) 7 ais a function. We say f is onto or surjective if B f (A). [We also write a function asfA B.]Review 1.5. You should review the definitions of functions, inverses, etc. that we assumeyou have learned.Examples 1.6.1. {1, 2, . . . , 26} and {a, b, . . . , z} have the same cardinality.2. Z and 2Z : {2n n Z} have the same cardinality, as f : Z 2Z given by n 7 2nis a bijection.3. Let Z denote the set of positive integers and N Z {0} the set of non-negativeintegers. Then Z, N, and Z all have the same cardinality. Indeed, the maps(2n 1 if n 0f : Z N by n 7 2n if n 0and g : N Z by n 7 n 1 are both bijections.If A is a set, we call the symbol A the cardinality of A and interpret it to meanthe “number of elements” in A. For example, if A is finite, i.e., the set A has finitelymany elements [we write A ], then A is the number of elements in A, e.g., we have {1, . . . , 26} 26. If A is not finite, we of course say that A is infinite. If a set A satisfies A Z , i.e., there exists a bijection f : Z A (equivalently, there exists a bijectiong : A Z), we say A is countable. (Some authors call such a set countably infinite ordenumerable.)The following facts can be shown [and we leave their proofs as exercises]:Facts 1.7.1. A subset of a countable set is either finite or countable.2. Q is countable.3. Let C be the set of complex numbers. Then {α C α algebraic }, the set of complexalgebraic numbers, is countable.Theorem 1.8. (Cantor) The set R of real numbers is not countable.

1. INTRODUCTION7Proof. Suppose that R is countable. As R and the closed interval [0, 1] have the samecardinality by Exercise 1.12(10), the interval [0, 1] must also be countable. As Z Z isnot finite, it is also countable by the first fact (or by Example 1.6(3)). Therefore, thereexists a bijection f : Z [0, 1], i.e., the closed interval [0, 1] is covered by a sequence.Write each f (n) in (base ten) decimal form, sayf (1) .a11 a12 a13 · · · a1n · · ·f (2) .a21 a22 a23 · · · a2n · · ·.f (n) .an1 an2 an3 · · · ann · · ·.For each n choose bn {1, . . . , 8} with bn 6 ann . [We omit 0 and 9 to prevent round offproblems.] Let b b1 b2 · · · bn · · · . Then b and f (n) differ in the nth digit as bn 6 ann .Moreover, as bn 6 0, 9, the numbers b and f (n) cannot be the same real number. Thusb 6 f (n) for all n Z , so f is not onto, a contradiction. (We have really used the factthat R is complete, i.e., that b is a real number.) Warning 1.9. Sets can be tricky – again we ask what is a set?Indeed, consider the statement:Statement 1.10. There is a universe, i.e., a set that contains all other sets.Now you should consider the following:Contemplate 1.11. (Russell’s Paradox) LetA : {B is a set B / B}.Is A A? Is A 6 A?What can you conclude?Exercises 1.12.1. Show if a nonzero integer a divides integers b and c, it divides bx cy for any integersx and y.2. Show if an 1 is a prime with n 1, then a 2 and n is a prime. [The converse isfalse as 23 M11 .]3. If 2n 1 is a prime, what can you say about n? Prove your assertion.a4. Let a, b, n Z with n 1 and b 6 0. Determine when n b is a rational number. Proveyour determination. (You can use the Fundamental Theorem of Arithmetic.) 5. Assume that the real number π is transcendental. Show that π is transcendental.6. Let f : A B be a map of sets. Prove that f is injective if and only if given any setC and any two set maps gi : C A, i 1, 2, with compositions f g1 f g2 , theng1 g2 .

87. Let f : A B be a map of sets. Prove that f is surjective if and only if given any setC and any two set maps hi : B C, i 1, 2, with compositions h1 f h2 f , thenh1 h2 .8. Show a subset of a countable set is either countable or finite.9. If the sets A and B are countable, show that the cartesian productA B : {(a, b) a A, b B}is also countable. Using induction (to be discussed), show ifA1 , . . . , An are countable so is A1 · · · An .[Hint: Show Z Z (or Z Z where Z : {n Z n 0}) is countable by drawinga big ( infinite) matrix. In a similar way one proves Fact 1.7(2). In fact, the cartesianproduct of countable sets is countable, which is needed to prove Fact 1.7(3). Can youprove this?]10. The closed interval [0, 1] and the set of all real numbers R have the same cardinality.11. Any two (finite) line segments (so each has more than one point) have the same cardinality. [Hint: Draw the two line segments parallel to each other.]

CHAPTER IThe IntegersIn this chapter, we investigate the basic properties of the set of integers. In particular,we show that every integer can be factored into a product of primes, unique up to order.To do so we introduce concepts that shall be generalized. We assume that the readerhas seen proofs by induction. We begin the chapter with an equivalent form of inductioncalled the Well-Ordering Principle and use it to establish facts about division of integers.In particular, we prove the division algorithm. Of great historical importance is the notionof prime and the property discovered by Euclid that characterizes a prime that became acornerstone of modern algebra.2. Well-Ordering and InductionWe denote the empty set by . In this section, we are interested in induction whichyou should have seen and turns out to be equivalent to the following:The Well-Ordering Principle 2.1. Let 6 S Z . Then S contains a least (alsocalled a minimal) element, i.e.,There exists an a S such that if x S, then a x.This is an axiom that we accept as being true. You can visualize it by drawing thepositive real line and ticking off the integers. You move to the right until you get to thefirst element in S.One can modify the Well-Ordering Principle to the seemingly more general:The Modified Well-Ordering Principle 2.2. Let 6 T Z. Suppose that thereexists an N Z such that N x for all x T , i.e., T is bounded from below. Then Tcontains a least element.Proof. Let f : Z Z be the map defined by x 7 x N 1 where here N meansthe absolute value of N . Then f is a bijection. [What is f 1 ?] Hence the restriction of f tothe subset T , which we denote by f T : T Z, is also injective. As f (T ) f T (T ) Z ,there exists a least element f (a) f (T ), a T , by the Well-Ordering Principle. Then ais the least element of T as f preserves . (You should check this.) Remark 2.3. In an analogous way, if 6 T Z is bounded from above, i.e., there existsan integer N satisfying s N for all s T , then T contains a largest (also called amaximal) element, i.e., an element a T such that x a for all x in T .We have the following simple applications of well-ordering.Application 2.4. There exists no integer N satisfying 0 N 1 (or strictly betweenany integers n and n 1).9

10I. THE INTEGERSProof. Let S {n Z 0 n 1}. If 6 S then there exists a least elementN S by well-ordering, so 0 N 1 which implies that 0 N 2 N 1 – can youprove this? – and N 2 Z contradicting the minimality of N . Application 2.5. Let P (n) be a statement that is true or false depending on n Z .If P (n) is not true for some n then by the Well-Ordering Principle, there exists a leastelement n Z such that P (n) is false. We call P (n) a minimal counterexample.Application 2.6. Suppose that S Z and 1 S. If S satisfies the condition thatwhenever n S also n 1 S, then S Z .Proof. LetT Z \ S {n Z n 6 S},i.e., Z T S, the union of T and S, and T S, the intersection of T and S. (Wesay that Z is the disjoint union of S and T , and we write Z S T .)Suppose that T 6 . Then by well-ordering there exists a least positive element n T .In particular, n 1 6 T . As 1 6 T , n 1, so we have n 1 Z . Hence by minimality,n 1 S. The hypothesis now implies that n S, a contradiction. Thus T soZ S. The applications yield the following:Application 2.7. (First Principle of Finite Induction) For each positive integer n, letP (n) be a statement that is true or false. Suppose we know that(1) (Base Case) P (1) is true.(2) (Induction Step) If P (n) is true then P (n 1) is true.Then P (n) is true for all positive integers n.The hypothesis in the induction step is called the induction hypothesis.Often the following equivalent variant of the First Principle of Finite Induction is moreuseful. That it is equivalent is left as an exercise.Application 2.8. (Second Principle of Finite Induction) For each positive integer n, letP (n) be a statement that is true or false. Suppose that the assumption that P (m) is truefor all positive integers m n implies that P (n) is true. Then P (n) is true for all positiveintegers n.Remark 2.9. If n 1 then {m 1 m Z } is empty, so you still must show thatP (1) is true if you wish to use the Second Principle of Finite Induction, as your proofwould fail for n 1 otherwise. Remember that well-ordering needs a nonempty set.Remark 2.10. Note that using the Modified Well-Ordering Principle, you can start induction at any integer and prove things from that point on, e.g., you can start at 0.We assume that you have seen induction proofs in the past, e.g., in your linear algebracourse. Induction proofs can be very complicated. We give such a complicated inductionproof. Note in the proof the formal steps versus the mathematical ones.Example 2.11. The product of any n 1 consecutive positive integers is divisible byn!.

2. WELL-ORDERING AND INDUCTION11Proof. Let m and n be two positive integers and set(m)n : m(m 1) · · · (m n 1),the product of n consecutive integers starting from m.Claim 2.12. We have n! (m)n for all positive integers m and n.Of course, the claim is exactly what we want to prove. Note that there are two integersin the claim. We haveIf m Z is arbitrary and n 1 then (m)n m and n! 1! m.We assumeInduction Hypothesis I. The claim holds for fixed n N 1 and for all m.This is the induction step on n, using N for clarity. As we know that this holds forn 1 and for all m, we must show that the result holds for N and all m, i.e., we mustshow(N 1)! (m)N 1 for all m N ! (m)N for all m.Let m 1. Then (1)N N ! and N ! (1)N . Note that this is the first step of an inductionon m. So we can assumeInduction Hypothesis II. The claim holds for fixed n N and m M . (Notationallyit is easier to use M rather than M 1).We must show that Induction Hypotheses I and II imply the result for n N andm M 1, i.e.,if N ! (M )N and (N 1)! (M 1)N 1 then N ! (M 1)N .Note that if we show this, then we have completed the induction step for the InductionHypothesis II hence the result would be true for n N and for all m. This in turncompletes the induction step for Induction Hypothesis I and hence would prove the claim.Note also, so far even though a lot has been written, everything has been completelyformal and no real work has been done except for the facts that 1 m and n! n!. Wefinally must do the mathematics. This comes from the equation(M 1)N (M )N (M 1)(M 2) · · · (M N ) M (M 1) · · · (M N 1) (M 1) · · · (M N 1)[(M N ) M ](factoring) N (M 1) · · · (M N 1) N (M 1)N 1 .By Induction Hypothesis I, we have(N 1)! (M 1)N 1 so N ! N (M 1)N 1 ,and by Induction Hypothesis II, we have N ! (M )N . This means thatN ! N (M 1)N 1 (M )N , i.e., N ! (M 1)Nby Exercise 1.12(1), completing the induction step for Induction Hypothesis II, whichcompletes the induction step for Induction Hypothesis I as needed.

12I. THE INTEGERSCorollary 2.13. Let n Z . Then there exist infinitely many n consecutive composite(i.e., non-prime and not 0 or 1) positive integers.Proof. Let m Z and N (m)n 1 m(m 1) · · · (m n). Then by the example,we have (n 1)! N . If follows that for any integer s satisfying 2 s n 1, we haves N s. As n 1 N s, the positive integers(*)N 2, N 3, . . . , N n 1are all composite. Of course, the same proof works with m 1, so we did not need the example to provethis. However, (*) says there are arbitrarily large gaps between primes. On the otherhand, primes are not ‘sparse’, as Chebyshev proved Bertrand’s Hypothesis, which saysIf n Z then there exists a prime p satisfying n p 2n.Of course, 2n in theXabove can only be prime if n 1. In fact, earlier Euler showed that1diverges, so there are ‘many more’ primes than say squares (inthe infinite sumpp a positive primesome sense).Corollary 2.14. Let m and n be positive integers with n m. Define the binomialcoefficients m(m 1) · · · (m n 1)mm! : n(m n)!n!n!and mm(m 1) · · · (m n 1).: ( 1)nn!n Then mand mare integers.nn nProof. We know that m (m n 1)is an integer by the example. The secondn!nstatement follows from the identity mn m n 1 ( 1).nn Corollary 2.15. Let p 1 be a prime. Then ppp,, . ,12p 1 are all divisible by p, i.e., p np for 1 n p 1.Proof. If 1 n p 1, then the example says thatn! p(p 1) · · · (p n 1) (p n 1)nWe also know that s and p have no common nontrivial factors if 1 s p. [Proof?] Wesay that s and p are relatively prime. (Cf. 4.4.) We shall show this below (cf. Theorem4.10) but assume for now the following:

3. ADDENDUM: THE GREATEST INTEGER FUNCTION13Theorem 2.16. (General Form of Euclid’s Lemma) Let a, b, c be nonzero integers witha and b relatively prime integers. If a bc then a c.Applying Euclid’s Lemma, we conclude thatn! (p 1) · · · (p n 1) so pn! p(p 1) · · · (p n 1)for all n satisfying 1 n p 1. (Why?) Exercises 2.17.1. Prove that the number of subsets of a set with n elements is 2n .2. When Gauss was ten years old he almost instantly recognized that 1 2 · · · n n(n 1). [Actually, what he did was a bit harder.] What is a formula for the sum of the2first n cubes? Prove your result.3. The first nine Fibonacci numbers are 1, 1, 2, 3, 5, 8, 13, 21, 34. What is the nth Fibonaccinumber Fn ? Show that Fn 2n .4. Note that Euclid’s proof of the infinitude of primes clearly shows that if pn is the nthn 1prime, then pn 1 pnn 1. Be more careful and show that pn 1 22 ? Using this,show that π(x) log log(x), where π(x) is the number of primes less than x if x 2.[This is a bad estimate.]5. Prove that the Well-Ordering Principle, the First Principle of Finite Induction, andthe Second Principle of Finite Induction are all equivalent.6. State and prove the binomial theorem. What algebraic properties do you need for yourproof to work?7. Fill in the missing details in the proof of Corollary 2.15.3. Addendum: The Greatest Integer FunctionOur (double) induction showing that binomial coefficients are integers was complicatedto write, although the mathematics was simple. In this addendum, we shall give anotherproof, mathematically more complicated, but of greater interest. We shall use someresults that we shall prove in the next section, in particular, the Division Algorithm 4.2and the Fundamental Theorem of Arithmetic 4.16. This alternate proof uses the followingfunction:Definition 3.1. The greatest integer function[ ] : R Z is given by [x] : the greatest integer n satisfying n x,i.e., if x R, using Application 2.4, we can writex n x0 with 0 x0 1, n Z then [x] n.This function satisfies:Properties 3.2. Let m be a positive integer. Then the following are true:(1) [x] x [x] 1.(2) [x m] [x] m.x(3) [ m] [ [x]].m

14I. THE INTEGERS(4) [x] [y] [x y] [x] [y] 1.(5) If n, a Z , then [ na ] is the number of integers among 1, . . . , n that are divisibleby a.Proof. (1) and (2) are easy to see.(3): Write x

n: 2n 1, na positive integer, a Mersenne number and a Mersenne prime if it is a prime. In 1644, Mersenne conjectured that for n 257, the Mersenne number M n is prime if and only if n 2;3;5;7;13;17;19;31;67;127;257. [If M n is a prime, then nmust be a prime as 2ab 1 factors if a;b 1.] It was shown in the 1880's that M 61 is a prime. In .