Preface

Something worth taking notes from Discrete Mathematics with Applications, 4th edition, Susanna S. Epp

This is my reading notes of Chapter 4: Elementary Number Theory and Methods of Proof

4.1 Direct Proof and Counterexample I: Introduction

• prime number/composite number:

  An integer $n$ is prime if, and only if, $n>1$ and for all positive integers $r$ and $s$, if $n = rs$, then either $r$ or $s$ equals $n$

• proving existential statements

  constructive proofs of existence 构造?

• disproving universal statements

  counterexample 反例

• proving universal statements

  the method of exhaustion 穷举法

  Method of Generalizing from the Genetic Particular: a particular but arbitrarily chosen $x$ from the set

  generic: “sharing all the common characteristics of a group or class”

4.2 Direct Proof and Counterexample II: Rational Numbers

4.3 Direct Proof and Counterexample III: Divisibility

• the notion of divisibility

  $d \mid n$ is read “$d$ divides $n$”. We can also say: $d$ is a factor/divisor of $n$; $n$ is divisible by $d$

• Theorem 4.3.4: divisibility by a Prime

  Any integer $n>1$ is divisible by a prime number

  Proof omitted here

• Theorem 4.3.5: The Unique Factorization of Integers Theorem

  also called the fundamental theorem of arithmetic (算术基本定理)

  Given any integers $n>1$ , there exist a positive integer $k$, distinct prime numbers $p_1, p_2, p_3…p_k$, and positive integers $e_1, e_2, e_3…e_k$ such that:

  $$n = {p_1}^{e_1}{p_2}^{e_2}{p_3}^{e_3}...{p_k}^{e_k}$$

• Exercise 47/48

  To prove that for any nonnegative integer $n$, if the the sum of the digits of $n$ is divisible by $9$ (or $3$), then $n$ is divisible by $9$ (or $3$)

  
  

  A very simple proof:

  $$\begin{equation} \begin{aligned} & n = a_k \cdot 10^k ...+a_1 \cdot 10^1 +a_0 \cdot 10^0 \\ & = a_k \cdot (999...9 +1)+ ...+a_1 \cdot (9+1) +a_0 \cdot 1 \\ & = 9 \cdot (a_k \cdot 111...1 +...+a_1 \cdot 1) +(a_k+...+a_1+a_0) \end{aligned} \end{equation}$$

• Exercise 49

  To prove that for any nonnegative integer $n$, if the the alternating sum of the digits of $n$ is divisible by $11$, then $n$ is divisible by $11$

  the alternating sum of $19260817$ is $7-1+8-0+6-2+9-1$

  
  

  A very simple proof:

  At first we need a lemma:

  • If $n = 10^k +1$ and $k$ is odd, then $11 \mid n$

  • If $n = 10^k-1$ and $k$ is even, then $11 \mid n$

    we can derive this by Mathematical Induction (数学归纳法)

    (I have not come out a strict direct proof other than it. If you have a brilliant idea, hope you can tell me :D)

  Break the proof into two cases: the total number of digits is even or odd

  • Case 1: even

    $$\begin{equation} \begin{aligned} & n = a_k \cdot 10^k + a_{k-1} \cdot 10^{k-1}+...+a_1 \cdot 10^1 +a_0 \cdot 10^0 \\ & = a_k \cdot (10^{k+1} +1)+ a_{k-1} \cdot (10^{k-1}-1)+...+a_1 \cdot (10^1+1) +a_0 \cdot(10^0-1) + \text{altenating sum}\\ \end{aligned} \end{equation}$$

    From our lemma we can deduce the conclusion

  • Case 2: odd

    Similar to Case 1(I told you it’s a very simple proof)

4.4 Direct Proof and Counterexample IV: Division into Cases and the Quotient -Remainder Theorem

• Theorem 4.4.1 The Quotient -Remainder Theorem

  Given any integer $n$ and positive integer $d$, there exist unique integers $q$ and $r$ such that

  $$n = dq+r \ \text{and} \ 0 \leq r \leq d$$

