Ch.4: Elementary Number Theory and Methods of Proof

Chapter 4 of the book "Discrete Mathematics with Applications" by Susanna S. Epp (4th edition) 4.1. Direct Proof and Counterexample I: Introduction 4.2. Direct Proof and Counterexample II: Rational Numbers 4.3. Direct Proof and Counterexample III: Divisibility 4.4. Direct Proof and Counterexample IV: Division into Cases and the Quotient-Remainder Theorem 4.5. Direct Proof and Counterexample V: Floor and Ceiling 4.6. Indirect Argument: Contradiction and Contraposition 4.7. Indirect Argument: Two Classical Theorems 4.8. Application: Algorithms

200 flashcards · Mathematics · by lakesare

Part of Textbooks › Discrete Mathematics with Applications (Susanna Epp) · 12 courses

1. [Direct Proof I: Introduction] Which facts about integers does the book assume in its proofs, besides the laws of basic algebra?

   There is no integer between 0 and 1, and the integers are closed under addition, subtraction and multiplication. So sums, differences and products of integers are integers. Most quotients are not: 3÷2=3/23 \div 2 = 3/23÷2=3/2 is not an integer, and 3÷03 \div 03÷0 is not a number.

2. [Direct Proof I: Introduction] Which three properties of equality does the book assume, for all objects A,B,CA, B, CA,B,C ?

   A=AA = AA=A ; if A=BA = BA=B then B=AB = AB=A ; if A=BA = BA=B and B=CB = CB=C then A=CA = CA=C .

3. [Direct Proof I: Introduction] When is an integer nnn even?

   n=2kn = 2kn=2k for some integer kkk ( nnn equals twice some integer). Example: 0=2⋅00 = 2 \cdot 00=2⋅0 is even; −6=2⋅(−3)-6 = 2 \cdot (-3)−6=2⋅(−3) is even.

4. [Direct Proof I: Introduction] When is an integer nnn odd?

   n=2k+1n = 2k + 1n=2k+1 for some integer kkk ( nnn equals twice some integer plus 1). Example: −301=2(−151)+1-301 = 2(-151) + 1−301=2(−151)+1 is odd.

5. [Direct Proof I: Introduction] aaa and bbb are integers. Is 6a2b6a^2b6a2b even? Justify from the definition.

   Yes: 6a2b=2(3a2b)6a^2b = 2(3a^2b)6a2b=2(3a2b) , and 3a2b3a^2b3a2b is an integer (a product of integers).

6. [Direct Proof I: Introduction] aaa and bbb are integers. Is 10a+8b+110a + 8b + 110a+8b+1 odd? Justify from the definition.

   Yes: 10a+8b+1=2(5a+4b)+110a + 8b + 1 = 2(5a + 4b) + 110a+8b+1=2(5a+4b)+1 , and 5a+4b5a + 4b5a+4b is an integer (a sum of products of integers).

7. [Direct Proof I: Introduction] When is an integer nnn prime?

   n>1n > 1n>1 , and for all positive integers r,sr, sr,s : if n=rsn = rsn=rs then r=nr = nr=n or s=ns = ns=n . Equivalently, n>1n > 1n>1 cannot be written as a product of two smaller positive integers.Example: 7=1⋅7=7⋅17 = 1 \cdot 7 = 7 \cdot 17=1⋅7=7⋅1 only, so 7 is prime.

8. [Direct Proof I: Introduction] When is an integer nnn composite?

   n>1n > 1n>1 and n=rsn = rsn=rs for some integers r,sr, sr,s with 1<r<n1 < r < n1<r<n and 1<s<n1 < s < n1<s<n . Example: 6=2⋅36 = 2 \cdot 36=2⋅3 is composite.

9. [Direct Proof I: Introduction] Is 1 prime?

   No: a prime must be greater than 1. 1 is not composite either.

10. [Direct Proof I: Introduction] What are the first six prime numbers and the first six composite numbers?

    Primes: 2, 3, 5, 7, 11, 13. Composites: 4, 6, 8, 9, 10, 12.

11. [Direct Proof I: Introduction] Why is every integer n>1n > 1n>1 either prime or composite?

    Either 1⋅n1 \cdot n1⋅n and n⋅1n \cdot 1n⋅1 are the only factorizations n=rsn = rsn=rs (prime), or some n=rsn = rsn=rs has 1<r<n1 < r < n1<r<n and 1<s<n1 < s < n1<s<n (composite). Every factorization n=rsn = rsn=rs into positive integers has 1≤r≤n1 \le r \le n1≤r≤n and 1≤s≤n1 \le s \le n1≤s≤n , so a factorization other than 1⋅n1 \cdot n1⋅n and n⋅1n \cdot 1n⋅1 has r,sr, sr,s strictly between 1 and nnn .

12. [Direct Proof I: Introduction] What is a constructive proof of existence of an x∈Dx \in Dx∈D with Q(x)Q(x)Q(x) ?

    A proof that finds an xxx in DDD that makes Q(x)Q(x)Q(x) true, or gives a set of directions for finding such an xxx .

13. [Direct Proof I: Introduction] Prove: there is an even integer nnn that can be written in two ways as a sum of two prime numbers.

    n=10n = 10n=10 : 10=5+5=3+710 = 5 + 5 = 3 + 710=5+5=3+7 , and 3, 5, 7 are prime. A constructive proof of existence: it exhibits the integer.

14. [Direct Proof I: Introduction] rrr and sss are integers. Prove: there is an integer kkk such that 22r+18s=2k22r + 18s = 2k22r+18s=2k .

    Let k=11r+9sk = 11r + 9sk=11r+9s . Then kkk is an integer (a sum of products of integers) and 2k=22r+18s2k = 22r + 18s2k=22r+18s by the distributive law.

15. [Direct Proof I: Introduction] What is a nonconstructive proof of existence, and what is its disadvantage?

    A proof that xxx exists either because an axiom or a proved theorem guarantees it, or because assuming no such xxx exists leads to a contradiction. Disadvantage: it may give no clue where or how xxx can be found.

