D

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