Chapter 4 Quiz (4.1-4.5 + Modular Arithmetic)

Even Integer

An integer is even if it equals 2 times some integer; that is, n = 2k for some integer k.

Odd Integer

An integer is odd if it equals 2 times some integer plus 1; that is, n = 2k + 1 for some integer k.

Prime Number

An integer greater than 1 that has no positive divisors other than 1 and itself.

Composite Number

An integer greater than 1 that is not prime.

Rational Number

A number that can be written as a fraction a/b where a and b are integers and b ≠ 0.

Divides (| symbol)

An integer a divides b (written a | b) if b = ak for some integer k.

Counterexample

A specific example that shows a general statement is false.

Direct Proof

A proof method that starts from known facts and uses logical steps to reach a conclusion.

Quotient-Remainder Theorem

For any integer n and positive integer d, there exist unique integers q and r such that n = dq + r and 0 ≤ r < d.

mod

n mod d is the remainder when n is divided by d.

div

n div d is the integer part of n divided by d; that is, the quotient without the remainder.

Congruence (mod)

a ≡ b (mod d) means a and b have the same remainder when divided by d, or d divides (a - b).

Modular Addition

(a + b) mod d = ((a mod d) + (b mod d)) mod d.

Modular Multiplication

(a * b) mod d = ((a mod d) * (b mod d)) mod d.

Modular Exponentiation

a^k mod d means the remainder when a raised to the power k is divided by d. Use repeated squaring for fast computation.

Parity

The property of being even or odd.