16. [Direct Proof I: Introduction] How do you disprove a statement of the form " ∀x∈D\forall x \in D∀x∈D , if P(x)P(x)P(x) then Q(x)Q(x)Q(x) "?

    Find an xxx in DDD with P(x)P(x)P(x) true and Q(x)Q(x)Q(x) false, a counterexample. This proves the negation " ∃x∈D\exists x \in D∃x∈D such that P(x)P(x)P(x) and not Q(x)Q(x)Q(x) ".

17. [Direct Proof I: Introduction] Disprove by counterexample: ∀\forall∀ real numbers aaa and bbb , if a2=b2a^2 = b^2a2=b2 then a=ba = ba=b .

    a=1a = 1a=1 , b=−1b = -1b=−1 : a2=1=b2a^2 = 1 = b^2a2=1=b2 , but 1≠−11 \ne -11=−1 . A true restricted version: if the squares of two positive numbers are equal, the numbers are equal.

18. [Direct Proof I: Introduction] When can a universal statement " ∀x∈D\forall x \in D∀x∈D , if P(x)P(x)P(x) then Q(x)Q(x)Q(x) " be proved by the method of exhaustion?

    When DDD is finite, or only finitely many elements of DDD satisfy P(x)P(x)P(x) : check every such element. Example: every even nnn with 4≤n≤264 \le n \le 264≤n≤26 is a sum of two primes: 4=2+24 = 2 + 24=2+2 , 6=3+36 = 3 + 36=3+3 , 8=3+58 = 3 + 58=3+5 , 10=5+510 = 5 + 510=5+5 , 12=5+712 = 5 + 712=5+7 , 14=11+314 = 11 + 314=11+3 , 16=5+1116 = 5 + 1116=5+11 , 18=7+1118 = 7 + 1118=7+11 , 20=7+1320 = 7 + 1320=7+13 , 22=5+1722 = 5 + 1722=5+17 , 24=5+1924 = 5 + 1924=5+19 , 26=7+1926 = 7 + 1926=7+19 .

19. [Direct Proof I: Introduction] Why can't the method of exhaustion prove that every even integer greater than 2 is a sum of two primes?

    There are infinitely many even integers to check. Even for a finite domain exhaustion can be impractical, e.g. checking every product a computer's multiplication circuit can compute.

20. [Direct Proof I: Introduction] What is the method of generalizing from the generic particular?

    To show that every element of a set has a property: suppose xxx is a particular but arbitrarily chosen element, and show that xxx has the property.

21. [Direct Proof I: Introduction] In the method of generalizing from the generic particular, why must xxx be arbitrarily chosen (generic)?

    So that nothing is assumed about xxx that is not true of every element; then all that is deduced about xxx holds for every element. Generic means "sharing all the common characteristics of a group or class".

22. [Direct Proof I: Introduction] Pick any number, add 5, multiply by 4, subtract 6, divide by 2, subtract twice the original number. Why is the result always 7?

    With xxx for the number: (x+5)⋅4−62−2x=4x+142−2x=(2x+7)−2x=7\dfrac{(x + 5) \cdot 4 - 6}{2} - 2x = \dfrac{4x + 14}{2} - 2x = (2x + 7) - 2x = 72(x+5)⋅4−6​−2x=24x+14​−2x=(2x+7)−2x=7 . xxx is particular (one quantity) but arbitrarily chosen (any number can be put in its place), so the computation holds for every number.

23. [Direct Proof I: Introduction] What are the three steps of the method of direct proof?

    Restate Express the statement in the form " ∀x∈D\forall x \in D∀x∈D , if P(x)P(x)P(x) then Q(x)Q(x)Q(x) " (often done mentally). Suppose Suppose xxx is a particular but arbitrarily chosen element of DDD for which P(x)P(x)P(x) is true ("Suppose x∈Dx \in Dx∈D and P(x)P(x)P(x) "). Show Show that Q(x)Q(x)Q(x) is true, using definitions, previously established results and the rules of logical inference. It works because "if P(x)P(x)P(x) then Q(x)Q(x)Q(x) " can be false only when P(x)P(x)P(x) is true…

24. [Direct Proof I: Introduction] What does the rule of existential instantiation say?

    If an object is assumed or deduced to exist, it can be given a name, as long as that name is not already used for something else. Example: mmm is even, so m=2rm = 2rm=2r for some integer rrr ; from then on rrr names that integer.

25. [Direct Proof I: Introduction] Theorem. The sum of any two even integers is even. How does the proof go?

    m=2rm = 2rm=2r and n=2sn = 2sn=2s for integers r,sr, sr,s , so m+n=2(r+s)m + n = 2(r + s)m+n=2(r+s) with r+sr + sr+s an integer. Proof: suppose mmm and nnn are particular but arbitrarily chosen even integers. By definition of even, m=2rm = 2rm=2r and n=2sn = 2sn=2s for some integers r,sr, sr,s . Then m+n=2r+2s=2(r+s)m + n = 2r + 2s = 2(r + s)m+n=2r+2s=2(r+s) . Let t=r+st = r + st=r+s ; ttt is an integer as a sum of integers, so m+n=2tm + n = 2tm+n=2t is even by definition of even.

26. [Direct Proof I: Introduction] Proof that the sum of any two even integers is even: mmm and nnn are even, so m=2rm = 2rm=2r and n=2sn = 2sn=2s for integers r,sr, sr,s ; then m+n=2(r+s)m + n = 2(r + s)m+n=2(r+s) , so m+nm + nm+n is even.Which directions of the definition " nnn is even ⇔\Leftrightarrow⇔ n=2kn = 2kn=2k for some integer kkk " does the proof use, and where?

    Both: "only if" ( ⇒\Rightarrow⇒ ) to write m=2rm = 2rm=2r , n=2sn = 2sn=2s ; "if" ( ⇐\Leftarrow⇐ ) to conclude from m+n=2(r+s)m + n = 2(r + s)m+n=2(r+s) that m+nm + nm+n is even.

27. [Direct Proof I: Introduction] Why may a proof that mmm and nnn are even not write " m=2rm = 2rm=2r and n=2rn = 2rn=2r for some integer rrr "?

    That says m=nm = nm=n , so the proof would cover only pairs of equal even integers, not arbitrarily chosen mmm and nnn . Once rrr is introduced with m=2rm = 2rm=2r , nnn needs a new name: n=2sn = 2sn=2s .