• Parity property (sounds very profound but extremely simple)

  Any integer is either even or odd

• Example 4.4.7

  The square of any odd integer has the form $8m+1$ for some integer $m$

  The proof in the book is kind of interesting. Each integer is represent in the following forms:

  $$n = 4q \ \text{or} \ n=4q+1 \ \text{or} \ n=4q+2 \ \text{or} \ n=4q+3$$

  And it is easy to prove that.

• Theorem 4.4.6 Triangle Inequality

  For all real numbers $x$ and $y$, $|x+y| \leq |x|+|y|$

• Exercise 49&50

  $$m \mod d = n \mod d \Leftrightarrow (m-n) \mod d$$

• Exercise 51&52

  $d>0$

  $m \mod d = a$ and $n \mod d = b$ $\Rightarrow$ $(m+n) \mod d = (a+b) \mod d$

  $m \mod d = a$ and $n \mod d = b$ $\Rightarrow$ $(mn) \mod d = ab \mod d$

4.5 Direct Proof and Counterexample V: Floor and Ceiling

• Latex: $\left \lceil{x}\right \rceil $ $\left \lfloor{x}\right \rfloor $

• Theorem 4.5.1

  For all real numbers $x$ and all integers $m$, $\left \lfloor {x+m} \right \rfloor = \left \lfloor {x} \right \rfloor +m$

• Exercise 23

  To prove that for any real number $x$, if $x$ is not an integer, then $\left \lceil{x}\right \rceil+\left \lfloor{-x}\right \rfloor = -1$

  Answer:

  (1) $x-1<\left \lfloor{x}\right \rfloor \leq x$

  (2) $-x-1 < \left \lfloor{-x}\right \rfloor \leq -x$

  Add (1) (2): $-2 < \left \lceil{x}\right \rceil+\left \lfloor{-x}\right \rfloor \leq 0$

  $x$ is not an integer but $\left \lceil{x}\right \rceil+\left \lfloor{-x}\right \rfloor$ must be an integer

• Exercise 25

  To prove that for all real numbers, $\left \lfloor {\left \lfloor {x/2} \right \rfloor/2} \right \rfloor = \left \lfloor {x/4} \right \rfloor$

  Answer:

  (1) ${\left \lfloor {x/2} \right \rfloor/2}-1<\left \lfloor {\left \lfloor {x/2} \right \rfloor/2} \right \rfloor \leq {\left \lfloor {x/2} \right \rfloor/2}$

  (2) $\left \lfloor {x/2} \right \rfloor /2 \leq x/4$

  substitude (2) into (1)

4.6 Indirect Argument: Contradiction and Contraposition

• Proof by contradiction

  suppose the negation of the argument is true, then show that this supposition (猜想) leads to a contradiction

• Proof by contraposition

  To prove the contrapositive of the statement is true

• Exercise:

  Prove that any integer greater than $11$ is the sum of two composite number:

  Solution:

  $n$ is even: $n = 2(k-4) + 8, k >= 6$

  $n$ is odd: $n = 2(k-4) +9, k>=6$

4.7 Indirect Argument: Two Classical Theorems

• The irrationality of $\sqrt{2}$

  make use of another theorem: If the square if the integer is even, then the integer is even

• The infinity of prime numbers

  Proposition 4.7.3:

  For any integer $a$ and any prime number $p$, if $p \mid a$, then $p \nmid {a+1}$

  thus let $N$ be the product of all prime numbers plus 1

• Exercise:

  Prove that if $n>2$, there exists a prime number in the range $(n,n!)$

  Solution:

  1. Any integer greater than 1 can be divided by a prime number
  2. For all integers $x \in [2,n]$, $x \mid n!$. We can deduce that all prime numbers $p \in [2,n]$, $p\mid n$
  3. We have the proposition 4.7.3 that if any prime number $q \mid n!$, then $q \nmid n!-1$
  4. Thus either $n!-1$ is prime or there exists a prime larger than $n$
  5. what a beautiful proof

  Extension: https://en.wikipedia.org/wiki/Bertrand%27s_postulate