Math 135 - Important Terms

Important Terms for the course Math 135 at the University of Waterloo

Chapter 1 §

1. Sets - Set Notation
2. Statement - a sentence that has the definite state of being true or false
   1. 2 + 3 = 6 (false statement) | + 2 5 (true statement)
   2. Does 7 = 5? (not a mathematical statement because you cannot assign true or false to it)
3. Natural Numbers denoted by
4. Set of integers where negative, positive, or zero are denoted by
5. Set of rational numbers denoted by contains all the numbers of the form where a is an integer and b is a non-zero integer
6. Set of real numbers denoted by contains all the numbers in decimal form
7. Negation - Finding the inverse meaning of a statement
   1. Suppose A is a true statement, A would be false
      1. ( A) = A
8. Quantified Statements contains 4 parts:
   1. A quantifier
   2. A variable (any symbol representing a quantity or mathematical object)
   3. a domain (any set)
   4. an open sentence involving the variable
9. Open Sentence - A sentence that contains a variable, where the truth of the sentence is determined by the value of the variable chosen from the domain of the variable
10. Quantifiers - Describe “how many” elements of the domain are claimed to make the open sentence true
11. - Universal Quantifier
12. - Existential Quantifier
13. Universally Quantified Statement - x S, P(x)
    1. This statement is read as “For all x in S, P(x) is true”
14. Existentially Quantified Statement - x S, P(x)
    1. This statement is read as “There exists at least one value of x in S for which P(x) is true”
15. Nested Quantifiers - Quantifiers in a statement containing more than one quantifier
16. s , t , t > s
    1. For all real numbers s, there exists a real number t such that t > s
17. x X, y Y, z Z, R(x,y,z)
    1. Can be rewritten as:
       1. x X, P(x), where P(x) is y Y, Q(x, y), where Q(x, y) is z Z, R(x, y, z)

Chapter 2 §

1. Negation is denoted by or the keyword “not” (Eg: A / not A)
2. Compound Statement is a statement composed of several individual statements, each of which is called a Component Statement
3. A B translates to A and B. This is similar to and statement in programming. Both A and B have to be true for A B to be true
4. A B translates to A or B. This is similar to or statement in programming. Either A OR B have to be true for A B to be true
5. Brackets are important, they specify the order of operation
6. De Morgan's Law (DML)
   1. (A B) ( A) ( B)
   2. (A B) ( A) ( B)
7. Commutative Laws:
   1. A B B A
   2. A B B A
8. Associative Laws:
   1. A (B C) (A B) C
   2. A (B C) (A B) C
9. Distributive Laws:
   1. A (B C) (A B) (A C)
   2. A (B C) (A B) (A C)
10. Implication:
    1. Format: A B
       1. Only false when A is true and B is false
       2. All other times true
11. Implication B A is called the converse of A B
12. Implication (B) (A) is called the contrapositive of A B
13. If and only if (iff) is represented by A B
    1. Only true when both A and B are same truth value (both have to be true or false)
    2. (A B) ((A B) (B A))

Chapter 3 §

• We prove a statement when we demonstrate its true and the argument to do is called a proof
  • You can prove an inequality by proving all of it’s constraints (eg: x 1 and x 3)
• We disprove a statement when we demonstrate it’s false
  • To disprove a universally quantified statement find a counter-example. For example if the statement is true for all domains find a value for which it isn’t
  • To disprove x S, P(x) prove it’s negation x S, P(x)
• When proving an identity we do NOT start by assuming the truth of that identity
• Be on the look out for extraneous solutions (solutions not in the domain created by acts such as rearranging the equation)
• k , x , x + 2kx + k = 0 x , k , x + 2kx + k = 0
  • Changing the order of nested quantifiers can change the truth value of a quantified statement
• To prove the implication x S, P(x) Q(x)
  • Assume x is an arbitrary element
  • Assume P(x) is true
  • Use that assumption to show Q(x) is true
• We assume an integer is even if it can be written as 2k (k = an integer). Otherwise an integer is written in the form 2k + 1 where we say the integer is odd
• 3 6 exists since 6 = 3 * 2, exists an integer k such that 6 = 3k
• -3 6 exists since 6 = (-3) * (-2), exists an integer k such that 6 = -3k
• 5 6 since no integer k exists so that 6 = k * 5
• For all integers a, a 0 0 = 0 * a
• For all non-zero integers a, a 0 since no integer k so that k * 0 = a
• For all integers b, 1 b since b can be written as b = b * 1 and -1 b since b can be written b = (-b) * (-1)
• Transfer of Divisibility (TD) - For all integers a, b, and c, if a b and b c, then a c
• Proposition 8: For all integers if a, b and c, if a b or a c, then a bc
  • If a b, then a bc
    • Assume a b, there exists an integer k so that b = ka. Substitute for b in product bc, we get
    • bc = (ka)c = kac = (kc)a
    • kc is an integer we can conclude a bc
  • If a c, then a bc
    • Exists integer m so that c = ma. Substituting this equation we get
    • bc = b(ma) = bma = (bm)a
    • bm is an integer we conclude a bc
  • These proofs can be re-written as if a c, then a bc is similar, and is omitted
