Rational Numbers and Divisibility We review various number systems: N = set of natural numbers = {0,1,2,3,...} Z = set of integers = { ...,-3,-2,-1,0,1,2,3,... } Q = rational numbers = {a/b | a,b in Z and b =/=0} R = real numbers = numbers used to measure distances on a number line = decimal expressions that may go on forever C = complex numbers = {a+ib | a,b in R, i= sqrt(-1)} Many other systems have been studied. Among these the following will soon be useful to us: 2Z = {2n | n in Z} = even numbers 1+2Z = {1+2n | n in Z} = odd numbers 3Z = {3n | n in Z} = multiples of 3 Z_2 = { 2Z, 1+2Z } = {Evens, Odds}; i.e., Z_2 has only two elements, and each is a set. Let us focus now on Q for awhile. Theorem: The sum of two rational numbers is rational. This can be rewritten as: ForAll x,y (x,y in Q --> x+y in Q). Proof: Let x and y be rational (i.e., generic particulars). Then by definition, x = a/b, y = c/d, where a,b,c,d are in Z and b and d are not zero. Then x+y = a/b + c/d = (ad+bc)/bd which is in Q since ad+bc and bd are in Z and bd=/=0. Since x and y are generic, then we have shown ForAll x,y (x,y in Q --> x+y in Q) The next example takes a little twist, bringing in an "indirect" step. Theorem: The sum of a rational and an irrational number is irrational. Proof: The statement can be rewritten as: ForAll x,y (x in Q and y not in Q --> x+y not in Q) So let x be in Q and y not in Q. Then x = a/b where a,b in Z and b=/=0, and y is not of that form. Now we seem stuck, since we have an expression for x that we can calculate with, but none for y. We then turn to the conclusion "x+y not in Q" and ask how it can fail. For it to fail would mean that x+y is rational, i.e., that x+y = c/d where c,d in Z and d =/=0. For that to happen, we'd have to have the following: x+y = c/d and x = a/b, which would force y = c/d - x = c/d - a/b = (bc - ad)/bd which is in Q. But this cannot be: y is irrational (chosen so by us at the beginning). So the situation that would force y to be in Q (namely that x+y is in Q) must be impossible: x+y must be irrational. We conclude that since x and y are generic, ForAll x,y (x in Q and y not in Q --> x+y not in Q). We started out with the direct method, then got stuck, and tried a different tack: we showed that the conclusion *could not fail* because if it did, that would contradict something that was true. This is called the indirect method. It goes like this: To prove A --> B, assume A. But then instead of proving B directly in steps leading from A, also assume ~B and see what happens. If this leads to a contradiction with something true, that means the assumption of ~B cannot be true, so B must be true. This a special case of something I call the Sherlock Holmes method of proof: "Watson, when all the possibilities except one have been shown to be impossible, then the remaining one -- no matter how improbable -- must be true." Holmes used this to track down the person guilty of murder; here we use it simply to track down a math truth. Here is how it goes: Suppose S1, S2, ..., S6 are the only 6 possibilities in a given situation (i.e., we know one of them must be true) and suppose we can show ~S2, ~S3 ..., ~S6; then S1 has to be true. The above example had only two cases: S1: x+y not in Q S2: x+y in Q We showed ~S2: x+y could not be in Q bec that contradicted something we knew (that x is in Q and y is not in Q). So S2 is false, and the only remaining "suspect" is S1. So S1 holds. This Holmesian method seems amazing: we show S1 is guilty by showing everyone else is NOT guilty, and we never even *look* at S1! That's scary, but it works (in mathematics and in fiction, maybe not in the courtroom). Now we turn to divisibility. This has to do with quotients and divisors and remainders, in the domain of integers. Consider q _____ d | n -qd --- r which is a diagram for this equation: n = r + qd, where 0 <= r < d That is, we divide n by divisor d, and get a quotient of q, with a remainder of r. We will examine this more carefully next week. But for now we consider a special case: r=0. When r = 0, then n = qd, and we say n is *divisible* by d, or that d is a divisor or factor of n, or n is a multiple of d. We write d | n, and read it as "d divides n", to mean there is no remainder. Another way to express this is: Exists q (n = qd), where of course q also has to be an integer. Recall the notations 2Z, 3Z, 1+2Z? This is useful here. For instance, 2 | n now can be restated as "n is in 2Z". Thus Even(n) has various representations, including: 2 | n n is in 2Z n = 2q for some integer q Definition: An integer n > 1 is *prime* if its only divisors (factors) are 1 and itself. The ten smallest primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. The sequence of primes goes on forever, as we shall show next week. For convenience, we shall let p_k be the kth prime in this sequence, starting with p_1 = 2, p_2 = 3, etc. [Note this is NOT the notation used in the book.] Theorem 4.3.4: Every integer n > 1 is divisible by a prime. Theorem 4.3.5 (Fund Thm of Arithmetic, aka Unique Factorization Thm, UFT): Every positive integer n>1 can be expressed as the product of prime factors, each raised to some non-neg power: n = p_1^n_1 * p_2^n_2 * ... * p_k^n_k * ... = 2^n_1 * 3^n_2 * 5^n_3 * ... where (i) all but finitely-many of the n_k are 0 (ii) the n_k are unique: no other values of n_k will produce n as the above product We call n = p_1^n_1 * p_2^n_2 * ... * p_k^n_k * ... the (unique) prime factorization of n. To save writing, we shall also simply use upf(n) to stand for this same product. Thus n = upf(n); that is, the LHS and the RHS have the same numerical value, but the RHS is shorthand for the long written-out product above. Example: 20 = 4 * 5 = 2^2 * 5^1 = 2^2 * 3^0 * 5^1 * 7^0 * 11^0 * ... Example 4.3.9: Suppose 8*7*6*5*4*3*2*m = 17*16*15*14*13*12*11*10 Does 17 | m ? 17 | RHS, so then also 17 | LHS (since they are the same number). But 17 is prime, and so must appear in upf(LHS). But the only prime factors of the LHS are the prime factors of 8, 7, 6, 5, 4, 3, 2 and m, and clearly 17 does not divide numbers smaller than itself. So it must be m that 17 divides. Thus 17 | m. Example: We are so used to thinking the prime factorization as unique that is may be hard to imagine it might be otherwise. But consider this: 41 * 13 =/= 43 * 11 =/= 57 * 9. While we can check this by actually computing the three products, it is easier to note that the prime factors involved (41, 13, 43, 11, 57, 3) are different from product to product, and so the products cannot be equal. Even more dramatic: 3^10 * 7^14 =/= 21 * 11^15. This is hard to figure out by simply hand-estimating sizes of the two sides. But the RHS has 11 as prime factor, and the LHS has only 3 and 7. So they cannot be equal.