28. [Direct Proof I: Introduction] Proofs in older books end with the initials QED, for quod erat demonstrandum, "this is what we needed to show".

29. [Direct Proof I: Introduction] What are the eight rules of style for writing the final version of a proof?

    Copy the statement Copy the statement of the theorem to be proved. Mark the beginning Clearly mark the beginning of the proof with the word Proof. Self-contained Explain the meaning of each variable used, as when declaring variables in a program. Example: "Suppose mmm and nnn are any even integers." Complete sentences Write the proof in complete, grammatically correct sentences; symbols are part of the sentences. Example: "Then m+n=2r+2s=2(r+s)m + n = 2r + 2s = 2(r + s)m+n=2r+2s=2(r+s) " reads…

30. [Direct Proof I: Introduction] What are the seven common mistakes in writing proofs that the book lists?

    Arguing from examples Example: " m=14m = 14m=14 and n=6n = 6n=6 are even and m+n=20m + n = 20m+n=20 is even" does not prove that every sum of two even integers is even. Using the same letter to mean two different things Example: " m=2k+1m = 2k + 1m=2k+1 and n=2k+1n = 2k + 1n=2k+1 for some integer kkk " forces m=nm = nm=n . Jumping to a conclusion Stating something without an adequate reason. Example: " m+n=2r+2sm + n = 2r + 2sm+n=2r+2s . So m+nm + nm+n is even" omits 2r+2s=2(r+s)2r + 2s = 2(r +…

31. [Direct Proof I: Introduction] "Proof" that the product of two odd integers is odd: suppose mmm and nnn are odd. We must show that mnmnmn is odd. This means that there exists an integer sss with mn=2s+1mn = 2s + 1mn=2s+1 . Also m=2a+1m = 2a + 1m=2a+1 and n=2b+1n = 2b + 1n=2b+1 for some integers a,ba, ba,b . Then mn=(2a+1)(2b+1)=2s+1mn = (2a + 1)(2b + 1) = 2s + 1mn=(2a+1)(2b+1)=2s+1 , so mnmnmn is odd.What is wrong?

    It treats sss as known, but the existence of sss with mn=2s+1mn = 2s + 1mn=2s+1 is exactly what must be shown. Safer: introduce a variable only if it is part of the hypothesis or deducible from it.

32. [Direct Proof I: Introduction] "Proof" fragment: suppose mmm is a particular but arbitrarily chosen odd integer. By definition of odd, m=2a+1m = 2a + 1m=2a+1 for any integer aaa .What is wrong?

    "For any integer aaa " should be "for some integer aaa ": solving m=2a+1m = 2a + 1m=2a+1 gives the single value a=(m−1)/2a = (m - 1)/2a=(m−1)/2 .

33. [Direct Proof I: Introduction] Why can you write the first and last sentence of a proof even for a theorem you do not understand?

    The starting point and the conclusion to be shown depend only on the linguistic form of the statement, not on its content.

34. [Direct Proof I: Introduction] Write the starting point and the conclusion to be shown in a proof of: every complete, bipartite graph is connected.

    Start: "Suppose GGG is a graph such that GGG is complete and bipartite." Conclusion to be shown: " GGG is connected." GGG is particular but arbitrarily chosen. The starting point supposes an element of the domain satisfying the hypothesis; the last sentence is the conclusion.

35. [Direct Proof I: Introduction] How do you prove that an existential statement " ∃x∈D\exists x \in D∃x∈D such that Q(x)Q(x)Q(x) " is false?

    Prove its negation, the universal statement " ∀x∈D\forall x \in D∀x∈D , not Q(x)Q(x)Q(x) ", e.g. by generalizing from the generic particular.

36. [Direct Proof I: Introduction] Show that there is no positive integer nnn such that n2+3n+2n^2 + 3n + 2n2+3n+2 is prime.

    n2+3n+2=(n+1)(n+2)n^2 + 3n + 2 = (n + 1)(n + 2)n2+3n+2=(n+1)(n+2) with both factors integers greater than 1 (since n≥1n \ge 1n≥1 ), so it is not prime. Example: n=1n = 1n=1 gives 6=2⋅36 = 2 \cdot 36=2⋅3 .

37. [Direct Proof I: Introduction] What does Fermat's last theorem state, and who proved it?

    There are no positive integers x,y,zx, y, zx,y,z with xn+yn=znx^n + y^n = z^nxn+yn=zn for an integer n≥3n \ge 3n≥3 . Proved by Andrew Wiles (published 1995). Fermat (1601 to 1665) claimed it in a book's margin, writing that he had a proof the margin was too small to contain. For n=2n = 2n=2 there are solutions: 32+42=523^2 + 4^2 = 5^232+42=52 .

38. [Direct Proof I: Introduction] What does the Goldbach conjecture state?

    Every even integer greater than 2 is a sum of two prime numbers. Unsolved; computer checks confirm it up to at least 101810^{18}1018 .Example: 26=7+1926 = 7 + 1926=7+19 .

39. [Direct Proof I: Introduction] Euler conjectured that a4+b4+c4=d4a^4 + b^4 + c^4 = d^4a4+b4+c4=d4 has no nontrivial whole-number solutions. Was he right?

    No: Noam Elkies disproved it in 1987. A counterexample found by computer search: 95,8004+217,5194+414,5604=422,481495{,}800^4 + 217{,}519^4 + 414{,}560^4 = 422{,}481^495,8004+217,5194+414,5604=422,4814 .

40. [Direct Proof II: Rational Numbers] When is a real number rrr rational, and when is it irrational?

    Rational: r=abr = \frac{a}{b}r=ba​ for some integers a,ba, ba,b with b≠0b \ne 0b=0 . Irrational: real but not rational. Example: 103\frac{10}{3}310​ and −539=−539-\frac{5}{39} = \frac{-5}{39}−395​=39−5​ are rational.

41. [Direct Proof II: Rational Numbers] Are 0.2810.2810.281 , 777 and 000 rational?

    Yes: 0.281=28110000.281 = \frac{281}{1000}0.281=1000281​ , 7=717 = \frac{7}{1}7=17​ , 0=010 = \frac{0}{1}0=10​ . Every finite decimal is rational, so a calculator with a finite-decimal display shows only rational numbers.

42. [Direct Proof II: Rational Numbers] Is 2/02/02/0 rational? Is it irrational?

    Neither: 2/02/02/0 is not a number (division by 0 is not allowed), and irrational numbers are real numbers.

43. [Direct Proof II: Rational Numbers] Write 0.12121212…0.12121212\ldots0.12121212… (the digits 12 repeating forever) as a ratio of integers.

    1299\boldsymbol{\frac{12}{99}}9912​ Let x=0.1212…x = 0.1212\ldotsx=0.1212… ; then 100x=12.1212…100x = 12.1212\ldots100x=12.1212… , so 99x=100x−x=1299x = 100x - x = 1299x=100x−x=12 .The same argument shows that every repeating decimal is rational.

44. [Direct Proof II: Rational Numbers] What does the zero product property say?

    If neither of two real numbers is zero, their product is not zero. Equivalently: if ab=0ab = 0ab=0 , then a=0a = 0a=0 or b=0b = 0b=0 .

45. [Direct Proof II: Rational Numbers] mmm and nnn are nonzero integers. Is m+nmn\frac{m + n}{mn}mnm+n​ rational?

    Yes: m+nm + nm+n and mnmnmn are integers, and mn≠0mn \ne 0mn=0 by the zero product property.

46. [Direct Proof II: Rational Numbers] How can the method of generalizing from the generic particular be seen as a challenge process?

    A challenger picks any element of the domain; you must be able to show that the chosen element has the property, for every possible choice. So you need a general procedure that works for an arbitrarily chosen element.

47. [Direct Proof II: Rational Numbers] Why is every integer a rational number?

    Any integer nnn equals n1\frac{n}{1}1n​ , a quotient of integers with nonzero denominator. Example: −12=−121-12 = \frac{-12}{1}−12=1−12​ , 0=010 = \frac{0}{1}0=10​ .

48. [Direct Proof II: Rational Numbers] Restate formally: "the sum of any two rational numbers is rational".

    ∀\forall∀ real numbers rrr and sss , if rrr and sss are rational then r+sr + sr+s is rational. Starting point: "Suppose rrr and sss are rational numbers." To show: " r+sr + sr+s is rational."

49. [Direct Proof II: Rational Numbers] Theorem. The sum of any two rational numbers is rational. How does the proof go?

    r=abr = \frac{a}{b}r=ba​ , s=cds = \frac{c}{d}s=dc​ with integers a,b,c,da, b, c, da,b,c,d , b,d≠0b, d \ne 0b,d=0 ; then r+s=ad+bcbdr + s = \frac{ad + bc}{bd}r+s=bdad+bc​ . ad+bcad + bcad+bc and bdbdbd are integers (sums and products of integers), and bd≠0bd \ne 0bd=0 by the zero product property, so r+sr + sr+s is rational by definition.Example: 12+23=1⋅3+2⋅22⋅3=76\frac{1}{2} + \frac{2}{3} = \frac{1 \cdot 3 + 2 \cdot 2}{2 \cdot 3} = \frac{7}{6}21​+32​=2⋅31⋅3+2⋅2​=67​ .

50. [Direct Proof II: Rational Numbers] What does it mean to prove something directly from the definitions?

    Using only basic algebra, the closure of the integers under +++ , −-− , ×\times× , and the definitions of the terms in the statement. No previously proved theorems about those terms.

51. [Direct Proof II: Rational Numbers] Known: the sum and difference of two odd integers are even; the product of two odd integers is odd; the product of two even integers is even; the sum of an odd and an even integer is odd. aaa is even and bbb is odd. Why is a2+b2+12\frac{a^2 + b^2 + 1}{2}2a2+b2+1​ an integer?

    a2+b2a^2 + b^2a2+b2 is odd (even plus odd), so a2+b2+1a^2 + b^2 + 1a2+b2+1 is even (odd plus odd), i.e. =2k= 2k=2k , and the quotient is kkk . b2=b⋅bb^2 = b \cdot bb2=b⋅b is odd (product of odd integers), a2=a⋅aa^2 = a \cdot aa2=a⋅a is even (product of even integers).Example: a=2a = 2a=2 , b=3b = 3b=3 : 4+9+12=7\frac{4 + 9 + 1}{2} = 724+9+1​=7 .

52. [Direct Proof II: Rational Numbers] A corollary is a statement whose truth can be immediately deduced from a theorem that has already been proved.

53. [Direct Proof II: Rational Numbers] The sum of any two rational numbers is rational.Derive from this: the double of a rational number is rational.

    2r=r+r2r = r + r2r=r+r is a sum of two rational numbers, so it is rational.

54. [Direct Proof III: Divisibility] nnn and ddd are integers, d≠0d \neq 0d=0 . When is nnn divisible by ddd ?

    When n=dkn = dkn=dk for some integer kkk . Written d∣nd \mid nd∣n , read " ddd divides nnn ": d∣n⇔∃\; d \mid n \Leftrightarrow \existsd∣n⇔∃ an integer kkk such that n=dkn = dkn=dk .Example: 3∣213 \mid 213∣21 since 21=3⋅721 = 3 \cdot 721=3⋅7 .

55. [Direct Proof III: Divisibility] nnn and ddd are integers with d≠0d \neq 0d=0 . Besides " nnn is divisible by ddd ", what four phrases say the same thing?

    nnn is a multiple of ddd Example: 323232 is a multiple of −16-16−16 , since 32=(−16)⋅(−2)32 = (-16) \cdot (-2)32=(−16)⋅(−2) . ddd is a factor of nnn Example: 666 is a factor of 545454 , since 54=6⋅954 = 6 \cdot 954=6⋅9 . ddd is a divisor of nnn Example: 777 is a divisor of −7-7−7 , since −7=7⋅(−1)-7 = 7 \cdot (-1)−7=7⋅(−1) . ddd divides nnn Example: 555 divides 404040 , since 40=5⋅840 = 5 \cdot 840=5⋅8 .

56. [Direct Proof III: Divisibility] kkk is a nonzero integer. Does kkk divide 000 ?

    Yes, because 0=k⋅00 = k \cdot 00=k⋅0 . So every nonzero integer is a divisor of 0.

57. [Direct Proof III: Divisibility] Theorem 4.3.1 (A Positive Divisor of a Positive Integer) For all integers aaa and bbb , if aaa and bbb are positive and a∣ba \mid ba∣b , then … ?

    a≤b\boldsymbol{a \le b}a≤b Example: the positive divisors of 12 are 1,2,3,4,6,121, 2, 3, 4, 6, 121,2,3,4,6,12 , all ≤12\le 12≤12 .

58. [Direct Proof III: Divisibility] For all positive integers aaa and bbb : if a∣ba \mid ba∣b , then a≤ba \le ba≤b .How does the proof go?

    b=akb = akb=ak with kkk positive, so k≥1k \ge 1k≥1 ; multiplying by a>0a > 0a>0 gives a≤ak=ba \le ak = ba≤ak=b . kkk is positive because aaa and bbb are positive.

59. [Direct Proof III: Divisibility] Theorem 4.3.2 (Divisors of 1) Which integers divide 1?

    Only 111 and −1-1−1 . 1⋅1=11 \cdot 1 = 11⋅1=1 and (−1)(−1)=1(-1)(-1) = 1(−1)(−1)=1 .

60. [Direct Proof III: Divisibility] For all positive integers aaa and bbb : if a∣ba \mid ba∣b , then a≤ba \le ba≤b .Why are 111 and −1-1−1 the only divisors of 1?

    If m∣1m \mid 1m∣1 , then 1=mn1 = mn1=mn with mmm and nnn of the same sign. If m>0m > 0m>0 , then m≤1m \le 1m≤1 , so m=1m = 1m=1 ; if m<0m < 0m<0 , then −m-m−m is a positive divisor of 1, so −m=1-m = 1−m=1 . −m-m−m divides 1 because (−m)(−n)=mn=1(-m)(-n) = mn = 1(−m)(−n)=mn=1 .

61. [Direct Proof III: Divisibility] kkk and mmm are integers. Is 10km10km10km divisible by 555 ? Is 3k+3m3k + 3m3k+3m divisible by 333 ?

    Yes and yes: 10km=5⋅(2km)10km = 5 \cdot (2km)10km=5⋅(2km) and 3k+3m=3(k+m)3k + 3m = 3(k + m)3k+3m=3(k+m) . 2km2km2km and k+mk + mk+m are integers, because products and sums of integers are integers.

62. [Direct Proof III: Divisibility] nnn and ddd are integers, d≠0d \neq 0d=0 . When does ddd not divide nnn (written d∤nd \nmid nd∤n )?

    When nd\dfrac{n}{d}dn​ is not an integer. Negating " ∃\exists∃ an integer kkk with n=dkn = dkn=dk " gives " ∀\forall∀ integers kkk , n≠dkn \neq dkn=dk ".Example: 4∤154 \nmid 154∤15 , since 154=3.75\frac{15}{4} = 3.75415​=3.75 .

63. [Direct Proof III: Divisibility] What is the difference between the notations a∣ba \mid ba∣b and a/ba / ba/b ?

    a∣ba \mid ba∣b is a sentence (" aaa divides bbb ", true or false); a/ba / ba/b is a number ( aaa divided by bbb ). So " 4∣(3+5)=4∣84 \mid (3 + 5) = 4 \mid 84∣(3+5)=4∣8 " is nonsense: it equates two sentences with " === ".Example: 3∣123 \mid 123∣12 is true, and 12/3=412 / 3 = 412/3=4 .

64. [Direct Proof III: Divisibility] How can you define " nnn is prime" using divisors?

    An integer n>1n > 1n>1 is prime if, and only if, its only positive integer divisors are 111 and nnn . Example: the positive divisors of 7 are 1 and 7, so 7 is prime; 9 has the divisor 3, so 9 is not prime.

65. [Direct Proof III: Divisibility] Theorem 4.3.3 (Transitivity of Divisibility) For all integers aaa , bbb and ccc , if a∣ba \mid ba∣b and b∣cb \mid cb∣c , then … ?

    a∣c\boldsymbol{a \mid c}a∣c Example: 3∣63 \mid 63∣6 and 6∣246 \mid 246∣24 , so 3∣243 \mid 243∣24 .

66. [Direct Proof III: Divisibility] aaa , bbb , ccc are integers. How do you prove: if a∣ba \mid ba∣b and b∣cb \mid cb∣c , then a∣ca \mid ca∣c ?

    Write b=arb = arb=ar and c=bsc = bsc=bs ; substituting gives c=(ar)s=a(rs)c = (ar)s = a(rs)c=(ar)s=a(rs) , and rsrsrs is an integer. So c=a⋅(some integer)c = a \cdot (\text{some integer})c=a⋅(some integer) , which is the definition of a∣ca \mid ca∣c .

67. [Direct Proof III: Divisibility] Theorem 4.3.4 (Divisibility by a Prime) What does it say about every integer n>1n > 1n>1 ?

    nnn is divisible by a prime number. Example: 91=7⋅1391 = 7 \cdot 1391=7⋅13 is divisible by the prime 7.

68. [Direct Proof III: Divisibility] How does the proof show that every integer n>1n > 1n>1 is divisible by a prime?

    If nnn is not prime, factor it: n=r0s0n = r_0 s_0n=r0​s0​ with 1<r0<n1 < r_0 < n1<r0​<n ; if r0r_0r0​ is not prime, factor r0=r1s1r_0 = r_1 s_1r0​=r1​s1​ with 1<r1<r01 < r_1 < r_01<r1​<r0​ , and so on, until some rkr_krk​ is prime. Each rir_iri​ divides nnn by transitivity of divisibility. The process stops because 1<rk<⋯<r1<r0<n1 < r_k < \dots < r_1 < r_0 < n1<rk​<⋯<r1​<r0​<n and there are fewer than nnn integers between 1 and nnn .Example: n=72n = 72n=72 : 72=12⋅672 = 12 \cdot 672=12⋅6 , 12=4…

69. [Direct Proof III: Divisibility] To check that an integer n>1n > 1n>1 is prime, which possible divisors is it enough to test?

    The prime numbers less than nnn . If n=abn = abn=ab with 1<a<n1 < a < n1<a<n , then aaa is divisible by some prime ppp , so p∣np \mid np∣n (transitivity) and p≤a<np \le a < np≤a<n .Example: 97 is prime, because none of 2,3,5,7,…,892, 3, 5, 7, \dots, 892,3,5,7,…,89 divides it.

70. [Direct Proof III: Divisibility] True or false: for all integers aaa and bbb , if a∣ba \mid ba∣b and b∣ab \mid ab∣a , then a=ba = ba=b .

    False. Counterexample: a=2a = 2a=2 , b=−2b = -2b=−2 . 2∣(−2)2 \mid (-2)2∣(−2) and (−2)∣2(-2) \mid 2(−2)∣2 , but 2≠−22 \neq -22=−2 .

71. [Direct Proof III: Divisibility] Claim: for all integers aaa and bbb , if a∣ba \mid ba∣b and b∣ab \mid ab∣a , then a=ba = ba=b .How does trying to prove the claim lead to a counterexample?

    b=kab = kab=ka and a=lba = lba=lb give b=(kl)bb = (kl)bb=(kl)b , so kl=1kl = 1kl=1 and k=l=±1k = l = \pm 1k=l=±1 . The case k=l=−1k = l = -1k=l=−1 gives b=−ab = -ab=−a , which suggests a=2a = 2a=2 , b=−2b = -2b=−2 . Cancelling bbb is allowed because b∣ab \mid ab∣a requires b≠0b \neq 0b=0 . The search for a proof often reveals a counterexample, and the search for a counterexample often reveals why a statement is true.

72. [Direct Proof III: Divisibility] What does the unique factorization of integers theorem say?

    Every integer n>1n > 1n>1 is prime or a product of primes, in exactly one way apart from the order of the factors. In symbols: n=p1e1p2e2⋯pkekn = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}n=p1e1​​p2e2​​⋯pkek​​ for distinct primes pip_ipi​ and positive integers eie_iei​ , and any other expression of nnn as a product of primes differs from this one only in the order of the factors.Example: 72=2⋅2⋅2⋅3⋅3=3⋅2⋅2⋅3⋅272 = 2 \cdot 2 \cdot 2 \cdot 3 \cdot 3 = 3 \cdot 2 \cdot 2 \cdot 3 \cdot 272=2⋅2⋅2⋅3⋅3=3⋅2⋅2…

