Transcript N - 陳光琦
資訊科學數學8 : Proof Strategy, Number and Orders 陳光琦助理教授 (Kuang-Chi Chen) [email protected] Mini Review & More Proof Methods Inference Rules - General Form • Inference Rule - Pattern establishing that if we know that a set of antecedent statements of certain forms are all true, then a certain related consequent statement is true. • antecedent 1 antecedent 2 … consequent “” means “therefore” Inference Rules & Implications • Each logical inference rule corresponds to an implication that is a tautology. • antecedent 1 Inference rule antecedent 2 … consequent • Corresponding tautology: ((ante. 1) (ante. 2) …) consequent Some Inference Rules • p pq Rule of Addition • pq Rule of Simplification • Rule of Conjunction p p q pq Modus Ponens & Tollens • p pq q • q pq p Rule of modus ponens 斷言法 (a.k.a. law of detachment) “the mode of affirming” a.k.a. “also known as” Rule of modus tollens 否定法 “the mode of denying” Syllogism Inference Rules • pq qr pr • pq p q Rule of hypothetical syllogism 三段論 Rule of disjunctive syllogism Many valid inference rules were first described by Aristotle. He called these patterns of argument “syllogisms.” Aristotle (ca. 384-322 B.C.) Inference Rules for Quantifiers • x P(x) P(o) (substitute any object o) • P(g) (for g a general element of u.d.) x P(x) • x P(x) P(c) (substitute a new constant c) • P(o) (substitute any extant object o) x P(x) Common Fallacies • A fallacy is an inference rule or other proof method that is not logically valid. - May yield a false conclusion! • Fallacy of affirming the conclusion: “pq is true, and q is true, so p must be true.” ? (No, because FT is true.) • Fallacy of denying the hypothesis: “pq is true, and p is false, so q must be false.”? (No, again because FT is true.) Proving Existentials • A proof of a statement of the form x P(x) is called an existence proof. • If the proof demonstrates how to actually find or construct a specific element a such that P(a) is true, then it is a constructive proof. • Otherwise, it is nonconstructive. Constructive Existence Proof Theorem: There exists a positive integer n that is the sum of two perfect cubes in two different ways - equal to j3 + k3 and l3 + m3 where j, k, l, m are positive integers, and {j, k} ≠ {l, m}. Proof: Consider n = 1729, j = 9, k = 10, l = 1, m = 12. Now just check that the equalities hold. Another Constructive Existence Proof Theorem: For any integer n>0, there exists a sequence of n consecutive composite integers. - Same statement in predicate logic: n>0 x i (1in)(x+i is composite) … Proof follows on the next … Predicate Logic • Predicate logic is an extension of propositional logic that permits concisely reasoning about whole classes of entities. • Propositional logic (recall) treats simple propositions (sentences) as atomic entities. • In contrast, predicate logic distinguishes the subject of a sentence from its predicate. - Remember these English grammar terms? Applications of Predicate Logic • It is the formal notation for writing perfectly clear, concise, and unambiguous mathematical definitions, axioms, and theorems for any branch of mathematics. - Predicate logic with function symbols, the “=” operator, and a few proof-building rules is sufficient for defining any conceivable mathematical system, and for proving anything that can be proved within that system! Practical Applications of Predicate Logic • It is the basis for clearly expressed formal specifications for any complex system. • It is basis for automatic theorem provers and many other Artificial Intelligence systems. E.g. automatic program verification systems. • Predicate-logic like statements are supported by some of the more sophisticated database query engines and container class libraries. - these are types of programming tools. … Constructive Existence Proof … Theorem: For any integer n>0, there exists a sequence of n consecutive composite integers. • Given n>0, let x = (n + 1)! + 1. • Let i 1 and i n, and consider x+i. • Note x+i = (n + 1)! + (i + 1). • Note (i+1)|(n+1)!, since 2 i+1 n+1. • Also (i+1)|(i+1). So, (i+1)|(x+i). • x+i is composite. • n x 1in : x+i is composite. Q.E.D. Nonconstructive Existence Proof Theorem: “There are infinitely many prime numbers.” • Any finite set of numbers must contain a maximal element, so we can prove the theorem if we can just show that there is no largest prime number. i.e., show that for any prime number, there is a larger number that is also prime. • More generally: For any number, a larger prime. • Formally: Show n p>n : p is prime. The Proof …using proof by cases… • Given n > 0, prove there is a prime p > n. • Consider x = n!+1. Since x > 1, we know (x is prime)(x is composite). Case 1: x is prime. Obviously x > n, so let p = x and we’re done. Case 2: x has a prime factor p. But if p n, then p mod x = 1. So p > n, and we’re done. The Halting Problem (Turing‘36) • The halting problem was the first mathematical function proven to have no algorithm that computes it! - We say, it is uncomputable. • The desired function is Halts(P, I) :≡ the truth value of this statement: “Program P, given input I, eventually terminates.” Alan Turing Theorem: Halts is uncomputable! 1912-1954 i.e., there does not exist any algorithm A that computes Halts correctly for all possible inputs. • Its proof is thus a non-existence proof. Corollary: General impossibility of predictive analysis of arbitrary computer programs. The Proof 1 • Given any arbitrary program H(P, I). • Consider algorithm Breaker, defined as: procedure Breaker(P: a program) halts := H(P, P) if halts then while T begin end • • Breaker makes a liar out of H, by doing the opposite of whatever H predicts. Note that Breaker(Breaker) halts iff H(Breaker, Breaker) = F. So H does not compute the function Halts! The Proof 2 • Given any arbitrary program H(P, I), which • generates either “loop forever” or “halts” Consider algorithm K, defined as: K makes a liar out of H, procedure K(P: a program) by doing the opposite of whatever H predicts. output := H(P, P) if output==“loop forever” then halts ; else while T do {} /*loop forever*/; Now K(K) halts, otherwise H(K, K) generate “halts”. By definition of K. K(K) loops forever. A violation of what H tell us! 如果 H(K, K) 產生 “halts”, 則 K 會loop forever, H 猜錯了 Limits on Proofs • Some very simple statements of number theory have not been proved or disproved! E.g. Goldbach’s conjecture: Every integer n≥2 is exactly the average? of some two primes. n≥2 primes p, q: n = (p+q)/2. • There are true statements of number theory (or any sufficiently powerful system) that can never be proved (or disproved) (Gödel). Goldbach's Conjecture • Goldbach's conjecture is one of the oldest unsolved problems in number theory and in all of mathematics. - Every even integer greater than 2 can be written as the sum of two primes. • Expressing a given even number as a sum of two • primes is called a Goldbach partition of the number. For example, 4=2+2 , 6=3+3 , 8=3+5, 10 = 3 + 7 = 5 + 5 , 12 = 5 + 7 , 14 = 3 + 11 = 7 + 7 , etc. • http://en.wikipedia.org/wiki/Goldbach's_conjecture More about Goldbach's Conjecture Origins • On 7 June 1742, the Prussian mathematician Christian Goldbach wrote a letter to Leonhard Euler (letter XLIII) in which he proposed the following conjecture: - Every integer greater than 2 can be written as the sum of three primes. • He considered 1 to be a prime number, a convention subsequently abandoned. A modern version of Goldbach's original conjecture is: - Every integer greater than 5 can be written as the sum of three primes. • Euler, becoming interested in the problem, answered by noting that this conjecture would follow from a stronger version, - Every even integer greater than 2 can be written as the sum of two primes, Origins cont’d … • Euler provided a stronger version, - Every even integer greater than 2 can be written as the sum of two primes, adding that he regarded this a fully certain theorem ("ein ganz gewisses Theorema"), in spite of his being unable to prove it. • The former conjecture is today known as the "ternary" Goldbach conjecture, the latter as the "strong" or "binary" Goldbach conjecture. The conjecture that all odd numbers greater than 7 are the sum of three odd primes is called the "weak" Goldbach conjecture. Both questions have remained unsolved ever since, although the weak form of the conjecture is much closer to resolution than the strong one.. • http://en.wikipedia.org/wiki/Goldbach's_conjecture More about Goldbach's Conjecture • Heuristic justification • The majority of mathematicians believe the conjecture (in both the weak and strong forms) to be true, at least for sufficiently large integers, mostly based on statistical considerations focusing on the probabilistic distribution of prime numbers: the bigger the number, the more ways there are available for that number to be represented as the sum of two or three other numbers, and the more "likely" it becomes that at least one of these representations consists entirely of primes. • The prime number theorem asserts that an integer m selected at random has roughly a 1/ln(m) chance of being prime. Thus if n is a large even integer and m is a number between 3 and n/2, then one might expect the probability of m and n-m simultaneously being prime to be 1/[ln(m)ln(n-m)] More about Goldbach's Conjecture • Number of ways to write an even number n as the sum of two primes (4 ≤ n ≤ 1,000,000) Other Applications • Predicate logic is the foundation of the field of mathematical logic, which culminated in Gödel’s incompleteness theorem, which revealed the ultimate limits of mathematical thought : Given any finitely describable, consistent proof procedure, there will always remain some true statements that will never be proven by that procedure. Kurt Gödel 1906-1978 i.e., we can’t discover all mathematical truths, unless we sometimes resort to making guesses. More Proof Examples Q1: Is this argument correct or incorrect? “All TAs compose easy quizzes. Bob is a TA. Therefore, Bob composes easy quizzes.” First, separate the premises from conclusions: Premise #1: All TAs compose easy quizzes. Premise #2: Bob is a TA. Conclusion: Bob composes easy quizzes. Answer of Q1 Next, re-render the example in logic notation. • Premise #1: All TAs compose easy quizzes. - Let U.D. = all people - Let T(x) :≡ “x is a TA” - Let E(x) :≡ “x composes easy quizzes” - Then Premise #1 says: x, T(x)→E(x) Answer cont’d … • Premise #2: Bob is a TA. - Let B :≡ Bob - Then Premise #2 says: T(B) - And the Conclusion says: E(B) • The argument is correct, because it can be reduced to a sequence of applications of valid inference rules, as follows: The Proof in Gory Details • Statement How obtained 1. x, T(x) → E(x) (Premise #1) 2. T(Bob) → E(Bob) (Universal instantiation) 3. T(Bob) (Premise #2) 4. E(Bob) (Modus Ponens from statements #2 and #3) Another Example Q2: Correct or incorrect: At least one of the 280 students in the class is intelligent. Y is a student of this class. Therefore, Y is intelligent. • First: Separate premises/conclusion, & translate to logic: Premises: (1) x InClass(x) Intelligent(x) (2) InClass(Y) Conclusion: Intelligent(Y) Answer of Q2 • No, the argument is invalid; we can disprove it with a counter-example, as follows: • Consider a case where there is only one intelligent student X in the class, and X≠Y. - Then the premise x InClass(x) Intelligent(x) is true, by existential generalization of InClass(X) Intelligent(X) - But the conclusion Intelligent(Y) is false, since X is the only intelligent student in the class, and Y≠X. • Therefore, the premises do not imply the conclusion. Example : Q3 Q3: Prove that the sum of a rational number and an irrational number is always irrational. • First, you have to understand exactly what the question is asking you to prove: - “For all real numbers x, y, if x is rational and y is irrational, then x + y is irrational.” - x, y: Rational(x) Irrational(y) → Irrational(x+y) Answer of Q3 • Next, think back to the definitions of the terms used in the statement of the theorem: reals r: Rational(r) ↔ Integer(i) Integer(j): r = i/j. reals r: Irrational(r) ↔ ¬Rational(r) (Almost always need the definitions of the terms in order to prove the theorem!) - Next, let’s go through a valid proof. Proof of Q3 Thm: x, y: Rational(x) Irrational(y) → Irrational(x+y) Proof: Let x, y be any rational and irrational numbers, respectively. … (universal generalization) • Since x is rational, we know that there must be some integers i and j such that x = i/j. So, let ix, jx be such integers. • What do we know about y? Only that y is irrational: ¬ integers i, j: y = i/j. • But, it’s difficult to use a direct proof here. We could try indirect proof also, but in this case, it is simpler to just use proof by contradiction (similar to indirect). Proof cont’d … • Suppose that x+y were not irrational. Then x+y would be rational, so integers i, j: x+y = i/j. So, let is and js be any such integers where x+y = is/ js. • Now, with all these things named, we can start seeing what happens when we put them together. • So, we have that (ix/jx) + y = (is/js). - Solving that equation for y, we have: y = (is/js) – (ix/jx) = (isjx – ixjs)/(jsjx) Finishing the Proof • y = (is/js) – (ix/jx) = (isjx – ixjs)/(jsjx) • Now, since the numerator and denominator of this expression are both integers, y is (by definition) rational. This contradicts the assumption that y was irrational. Therefore, our hypothesis that x+y is rational must be false, and so the theorem is proved. ■ Example Wrong Answer • 1 is rational. √2 is irrational. 1+√2 is irrational. Therefore, the sum of a rational number and an irrational number is irrational. (Direct proof.) • Why does this answer merit no credit? - The student attempted to use an example to prove a universal statement. This is always wrong! - Even as an example, it’s incomplete, because the student never even proved that 1+√2 is irrational! Proof Strategies Overview • In the previous, we already saw: - Several types of proofs of implications p→q: . Direct, Indirect, Vacuous, Trivial . - Types of existence proofs: . Constructive vs. Nonconstructive. - Some methods of proving general statements p: . Proof by cases, proof by contradiction. • Here, we will see examples of: - Forward vs. backward reasoning. . Proof by cases. - Adapting existing proofs. . Turning conjectures into proofs. Forward Reasoning • Have premises p, and want to prove q. 1. Find a s1 such that p→s1 2. Then, modus ponens gives you s1. 3. Then, find an s2 (such that) s1→s2. 4. Then, modus ponens gives you s2. 5. And hope to eventually get to an sn sn→q. • The problem with this method is… It can be tough to see the path looking from p. Backward Reasoning • It can often be easier to see the very same path if you just start looking from the conclusion q instead… - That is, first find an s−1 such that s−1→q. - Then, find an s−2 s−2→s−1, and so on… - Working back to an s−n p→s−n. • We still are using modus ponens to propagate truth forwards down the chain from p to s−n to … to s1 to q! - We find the chain backwards, but apply it forwards. - This is not quite the same thing as an indirect proof… In that, we would use modus tollens and ¬q to prove ¬s−1, etc. However, it is similar. Backward Reasoning Example Theorem: a>0, b>0, a≠b: (a+b)/2 > (ab)1/2. Proof: - Notice it is not obvious how to go from the premises a>0, b>0, a≠b directly forward to the conclusion (a+b)/2 > (ab)1/2. - So, let’s work backwards from the conclusion, (a+b)/2 > (ab)1/2 ! ■ Steps of Example 1. (a+b)/2 > (ab)1/2 (squaring both sides) 2. (a+b)2/4 > ab (multiplying through by 4) 3. (a+b)2 > 4ab (squaring a+b) 4. a2+2ab+b2 > 4ab 5. a2−2ab+b2 > 0 (subtracting out 4ab) (factoring left side) 6. (a−b)2 > 0 # Now, since a≠b, (a−b)≠0, thus (a−b)2>0, and we can work our way back along the chain of steps… “Forward” Example Theorem: a>0, b>0, a≠b: (a+b)/2 > (ab)1/2. Proof. Since a≠b, (a−b)≠0, thus (a−b)2>0, i.e., a2−2ab+b2 > 0. Adding 4ab to both sides, a2+2ab+b2 > 4ab. Then, we have (a+b)2 > 4ab, so (a+b)2/4 > ab. Since ab is positive, we can take the square root of both sides and get (a+b)/2 > (ab)1/2. ■ - This is just a simple proof proceeding directly from premises to conclusion. A common student reaction: “But how did you know to pick 4ab out of thin air, to add to both sides?” Answer: By working backwards from the conclusion! Stone Game Example • Game rules: There are 15 stones in a pile. Two players take turns removing either 1, 2, or 3 stones. Whoever takes the last stone wins. Theorem: There is a strategy for the first player that guarantees him a win. - How do we prove this? Constructive proof… - Looks complicated… How do we pick out the winning strategy from among all possible strategies? - Work backwards from the endgame! Working Backwards in the Game • Player 1 wins if there is no stone on player 2’s pseudo last turn … • P1 can arrange this if there are 1, 2, or 3 stones on his last turn… • This will be true as long as player 2 had 4 stones or 4n stones on his turn… Player 1 Player 2 0 1, 2, 3 4 5, 6, 7 8 9, 10, 11 12 13, 14, 15 “Forward” Version Theorem. Whoever moves first can always force a win. Proof. Player 1 can remove 3 stones, leaving 12. After player 2 moves, there will then be either 11, 10, or 9 stones left. In any of these cases, player 1 can then reduce the number of stones to 8. Then, player 2 will reduce the number to 7, 6, or 5. Then, player 1 can reduce the number to 4. Then, player 2 must reduce them to 3, 2, or 1. Player 1 then removes the remaining stones and wins. ■ Cases Example Theorem: nZ ¬(2|n 3|n) → 24|(n2−1). Proof: Since 2·3 = 6, the value of n mod 6 is sufficient to tell us whether 2|n or 3|n. If (n mod 6){0, 3} then 3|n; if it is in {0, 2, 4} then 2|n. Thus (n mod 6){1, 5}. Case #1: If n mod 6 = 1, then (k) n = 6k+1. n2 = 36k2+12k+1, so n2−1 = 36k2+12k = 12(3k+1)k. Note 2|(3k+1)k since either k or 3k+1 is even. Thus 24|(n2−1). Case #2: If n mod 6 = 5, then n = 6k+5. n2−1 = (n−1)·(n+1) = (6k+4)·(6k+6) = 12·(3k+2)·(k+1). Either k+1 or 3k+2 is even. Thus, 24|(n2−1). ■ Proof by Examples ? • A universal statement can never be proven by using examples, unless the universe can be validly reduced to only finitely many examples, and your proof covers all of them! Theorem: ¬ x, yZ: x2+3y2 = 8. Proof: If |x|≥3 or |y|≥2 then x2+3y2 >8. This leaves x2{0, 1, 4} and 3y2{0, 3}. The largest pair sum to 4+3 = 7 < 8. ■ Adapting Existing Proofs Theorem: There are infinitely many primes of the form 4k+3, where kN. - One way to prove that there are infinitely many primes because if p1,…,pn were all the primes, then (∏pi)+1 must be prime or have a prime factor greater than pn contradiction! Adapting Existing Proofs Theorem: There are infinitely many primes of the form 4k+3, where kN. Proof: Similarly, suppose q1,…,qn lists all primes of the form 4k+3, and analogously consider Q = 4(∏qi)+3. Unfortunately, since q1 = 3 is possible, 3|Q and so Q does have a prime factor among the qi, so this doesn’t work! So instead, consider Q = 4(∏qi)−1 = 4(∏qi−1)+3. This has the right form, and has no qi as a factor since i: Q ≡ −1 (mod qi). Conjecture and Proof • We know that some numbers of the form 2p−1 are prime when p is prime. - These are called the Mersenne primes (梅森質數). • Can we prove the inverse, that an−1 is composite whenever either a>2, or (a=2 but n is composite)? - All we need is to find a factor greater than 1. • Note an−1 factors into (a−1)(an−1+…+a+1). - When a>2, (a−1)>1, and so we have a factor. - When n is composite, r, s>1: n=rs. Thus, given a=2, an = 2n = 2rs = (2r)s, and since r>1, 2r > 2 so 2n − 1 = bs−1 with b = 2r > 2, which now fits the first case. FYI : Mersenne Primes 梅森數 & 梅森質數 • 法國數學家梅森 (Marin Mersenne 1588-1648) 和業 餘數學王子費馬 (Pierre de Fermat 1601-1665) 是好 友。十七世紀，費馬也曾對完全數 (Perfect Number) 的問題有興趣。他考察過如 2p – 1 的數的質性。 1640年 6月，費馬給梅森的信中提出三個定理，是 研究整數質數的基礎： 1. 若 n 不是質數，則 2n-1 也不是質數。 2. 若 n 是質數，則 2n-2 可被 2n 整除，即 2n-1 = 1 (mod n)，即後來的「費馬小定理」(Fermat's Little Theorem)。 3. 若 n 是質數除了 2kn+1 這種形式的數以外， 2n-1 不能被其他形式的質數整除。 • http://hk.geocities.com/goodprimes/CMersenne1.htm More : Mersenne Primes 梅森數 & 梅森質數 • 定理(1)相當於若 2n-1 是質數，則 n 是質數，反之 則未必成立。 • 梅森在其於1644年出版的著作《物理—數學探索》 的序言中提出在不超過 257 的 55 個質數中，僅當 p = 2、3、5、7、13、17、19、31、67、127 和 257， 這 11 個質數時，2p-1 為質數。他本人驗証了前七 個數，後四個數因計自算量太大而未能驗証。為了 紀念他，後人把形如 2p-1 的數稱為梅森數 (Mersenne Number, Mp)，形如 2p-1 的質數稱為梅 森質數 (Mersenne Prime) ，上述斷言稱為梅森猜想 (Mersenne‘s Conjecture) 。然而梅森在其論作中竟 有五個錯誤之多。 • http://hk.geocities.com/goodprimes/CMersenne1.htm More : Mersenne Primes 梅森數 & 梅森質數 • 其後的梅森質數的發現都是借助 GIMPS (Great Internet Mersenne Prime Search) 的程式協助。 • 44th Known Mersenne Prime Found!! • On September 4, 2006, in the same room just a few feet away from their last find, Dr. Curtis Cooper and Dr. Steven Boone's CMSU team broke their own world record, discovering the 44th known Mersenne prime, 232,582,657-1. The new prime at 9,808,358 digits is 650,000 digits larger than their previous record prime found last December. • http://www.mersenne.org/prime.htm Conjecture & Counterexamples Conjecture: integers n > 0, n2−n+41 is prime. Hmm, let’s see if we can find any counter-examples: 12−1+41 = 41 (prime) 22−2+41 = 4−2+41 = 43 (prime) 32−3+41 = 47 (prime) Looking good so far!! Can we conclude after showing that it checks out in, say, 20 or 30 cases, that the conjecture must be true? • NEVER_NEVER NEVER NEVER NEVER !!! # Of course, 412−41+41 is divisible by 41!! Even Great Mathematicians Can Propose False Conjectures! • Euler conjectured that for n > 2, the sum of n−1 nth powers of positive integers is not an nth power. Remained true for all cases checked for 200 years, but no proof was found. • Finally, in 1966, someone noticed that 275 + 845 + 1105 + 1335 = 1445. Larger counter-examples have also been found for n = 4, but none for n > 5 yet. Euler's Conjecture • Euler's conjecture is a conjecture in mathematics related to Fermat's last theorem which was proposed by Leonhard Euler in 1769. It states that for all integers n and k greater than 1, if the sum of n kth powers of positive integers is itself a kth power, then n is not smaller than k. In symbols, that is if , for n > 2 where each ai's are some particular (positive) integer and b is another integer, then n ≥ k. Euler's Conjecture • The conjecture was disproven by L. J. Lander and T. R. Parkin • • • in 1966 when they found the following counterexample for k = 5: 275 + 845 + 1105 + 1335 = 1445. In 1986, Noam Elkies found a method to construct counterexamples for the k = 4 case. His smallest counterexample was the following: 26824404 + 153656394 + 187967604 = 206156734. In 1988, Roger Frye subsequently found the smallest possible k = 4 counterexample by a direct computer search using techniques suggested by Elkies: 958004 + 2175194 + 4145604 = 4224814. In 1966 Lander, Parkin and John F. Selfridge conjectured that for every k > 3, if then n+m≥k . Fermat’s “Last Theorem” Theorem: xn+yn = zn has no solutions in integers xyz ≠ 0 with integer n > 2. - In the 1600s, Fermat famously claimed in a marginal note that he had a “wondrous proof” of the theorem. But unfortunately, if he had one, he never published it! - The theorem remained a publicly unproven conjecture for the next ~400 years! - Finally, a proof that requires hundreds of pages of advanced mathematics was found by Wiles at Princeton in 1990. It took him 10 years of work to find it! • Challenge: Find a short, simple proof of Fermat’s last theorem, and you will become instantly famous! Some Open Conjectures Conjecture 1: There are infinitely many primes of the form n2+1, where nZ. Conjecture 2: (Twin Prime Conjecture) There are infinitely pairs of primes of the form (p, p+2). Conjecture 3: (The Hailstone Problem) If h(x) = x/2 when x is even, and 3x+1 when x is odd, then xN nN hn(x) = 1 (where the superscript denotes composition of h with itself n times). Prove any of these, and you can probably have a lifetime career sitting around doing pure mathematics… Basic Number Theory The Integers & Division Of course, you already know what the integers are, and what division is… But: There are some specific notations, terminology, and theorems associated with these concepts which you may not know. These form the basics of number theory. - Vital in many important algorithms today (hash functions, cryptography, digital signatures). Divides, Factor, Multiple Let a,bZ with a0. Def.: a|b “a divides b” : (cZ: b=ac) “There is an integer c such that c times a equals b.” E.g., 312 True, but 37 False. Iff a divides b, then we say a is a factor or a divisor of b, and b is a multiple of a. E.g., “b is even” :≡ 2|b. Is 0 even? Is −4? Facts re: the Divides Relation Theorem: a, b, c Z: 1. a|0 2. (a|b a|c) a | (b + c) 3. a|b a|bc 4. (a|b b|c) a|c Proof of (2): a|b means there is an s such that b=as, and a|c means that there is a t such that c=at, so b+c = as+at = a(s+t), so a|(b+c). ■ More Detailed Version of Proof Show a, b, c Z: (a|b a|c) a | (b + c). • Let a, b, c be any integers such that a|b and a|c, and show that a | (b + c). • By defn. of “ | ” , we know s: b = as, and t: c = at. Let s, t, be such integers. • Then b+c = as + at = a(s+t), so u: b+c = au, namely u = s+t. Thus a|(b+c). Prime Numbers • An integer p>1 is prime iff it is not the product of two integers greater than 1: p>1 a, bN: a>1, b>1, ab = p. • The only positive factors of a prime p are 1 and p itself. Some primes: 2, 3, 5, 7, 11,... • Non-prime integers greater than 1 are called composite, because they can be composed by multiplying two integers greater than 1. Review So Far • a|b “a divides b” cZ: b=ac • “p is prime” p>1 aN: (1 < a < p a|p) • Terms factor, divisor, multiple, composite. Fundamental Theorem of Arithmetic • Every positive integer has a unique representation as the product of a non-decreasing series of zero or more primes. Examples: - 1 = (product of empty series) = 1 - 2 = 2 (product of series with one element 2) - 4 = 2·2 (product of series 2, 2) - 2000 = 2·2·2·2·5·5·5; 2001 = 3·23·29; - 2002 = 2·7·11·13; 2003 = 2003 (no clear pattern!) Later, we will see how to rigorously prove the Fundamental Theorem of Arithmetic, starting from scratch! An Application of Primes! • When you visit a secure web site (https:… address, indicated by padlock icon in IE, key icon in Netscape), the browser and web site may be using a technology called RSA encryption. • This public-key cryptography scheme involves exchanging public keys containing the product pq of two random large primes p and q (a private key) which must be kept secret by a given party. • So, the security of your day-to-day web transactions depends critically on the fact that all known factoring algorithms are intractable! … 密碼學 … Note: There is a tractable quantum algorithm for factoring; so if we can ever build big quantum computers, then RSA is not secure. The Division “Algorithm” • It’s really just a theorem, not an algorithm… – Only called an “algorithm” for historical reasons. Theorem: For any integer dividend a and divisor d≠0, there is a unique integer quotient q and remainder rN such that a = dq + r and 0 r < |d|. Formally, the thm. is: a, dZ, d≠0: !q, rZ: 0r<|d|, a=dq+r. • We can find q and r by: q = [ad], r = adq. Greatest Common Divisor • The greatest common divisor gcd(a, b) of integers a, b (not both 0) is the largest (most positive) integer d that is a divisor both of a and of b. d = gcd(a, b) = max(d: d|a d|b) d|a d|b eZ, (e|a e|b) → d ≥ e Example: gcd(24, 36)=? Positive common divisors: 1, 2, 3, 4, 6, 12. The largest one of these is 12. GCD Shortcut • If the prime factorizations are written as a a a a p1 1 p2 2 pn n and b p1b1 p2b2 pnbn , then the GCD is given by: gcd( a, b) p min( a1 ,b1 ) 1 p min( a2 ,b2 ) 2 p min( an ,bn ) n • Example of using the shortcut: a=84=2·2·3·7 = 22·31·71 b=96=2·2·2·2·2·3 = 25·31·70 gcd(84,96) = 22·31·70 = 2·2·3 = 12. . Relatively Prime • Integers a and b are called relatively prime or coprime iff their gcd = 1. E.g., Neither 21 nor 10 is prime, but they are coprime. 21= 3·7 and 10 = 2·5, so they have no common factors > 1, so their gcd = 1. • A set of integers {a1, a2,…} is (pairwise) relatively prime if all pairs (ai, aj), for ij, are relatively prime. Least Common Multiple • lcm(a,b) of positive integers a, b, is the smallest positive integer that is a multiple both of a and of b. E.g., lcm(6,10)=30 m = lcm(a,b) = min(m: a|m b|m) a|m b|m nZ: (a|n b|n) → (m ≤ n) • If the prime factorizations are written as bn b1 b2 a a a a p1 p2 pn and b p1 p2 pn , then the LCM is given by 1 n 2 lcm (a, b) p max( a1 ,b1 ) 1 p max( a2 ,b2 ) 2 p max( an ,bn ) n . The mod Operator • An integer “division remainder” operator. • Let a, dZ with d>1. Then a mod d denotes the remainder r from the division “algorithm” with dividend a and divisor d; i.e. the remainder when a is divided by d. - Using e.g. long division. • We can compute (a mod d) by: a d·[a/d]. • In C/C++/Java languages, “%” = mod. Modular Congruence • Let a, bZ, mZ+ , where Z+ = {nZ | n>0}=N−{0} (the + integers). • Then a is congruent to b modulo m, written “ab (mod m)”, iff m | ab . (同餘的) Note: this is a different use of “” than the meaning “is defined as” we’ve used before. • It’s also equivalent to: (ab) mod m = 0. Spiral Visualization of mod ≡0 (mod 5) 20 15 ≡1 10 (mod 5) ≡ 4 19 21 5 14 9 16 (mod 5) 0 4 6 11 1 3 2 8 7 13 12 18 17 22 ≡ 2 ≡3 (mod 5) (mod 5) E.g., modulo-5 arithmetic Useful Congruence Theorems Theorem: Let a, bZ, mZ+. Then: ab (mod m) kZ a=b+km. Theorem: Let a, b, c, dZ, mZ+. Then if ab (mod m) and cd (mod m), then: . a+c b+d (mod m), and . ac bd (mod m)