handout #12

CSE390D—Introduction to Discrete Math
Midterm Cheatsheet

Note: For proofs, you may use the theorems and definitions on this page. You do not have to cite which theorem you are using except for The Division Algorithm and The Fundamental Theorem of Arithmetic. You may not use other theorems from the book unless you prove them.

Ways to express the conditional statement p → q:

if p, then q p implies q
if p, q p only if q
p is sufficient for q a sufficient condition for q is p
q if p q whenever p
q when p q is necessary for p
a necessary condition for p is q             q follows from p
q unless ¬p  
Definition: The integer n is even if there exists an integer k such that n = 2k, and n is odd if there exists an integer k such that n = 2k + 1. (Note that an integer is either even or odd, and no integer is both even and odd.)

Definition: If a and b are integers with a ≠ 0, we say that a divides b if there is an integer c such that b = ac. When a divides b we say that a is a factor of b and that b is a multiple of a. The notation a | b denotes that a divides b.

Theorem: Let a, b, and c be integers. Then

  1. if a | b and a | c, then a | (b + c);
  2. if a | b, then a | bc for all integers c;
  3. if a | b and b | c, then a | c.
Theorem—The Division Algorithm: Let a be an integer and d a positive integer. Then there are unique integers q and r, with 0 ≤ r < d, such that a = dq + r.

Definition: In the equality given in the division algorithm, d is called the divisor, a is called the dividend, q is called the quotient, and r is called the remainder. This notation is used to express the quotient and remainder:

q = a div d,     r = a mod d.
Definition: If a and b are integers and m is a positive integer, then a is congruent to b modulo m if m divides a - b. We use the notation a ≡ b (mod m) to indicate that a is congruent to b modulo m.

Theorem: Let m be a positive integer. If a ≡ b (mod m) and c ≡ d (mod m), then:

a + c ≡ b + d (mod m)      and     ac ≡ bd (mod m)

Definition: A positive integer p greater than 1 is called prime if the only positive factors of p are 1 and p. A positive integer that is greater than 1 and is not prime is called composite.

Theorem—The Fundamental Theorem of Arithmetic: Every positive integer greater than 1 can be written uniquely as a prime or as a product of two or more primes where the prime factors are written in order of nondecreasing size.

Definition: Let a and b be integers, not both zero. The largest integer d such that d | a and d | b is called the greatest common divisor of a and b. The greatest common divisor of a and b is denoted by gcd(a, b).

Definition: The least common multiple of the positive integers a and b is the smallest positive integer that is divisible by both a and b. The least common multiple of a and b is denoted by lcm(a, b).

Stuart Reges
Last modified: Fri Oct 25 08:41:20 PDT 2024