73. [Direct Proof III: Divisibility] The unique factorization of integers theorem is also called the fundamental theorem of arithmetic.

74. [Direct Proof III: Divisibility] Who first stated the unique factorization of integers theorem precisely, and when?

    Carl Friedrich Gauss, in 1801. Euclid (about 300 B.C.) seems to have known the theorem already.

75. [Direct Proof III: Divisibility] Why is the number 1 not defined to be prime?

    Prime factorizations would not be unique. Example: 6=2⋅3=1⋅2⋅3=1⋅1⋅2⋅36 = 2 \cdot 3 = 1 \cdot 2 \cdot 3 = 1 \cdot 1 \cdot 2 \cdot 36=2⋅3=1⋅2⋅3=1⋅1⋅2⋅3 .

76. [Direct Proof III: Divisibility] What is the standard factored form of an integer n>1n > 1n>1 ?

    n=p1e1p2e2⋯pkek\boldsymbol{n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}}n=p1e1​​p2e2​​⋯pkek​​ with primes p1<p2<⋯<pkp_1 < p_2 < \dots < p_kp1​<p2​<⋯<pk​ and positive integers e1,…,eke_1, \dots, e_ke1​,…,ek​ . The primes are written in ascending order; the unique factorization theorem says this form exists and is unique.Example: 72=23⋅3272 = 2^3 \cdot 3^272=23⋅32 .

