Chapter 4 Quiz (4.1-4.5 + Modular Arithmetic)

Covers: Sections 4.1–4.5 + Modular Arithmetic
Focus: Direct Proofs, Counterexamples, Rational Numbers, Divisibility, Quotient-Remainder Theorem, Modular Arithmetic

Section 4.1: Direct Proof and Counterexample I - Introduction

Definitions

• Even Integer: An integer n is even if n = 2k for some integer k.

• Odd Integer: An integer n is odd if n = 2k + 1 for some integer k.

• Prime Number: A number > 1 that has no divisors other than 1 and itself.

• Composite Number: A number > 1 that is not prime.

Key Ideas

• To prove a statement: Show it logically follows from known facts.

• To disprove a statement: Provide a counterexample (a specific case where it's false).

Example (Proof by Definition)

Prove: 10a + 8b + 1 is odd for all integers a and b.

• 10a + 8b = 2(5a + 4b), which is even

• Then: 10a + 8b + 1 = even + 1 = odd

Section 4.2: Writing Proofs

Proof Structure

1. State what is given and what to prove.

2. Use definitions and logical steps.

3. Conclude with a justification (QED).

Tips

• Avoid arguing from examples.

• Always define variables and explain steps.

• Avoid assuming what you're trying to prove.

Common Mistake:

Incorrect: "m and n are even, so m + n is even." Correct: "m = 2r, n = 2s; m + n = 2(r + s)"

Section 4.3: Rational Numbers

Definition

• A rational number is any number that can be written as a ratio a/b where a and b are integers, b ≠ 0.

Key Theorems

• The sum, difference, and product of rational numbers are rational.

• Repeating decimals are rational.

Example:

Prove: The sum of two rational numbers is rational.

• Let r = a/b, s = c/d

• r + s = (ad + bc)/bd (still a ratio of integers with non-zero denominator)

Section 4.4: Divisibility

Definitions

• a | b means "a divides b", or b = ak for some integer k

• A number divides 0: a | 0 is always true if a ≠ 0

Key Theorems

• Transitivity: If a | b and b | c, then a | c

• Every integer > 1 is divisible by a prime

Prime Factorization

• Every integer > 1 can be uniquely factored into primes

Example:

Prove: If a | b and b | c, then a | c

• b = ak, c = bm → c = a(km)

Section 4.5: Division into Cases + Quotient-Remainder Theorem

Quotient-Remainder Theorem

Given any integer n and positive integer d, there are unique integers q and r such that:

• n = dq + r where 0 ≤ r < d

div and mod

• n div d = q, n mod d = r

• n = d * (n div d) + (n mod d)

Common Use: Prove patterns

Example: Any integer is one of: 4q, 4q+1, 4q+2, 4q+3

Parity Example:

Prove: Consecutive integers have opposite parity.

• Case 1: m = 2k (even) → m + 1 = 2k + 1 (odd)

• Case 2: m = 2k + 1 (odd) → m + 1 = 2k + 2 = 2(k + 1) (even)

Modular Arithmetic

Definition

a ≡ b (mod d) means a mod d = b mod d OR d | (a - b)

Modular Rules

1. Addition: (a + b) mod d = [(a mod d) + (b mod d)] mod d

2. Multiplication: (a × b) mod d = [(a mod d) × (b mod d)] mod d

3. Exponentiation: a^k mod d can be computed by repeated squaring

Example:

Compute: (7 × 8) mod 3

• 7 mod 3 = 1, 8 mod 3 = 2

• (1 × 2) mod 3 = 2

Quick Checks

• a mod 10 is the last digit of a

• If m mod 11 = 6, then 4m mod 11 = 2