• Divisibility of Integer Combinations (DIC) - For all integers a, b and c, if a b and a c, then for all integers x and y, a (bx + cy)
• To prove an implication using contrapositive (A B) replace it with it’s contrapositive (B) (A)
• Anytime we come across an argument claiming A and A are true we say there must be a contradiction in the argument
• (A B C) ((A C) (B C))
• Proof by Contradiction -

Chapter 4 §

• Properties of Summation (PS)
  1. Multiplying by a constant
     • = c (where c is constant)
  2. Adding two sums and subtracting two sums
     • + =
     • - =
  3. Change the bounds of the index of summation
  4. Breaking a sum apart
     • = +
• Product Notation
  • = xx xx
• Axiom is a statement that is assumed to be true. No proof given
• Axiom 1 - Principle of Mathematical Induction (POMI)
  • Let P(n) be an open sentence depends on n
    • If statements 1 and 2 are both true:
      • P(1)
      • For all k , if P(k), then P(k + 1)
    • then statement 3 is true:
      • For all n , P(n)
• Axiom 2 - Principle of Strong Induction (POSI)
  • Let P(n) be an open sentence that depends on n
  • If statements 1 and 2 are both true
    1. P(1)
    2. For all k , if P(1) P(2) P(k) then P(k + 1)
  • then statement 3 is true: 3. For all n , P(n)
• If you can prove the inductive conclusion P(k + 1) by assuming only P(k) then use POMI but if you need to assume P(i) for one or more i with i < k, then use POSI

Chapter 5 §

• Number of elements in a finite set is called cardinality denoted by | S |
• Universe of Discourse - contains all the objects we might encounter in a given situation
• {x : P(x)}
  • x is an element of
  • P(x) is true
• {f(x) : x }
  • containing all objects of the form f(x) such that x is an element of
• {f(x) : x , P(x)} or {f(x) : P(x), x }
  • x is an element of
  • P(x) is true
• Union of two sets S and T written S T is the set of all elements belonging to either set S or set T(or both)
  • S T = {x: x S OR x T} = {x: (x S) (x T)}
• The intersection of two sets S and T, written S T is the set of all elements belonging to both set S and set T
  • S T = {x: x S AND x T} = {x: (x S) (x T)}
• Set difference of two sets S and T is written as S - T (or S \ T) is the set of all elements belonging to S but not T
  • S - T = {x : x S AND x T} = {x : (x S) (x T)} = {x : (x S) ((x T))}
• Complement of set S, written is set of all elements not in S
  • = {x : x S}
• = -
  • = -
• Two sets are said to be disjoint when S T =
• A set S is called a subset of set T, written symbolically as S T, when every element of S belongs to T
• A set S is called a proper subset of a set T, written symbolically as S T, when S is a subset of T and there exists an element in T which does not belong in S
• When S is not a subset of T, we can write it as S T
• When we have S T we also say T is a superset of S
• When we have S T we also say T is a proper subset of S

Chapter 6 §

• Bounds By Divisibilty (BBD) - For all integers a and b, if b a and a 0 then b a
• Division Algorithm (DA) - a = qb + r, 0 r < b
• Common Divisor - a, b, c if c a and c b then integer c is a common divisor
• Let a and b be integers
  • If a and b are both zero, an integer d > 0 is the greatest common divisor of a and b, written d = gcd(a, b), when
    • d is a common divisor of a and b, and
    • for all integers c, if c is a common divisor of a and b, then c d
  • If a and b are both zero, we define gcd(a, b) = gcd(0, 0) = 0
• Let a be an arbitrary integer
  • We have gcd(a, a) = gcd(a, -a) = a
  • We have gcd(a, 1) = gcd(a, -1) = 1
  • We have gcd(a, 0) = a
• GCD With Remainder (GCD WR) - For all integers a, b, q and r, if a = qb + r, then gcd(a, b) = gcd(b, r)
• GCD Characterization Theorem (GCD CT)
  • For all integers a and b, and non-negative integers d, if
    • d is a common divisor of a and b, and
    • there exist integers s and t such that as + bt = d
  • then d = gcd(a, b)
• Bezout's Lemma (BL) - For all integers a and b, there exist integers s and t such that as + bt = d, where d = gcd(a, b)
• Floor - Floor of a real number x is written as , is the largest integer less than or equal to x
• Extended Euclidean Algorithm (EEA)
  • Input: Integers a, b with
  • Initialize: Construct a table with four columns so that
    • the columns are labelled x, y, r and q
    • the first row in the table is (1, 0, a, 0)
    • the second row in the table is (0, 1, b, 0)
  • Repeat: For i 3
    • Row Row - qRow
  • Stop: When r = 0
  • Output: Set n = i - 1. Then gcd(a, b) = r, and s = x and t = y are a certificate of correctness