77. [Direct Proof III: Divisibility] Write 3,3003{,}3003,300 in standard factored form.

    3,300=22⋅3⋅52⋅11\boldsymbol{3{,}300 = 2^2 \cdot 3 \cdot 5^2 \cdot 11}3,300=22⋅3⋅52⋅11 3,300=100⋅33=4⋅25⋅3⋅11=2⋅2⋅5⋅5⋅3⋅113{,}300 = 100 \cdot 33 = 4 \cdot 25 \cdot 3 \cdot 11 = 2 \cdot 2 \cdot 5 \cdot 5 \cdot 3 \cdot 113,300=100⋅33=4⋅25⋅3⋅11=2⋅2⋅5⋅5⋅3⋅11 .

78. [Direct Proof III: Divisibility] mmm is an integer with 8⋅7⋅6⋅5⋅4⋅3⋅2⋅m=17⋅16⋅15⋅14⋅13⋅12⋅11⋅108 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot m = 17 \cdot 16 \cdot 15 \cdot 14 \cdot 13 \cdot 12 \cdot 11 \cdot 108⋅7⋅6⋅5⋅4⋅3⋅2⋅m=17⋅16⋅15⋅14⋅13⋅12⋅11⋅10 . Does 17∣m17 \mid m17∣m ? Why?

    Yes. The prime 17 occurs in the factorization of the right side, so by unique factorization it occurs on the left, and no prime factor of 8,7,…,28, 7, \dots, 28,7,…,2 is 17. So 17 must be a prime factor of mmm .

