proofs3

In this lecture: 

In this lecture Number Theory ● Quotient and Remainder ● Floor and Ceiling Proofs ● Direct proofs and Counterexamples (cont.) ● Division into cases

Quotient-Remainder Theorem: 

Quotient-Remainder Theorem Theorem: For  nZ and dZ+ ! q,rZ such that n=d·q+r and 0≤r<d. q is called quotient; r is called remainder. Notation: q = n div d; r = n mod d. Examples: 1) 53 = 8·6+5. Hence 53 div 8 = 6; 53 mod 8 = 5. 2) -29 = 7·(-5)+6. Hence -29 div 7 = -5; -29 mod 7 = 6.

Example of using div and mod: 

Example of using div and mod Last year Halloween was on Tuesday. Q.: What day is Halloween this year? Solution: There are 365 days between 10/31/06 and 10/31/07. 365 mod 7 = 1. Thus, if 10/31/06 is Tuesday then 10/31/07 is Wednesday.

Proof Technique: Division into Cases: 

Proof Technique: Division into Cases Suppose at some stage of a proof ● we know that A1 or A2 or A3 or … or An is true; ● want to deduce a conclusion C. Use division into cases: Show A1→C, A2→C, …, An→C. Conclude that C is true.

Division into Cases: Example: 

Division into Cases: Example Proposition: If nZ s.t. neither of 2 or 3 divide n, (1) then n2 mod 12 = 1. (2) Proof: Suppose nZ s.t. neither of 2 or 3 divide n. By quotient-remainder theorem, exactly one of the following is true: a) n=6k, b) n=6k+1, c) n=6k+2, d) n=6k+3, e) n=6k+4, f) n=6k+5 for some integer k. (3) n can’t be 6k, 6k+2 or 6k+4 because in that case 2 | n (which contradicts (1) ). (4) n can’t be 6k+3 because in that case 3 | n (which contradicts (1) ). (5)

Division into Cases: Example(cont.): 

Division into Cases: Example(cont.) Proof(cont.): Based on (3), (4) and (5), either n=6k+1 or n=6k+5. Let’s show (2) for each of these two cases. Case 1: Suppose n=6k+1. Then n2 = (6k+1)2=36k2+12k+1 (by basic algebra) = 12(3k2+k)+1 (6) Let p=3k2+k. Then p is an integer. n2 = 12p+1 . ( by substitution in (6) ) Hence n2 mod 12 = 1 by quotient-remainder th-m. Case 2: Suppose n=6k+5. (exercise) ■

Floor and Ceiling: 

Floor and Ceiling Definition: For any real number x, ● the floor of x: = the unique integer n s.t. n ≤ x < n+1; ● the ceiling of x: = the unique integer n s.t. n-1 < x ≤ n. Examples:

Properties of Floor and Ceiling: 

Properties of Floor and Ceiling For  xR and mZ , . is false. Counterexample: For x=1.7, y=2.8, Note: If x,y>0 and the sum of their fractional parts is <1 then

Properties of Floor and Ceiling: 

Properties of Floor and Ceiling Theorem: For  nZ , Proof: Case 1: Suppose n is odd. Then n=2k+1 for some integer k. (1)

Properties of Floor and Ceiling: 

Properties of Floor and Ceiling Proof (cont.): By substitution from (1), (2) because kZ and k ≤ k+1/2 < k+1. On the other hand, n=2k+1 → k=(n-1)/2. (by basic algebra) (3) Based on (2) and (3), Case 2: n is even (left as exercise). ■