• Common Divisor Divides GCD (CDD GCD) - For all integers a, b, and c, if c a and c b then c gcd(a, b)
• Coprime - If gcd(a, b) = 1 then two integers a and b are coprime
• Coprimeness Characterization Theorem (CCT) - For all integers a and b, gcd(a, b) = 1 if and only if there exist integer s and t such that as + bt = 1
• Division by GCD (DB GCD) - For all integers a and b, not both zero, gcd() = 1, where d = gcd(a, b)
• Coprimeness and Divisibility (CAD) - For all integers a, b and c, if c ab and gcd(a, c) = 1, then c b
• Prime/Prime Number - A natural number p > 1 where p’s only positive divisors are 1 and p itself. Otherwise p is called composite
• Prime Factorization (PF) - Every natural number n > 1 can be written as a product of primes
• Euclid's Theorem - The number of primes is infinite
• Euclid's Lemma (EL) - For all integers a and b, and prime numbers p, if p ab, then p a or p b
• Unique Factorization Theorem (UFT) - Every natural number n > 1 can be written as a product of prime factors uniquely, apart from the order factors
• Finding a Prime Factor (FPF) - Every natural number n > 1 is either prime or has a prime factor less than or equal to
• Divisors From Prime Factorization (DFPF)
  • Let n and c be positive integers
  • let n = p p p
  • The integer c is a positive divisor of n if and only if c can be represented as a product
  • c = , where for i = 1, 2, , k
• GCD From Prime Factorization (GCD PF)
  • Let a and be positive integers, and let
  • a =
  • b =
  • gcd(a, b) = p where = min {} for i = 1, 2, , k

Chapter 7 §

• Diophantine Equation - Both coefficients and variables are integers, this equation is called linear if each term in the equation is a constant or a constant times a single variable
• Linear Diophantine Equation Theorem, Part 1, (LDET 1)
  • For all integers a, b, and c, with a and b both non zero, the linear Diophantine Equation
    • ax + by = c
  • (in variables x and y) has an integer solution if and only if d c, where d = gcd(a, b)
• Linear Diophantine Equation Theorem, Part 2, (LDET 2)
  • Let a, b and c be integers with a and b both non zero, and define d = gcd(a, b). If x = x and y = y is one particular integer solution to the linear Diophantine Equation ax + by = c, then the set of all solutions is given by
  • {(x, y): x = }

Chapter 8 §

Note

Let m be a fixed positive integer. For integers a and b, we say that a is congruent to b modulo m, and write

(mod m) > when . For integers a and b such that , we write (mod m). We refer to as congruence, and m as its modulus

• Reflexivity: For all integers a, a = a
• Symmetry: For all integers a and b, if a = b, then b = a
• Transitivity: For all integers a, b and c, if a = b and b = c, then a = c

[!Congruence is an Equivalence Relation (CER)]

For all integers a, b and c we have

1. (mod m)
2. If (mod m), then (mod m)
3. If (mod m) and (mod m), then (mod m)

• For all integers and if (mod m) and (mod m), then
  • (mod m)
  • (mod m)
  • (mod m)

[!Congruence Add and Multiply (CAM)]

For all positive integers n, for all integers and if (mod m) for all then

1. (mod m)
2. (mod m)

[!Congruence Power (CP)]

For all positive integers n and integers a and b if (mod m), then (mod m)

[!Congruence Divide (CD)]

For all integers a, b and c, if (mod m) and gcd(c, m) = 1, then (mod m)

[!Congruent Iff Same Reminder (CISR)]

For all integers a and b, (mod m) if and only if a and b have the same remainder when divided by m

[!Congruent To Remainder (CTR)]

For all integers a and b with (mod m) if and only if a has remainder b when divided by m

• For all non-negative integers a, a is divisible by 3 if and only if the sum of the digits of a is divisible by 3
• For all non-negative integers a, a is divisible by 11 if and only if is divisible by 11
  • is the sum of the digits of even powers (of 10) in digits of a
  • is the sum of digits of odd powers (of 10) in digits of a

[!Congruence Class]

m different congruent classes modulo m, since there are m choices 0, 1, , m - 1 of remainder when dividing by m

In modular arithmetic, following properties hold for all [a] :

[!Modular Arithmetic Theorem (MAT)]

For all integers a and c, with a non-zero, the equation

in has a solution if and only if where d = gcd(a, m). When there are d solutions given by

Where is one particular solution

[!Fermat’s Little Theorem (FLT)]

For all prime numbers p and integers a not divisible by p, we have

(mod )

[!flt variation]

For all prime numbers p and integers a, we have (mod )

[!Chinese Remainder Theorem]

For all integers and and positive integers and , if gcd() = 1, then the simultaneous linear congruences

• (mod )
• (mod )

have a unique solution modulo . Thus if is one particular solution, then the solutions are given by the set of all integers n such that

(mod )