79. [Direct Proof IV: Quotient-Remainder] What does the quotient-remainder theorem say about an integer nnn and a positive integer ddd ?

    There exist unique integers qqq and rrr such that n=dq+rn = dq + rn=dq+r and 0≤r<d0 \le r < d0≤r<d . qqq is the quotient and rrr the remainder.Example: n=11n = 11n=11 , d=4d = 4d=4 : 11=4⋅2+311 = 4 \cdot 2 + 311=4⋅2+3 , so q=2q = 2q=2 , r=3r = 3r=3 .

80. [Direct Proof IV: Quotient-Remainder] Quotient-remainder theorem: for an integer nnn and a positive integer ddd there are unique integers q,rq, rq,r with n=dq+rn = dq + rn=dq+r and 0≤r<d0 \le r < d0≤r<d .On the number line, which multiple of ddd is dqdqdq ?

    The largest multiple of ddd that is ≤n\le n≤n ; rrr is the distance from dqdqdq up to nnn . nnn positive. nnn negative: qqq is negative, and r≥0r \ge 0r≥0 is still added to dqdqdq to reach nnn .

81. [Direct Proof IV: Quotient-Remainder] Find integers qqq and rrr with −54=4q+r-54 = 4q + r−54=4q+r and 0≤r<40 \le r < 40≤r<4 .

    q=−14, r=2\boldsymbol{q = -14, \ r = 2}q=−14, r=2 −54=4⋅(−14)+2-54 = 4 \cdot (-14) + 2−54=4⋅(−14)+2 . Not q=−13q = -13q=−13 , r=−2r = -2r=−2 : the remainder must be nonnegative.

82. [Direct Proof IV: Quotient-Remainder] Find integers qqq and rrr with 54=70q+r54 = 70q + r54=70q+r and 0≤r<700 \le r < 700≤r<70 .

    q=0, r=54\boldsymbol{q = 0, \ r = 54}q=0, r=54 54=70⋅0+5454 = 70 \cdot 0 + 5454=70⋅0+54 .

83. [Direct Proof IV: Quotient-Remainder] nnn is an integer and ddd a positive integer. What are ndiv⁡dn \operatorname{div} dndivd and n mod dn \bmod dnmodd ?

    ndiv⁡d=qn \operatorname{div} d = qndivd=q and n mod d=rn \bmod d = rnmodd=r , where n=dq+rn = dq + rn=dq+r and 0≤r<d0 \le r < d0≤r<d . The integer quotient and the nonnegative remainder of dividing nnn by ddd .Example: 32div⁡9=332 \operatorname{div} 9 = 332div9=3 and 32 mod 9=532 \bmod 9 = 532mod9=5 , since 32=9⋅3+532 = 9 \cdot 3 + 532=9⋅3+5 .

84. [Direct Proof IV: Quotient-Remainder] Do the operators / and % of C or Java always give the qqq and rrr of the quotient-remainder theorem?

    No: only when n≥0n \ge 0n≥0 (and d>0d > 0d>0 ). For negative nnn they do not. Example: in C, −54 / 4=−13-54 \,/\, 4 = -13−54/4=−13 and −54 % 4=−2-54 \,\%\, 4 = -2−54%4=−2 , but q=−14q = -14q=−14 , r=2r = 2r=2 .

85. [Direct Proof IV: Quotient-Remainder] nnn is an integer and ddd a positive integer. Which values can n mod dn \bmod dnmodd take, and when is n mod d=0n \bmod d = 0nmodd=0 ?

    0,1,…,d−10, 1, \dots, d - 10,1,…,d−1 ; and n mod d=0n \bmod d = 0nmodd=0 exactly when d∣nd \mid nd∣n . Example: n mod 3∈{0,1,2}n \bmod 3 \in \{0, 1, 2\}nmod3∈{0,1,2} , and 12 mod 3=012 \bmod 3 = 012mod3=0 because 3∣123 \mid 123∣12 .

86. [Direct Proof IV: Quotient-Remainder] How do you compute n mod dn \bmod dnmodd from ndiv⁡dn \operatorname{div} dndivd ?

    n mod d=n−d⋅(ndiv⁡d)\boldsymbol{n \bmod d = n - d \cdot (n \operatorname{div} d)}nmodd=n−d⋅(ndivd) From n=dq+rn = dq + rn=dq+r . On a calculator, ndiv⁡dn \operatorname{div} dndivd (for n≥0n \ge 0n≥0 ) is n/dn / dn/d with the digits after the decimal point dropped.Example: 32/9=3.555…32 / 9 = 3.555\ldots32/9=3.555… , so 32div⁡9=332 \operatorname{div} 9 = 332div9=3 and 32 mod 9=32−27=532 \bmod 9 = 32 - 27 = 532mod9=32−27=5 .

87. [Direct Proof IV: Quotient-Remainder] Today is Tuesday, and neither this year nor next year is a leap year. What day of the week is it one year from today?

    Wednesday. 365=52⋅7+1365 = 52 \cdot 7 + 1365=52⋅7+1 : 364 days from today is a Tuesday, and one day later is Wednesday.In general, with Sunday =0= 0=0 , Monday =1= 1=1 , …, Saturday =6= 6=6 : the day NNN days after day TTT is (T+N) mod 7(T + N) \bmod 7(T+N)mod7 .

88. [Direct Proof IV: Quotient-Remainder] mmm is an integer with m mod 11=6m \bmod 11 = 6mmod11=6 . What is 4m mod 114m \bmod 114mmod11 ?

    2\boldsymbol{2}2 m=11q+6m = 11q + 6m=11q+6 , so 4m=44q+24=11(4q+2)+24m = 44q + 24 = 11(4q + 2) + 24m=44q+24=11(4q+2)+2 , and 0≤2<110 \le 2 < 110≤2<11 .

89. [Direct Proof IV: Quotient-Remainder] What is the parity property of integers?

    Every integer is either even or odd, and not both. Quotient-remainder theorem with d=2d = 2d=2 : n=2q+rn = 2q + rn=2q+r with r∈{0,1}r \in \{0, 1\}r∈{0,1} , so n=2qn = 2qn=2q or n=2q+1n = 2q + 1n=2q+1 . Uniqueness of qqq and rrr rules out both.Example: −7=2⋅(−4)+1-7 = 2 \cdot (-4) + 1−7=2⋅(−4)+1 is odd.

90. [Direct Proof IV: Quotient-Remainder] Whether an integer is even or odd is called its parity.

    Example: 5 has odd parity and 28 has even parity.

91. [Direct Proof IV: Quotient-Remainder] Theorem 4.4.2 What can you say about the parity of two consecutive integers?

    They have opposite parity: one is even and the other is odd. Two integers are consecutive if one is one more than the other.Example: 12 and 13; 1,073 and 1,074.

92. [Direct Proof IV: Quotient-Remainder] How do you prove that of two consecutive integers mmm and m+1m + 1m+1 , one is even and the other odd?

    Case 1: mmm is even m=2km = 2km=2k , so m+1=2k+1m + 1 = 2k + 1m+1=2k+1 is odd. Example: m=4m = 4m=4 , m+1=5m + 1 = 5m+1=5 . Case 2: mmm is odd m=2k+1m = 2k + 1m=2k+1 , so m+1=2k+2=2(k+1)m + 1 = 2k + 2 = 2(k + 1)m+1=2k+2=2(k+1) is even. Example: m=7m = 7m=7 , m+1=8=2⋅4m + 1 = 8 = 2 \cdot 4m+1=8=2⋅4 . By the parity property, mmm is even or odd, so the two cases cover every integer.

93. [Direct Proof IV: Quotient-Remainder] What is the method of proof by division into cases?

    To prove "If A1A_1A1​ or A2A_2A2​ or … or AnA_nAn​ , then CCC ", prove "If A1A_1A1​ , then CCC ", "If A2A_2A2​ , then CCC ", …, "If AnA_nAn​ , then CCC ". Then CCC holds whichever of A1,…,AnA_1, \dots, A_nA1​,…,An​ is true.Example: " mmm is even or mmm is odd", so proving a statement for even mmm and for odd mmm proves it for every integer mmm .

94. [Direct Proof IV: Quotient-Remainder] Why can every integer nnn be written as 4q4q4q , 4q+14q + 14q+1 , 4q+24q + 24q+2 or 4q+34q + 34q+3 for some integer qqq ?

    Quotient-remainder theorem with d=4d = 4d=4 : n=4q+rn = 4q + rn=4q+r with 0≤r<40 \le r < 40≤r<4 , so r∈{0,1,2,3}r \in \{0, 1, 2, 3\}r∈{0,1,2,3} . In general, every integer has one of the forms dq, dq+1, …, dq+(d−1)dq, \ dq + 1, \ \dots, \ dq + (d - 1)dq, dq+1, …, dq+(d−1) .Example: −5=4⋅(−2)+3-5 = 4 \cdot (-2) + 3−5=4⋅(−2)+3 .

95. [Direct Proof IV: Quotient-Remainder] Theorem 4.4.3 What form does the square of every odd integer have?

    8m+1\boldsymbol{8m + 1}8m+1 for some integer mmm , i.e. n2 mod 8=1n^2 \bmod 8 = 1n2mod8=1 for odd nnn . Example: 32=9=8⋅1+13^2 = 9 = 8 \cdot 1 + 132=9=8⋅1+1 , 52=25=8⋅3+1\ 5^2 = 25 = 8 \cdot 3 + 1 52=25=8⋅3+1 , 72=49=8⋅6+1\ 7^2 = 49 = 8 \cdot 6 + 1 72=49=8⋅6+1 .

96. [Direct Proof IV: Quotient-Remainder] How does the proof by cases show that the square of every odd integer nnn has the form 8m+18m + 18m+1 ?

    Case 1: n=4q+1n = 4q + 1n=4q+1 n2=16q2+8q+1=8(2q2+q)+1n^2 = 16q^2 + 8q + 1 = 8(2q^2 + q) + 1n2=16q2+8q+1=8(2q2+q)+1 Example: n=5n = 5n=5 ( q=1q = 1q=1 ): 25=8⋅3+125 = 8 \cdot 3 + 125=8⋅3+1 . Case 2: n=4q+3n = 4q + 3n=4q+3 n2=16q2+24q+9=8(2q2+3q+1)+1n^2 = 16q^2 + 24q + 9 = 8(2q^2 + 3q + 1) + 1n2=16q2+24q+9=8(2q2+3q+1)+1 Example: n=7n = 7n=7 ( q=1q = 1q=1 ): 49=8⋅6+149 = 8 \cdot 6 + 149=8⋅6+1 . The two cases cover every odd nnn : by the quotient-remainder theorem with d=4d = 4d=4 , nnn is 4q4q4q…

97. [Direct Proof IV: Quotient-Remainder] Claim: the square of every odd integer nnn has the form 8m+18m + 18m+1 for some integer mmm .Writing n=2q+1n = 2q + 1n=2q+1 gives n2=4(q2+q)+1n^2 = 4(q^2 + q) + 1n2=4(q2+q)+1 . Why does this already prove the claim?

    q2+q=q(q+1)q^2 + q = q(q + 1)q2+q=q(q+1) is a product of two consecutive integers, so it is even, and 4⋅2j+1=8j+14 \cdot 2j + 1 = 8j + 14⋅2j+1=8j+1 . One of qqq and q+1q + 1q+1 is even.Example: n=7n = 7n=7 , q=3q = 3q=3 : q(q+1)=12q(q + 1) = 12q(q+1)=12 , and 49=4⋅12+1=8⋅6+149 = 4 \cdot 12 + 1 = 8 \cdot 6 + 149=4⋅12+1=8⋅6+1 .

98. [Direct Proof IV: Quotient-Remainder] What is the absolute value ∣x∣|x|∣x∣ of a real number xxx ?

    ∣x∣=x\boldsymbol{|x| = x}∣x∣=x if x≥0x \ge 0x≥0 , and ∣x∣=−x\boldsymbol{|x| = -x}∣x∣=−x if x<0x < 0x<0 . Example: ∣3∣=3|3| = 3∣3∣=3 and ∣−3∣=−(−3)=3|-3| = -(-3) = 3∣−3∣=−(−3)=3 .

99. [Direct Proof IV: Quotient-Remainder] A lemma is a statement that does not have much interest of its own but helps to derive other results.

100. [Direct Proof IV: Quotient-Remainder] Lemma 4.4.4 For every real number rrr , how does rrr compare with ∣r∣|r|∣r∣ and −∣r∣-|r|−∣r∣ ?

     −∣r∣≤r≤∣r∣\boldsymbol{-|r| \le r \le |r|}−∣r∣≤r≤∣r∣ Proof by cases: if r≥0r \ge 0r≥0 , then r=∣r∣r = |r|r=∣r∣ and −∣r∣≤0≤r-|r| \le 0 \le r−∣r∣≤0≤r ; if r<0r < 0r<0 , then r=−∣r∣r = -|r|r=−∣r∣ and r<0<∣r∣r < 0 < |r|r<0<∣r∣ .Example: r=−2r = -2r=−2 : −2≤−2≤2-2 \le -2 \le 2−2≤−2≤2 .