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) | $\pi$ + 2 $\ge$ 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 $\mathbb{N}$
4. Set of integers where negative, positive, or zero are denoted by $\mathbb{Z}$
5. Set of rational numbers denoted by $\mathbb{Q}$ contains all the numbers of the form $\frac{a}{b}$ where a is an integer and b is a non-zero integer
6. Set of real numbers denoted by $\mathbb{R}$ contains all the numbers in decimal form
7. Negation - Finding the inverse meaning of a statement
   1. Suppose A is a true statement, $\neg$ A would be false
      1. $\neg$ ($\neg$ 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. $\forall$ - Universal Quantifier
12. $\exists$ - Existential Quantifier
13. Universally Quantified Statement - $\forall$ x $\in$ S, P(x)
    1. This statement is read as “For all x in S, P(x) is true”
14. Existentially Quantified Statement - $\exists$ x $\in$ 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. $\forall$ s $\in$ $\mathbb{R}$, $\exists$ t $\in$ $\mathbb{R}$, t > s
    1. For all real numbers s, there exists a real number t such that t > s
17. $\exists$ x $\in$ X, $\forall$ y $\in$ Y, $\exists$ z $\in$ Z, R(x,y,z)
    1. Can be rewritten as:
       1. $\exists$ x $\in$ X, P(x), where P(x) is $\forall$ y $\in$ Y, Q(x, y), where Q(x, y) is $\exists$ z $\in$ Z, R(x, y, z)

Chapter 2 §

1. Negation is denoted by $\neg$ or the keyword “not” (Eg: $\neg$A / not A)
2. Compound Statement is a statement composed of several individual statements, each of which is called a Component Statement
3. A $\wedge$ B translates to A and B. This is similar to and statement in programming. Both A and B have to be true for A $\wedge$ B to be true
4. A $\vee$ B translates to A or B. This is similar to or statement in programming. Either A OR B have to be true for A $\vee$ B to be true
5. Brackets are important, they specify the order of operation
6. De Morgan's Law (DML)
   1. $\neg$ (A $\wedge$ B) $\equiv$ ($\neg$ A) $\vee$ ($\neg$ B)
   2. $\neg$ (A $\vee$ B) $\equiv$ ($\neg$ A) $\wedge$ ($\neg$ B)
7. Commutative Laws:
   1. A $\wedge$ B $\equiv$ B $\wedge$ A
   2. A $\vee$ B $\equiv$ B $\vee$ A
8. Associative Laws:
   1. A $\wedge$ (B $\wedge$ C) $\equiv$ (A $\wedge$ B) $\wedge$ C
   2. A $\vee$ (B $\vee$ C) $\equiv$ (A $\vee$ B) $\vee$ C
9. Distributive Laws:
   1. A $\wedge$ (B $\vee$ C) $\equiv$ (A $\wedge$ B) $\vee$ (A $\wedge$ C)
   2. A $\vee$ (B $\wedge$ C) $\equiv$ (A $\vee$ B) $\wedge$ (A $\vee$ 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 ($\neg$B) $⟹$ ($\neg$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) $\equiv$ ((A $⟹$ B) $\wedge$ (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 $\le$ 1 and x $\ge$ 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 $\exists$ x $\in$ S, P(x) prove it’s negation $\forall$ x $\in$ S, $\neg$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)
• $\forall$ k $\in$ $\mathbb{Z}$, $\exists$ x $\in$ $\mathbb{R}$, x${}^2$ + 2kx + k = 0 $\ne$ $\exists$ x $\in$ $\mathbb{R}$, $\forall$ k $\in$ $\mathbb{Z}$, x${}^2$ + 2kx + k = 0
  • Changing the order of nested quantifiers can change the truth value of a quantified statement
• To prove the implication $\forall$ x $\in$ 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 $\mid$ 6 exists since 6 = 3 * 2, exists an integer k such that 6 = 3k
• -3 $\mid$ 6 exists since 6 = (-3) * (-2), exists an integer k such that 6 = -3k
• 5 $\nmid$ 6 since no integer k exists so that 6 = k * 5
• For all integers a, a $\mid$ 0 $\because$ 0 = 0 * a
• For all non-zero integers a, a $\mid$ 0 since no integer k so that k * 0 = a
• For all integers b, 1 $\mid$ b since b can be written as b = b * 1 and -1 $\mid$ b since b can be written b = (-b) * (-1)
• Transfer of Divisibility (TD) - For all integers a, b, and c, if a $\mid$ b and b $\mid$ c, then a $\mid$ c
• Proposition 8: For all integers if a, b and c, if a $\mid$ b or a $\mid$ c, then a $\mid$ bc
  • If a $\mid$ b, then a $\mid$ bc
    • Assume a $\mid$ b, there exists an integer k so that b = ka. Substitute for b in product bc, we get
    • bc = (ka)c = kac = (kc)a
    • $\because$ kc is an integer we can conclude a $\mid$ bc
  • If a $\mid$ c, then a $\mid$ 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 $\mid$ bc
  • These proofs can be re-written as if a $\mid$ c, then a $\mid$ bc is similar, and is omitted
• Divisibility of Integer Combinations (DIC) - For all integers a, b and c, if a $\mid$ b and a $\mid$ c, then for all integers x and y, a $\mid$ (bx + cy)
• To prove an implication using contrapositive (A $⟹$ B) replace it with it’s contrapositive ($\neg$B) $⟹$ ($\neg$A)
• Anytime we come across an argument claiming A and $\neg$A are true we say there must be a contradiction in the argument
• (A $\vee$ B $⟹$ C) $\equiv$ ((A $⟹$ C) $\wedge$ (B $⟹$ C))
• Proof by Contradiction -

Chapter 4 §

• Properties of Summation (PS)
  1. Multiplying by a constant
     • ${\sum }_{i=m}^{k}c{x}_i$ = c ${\sum }_{i=m}^k{x}_i$ (where c is constant)
  2. Adding two sums and subtracting two sums
     • ${\sum }_{i=m}^k{x}_i$ + ${\sum }_{i=m}^k{y}_i$ = ${\sum }_{i=m}^k(x_i+y_i)$
     • ${\sum }_{i=m}^k{x}_i$ - ${\sum }_{i=m}^k{y}_i$ = ${\sum }_{i=m}^k(x_i-y_i)$
  3. Change the bounds of the index of summation
     • ${\sum }_{i=m}^k{x}_i$ ${\sum }_{i=m+r}^{k+r}{x}_{i-r}$
  4. Breaking a sum apart
     • ${\sum }_{i=m}^k{x}_i$ = ${\sum }_{i=m}^r{x}_i$ + ${\sum }_{i=r+1}^k{x}_i$
• Product Notation
  • ${\prod }_{i=m}^k{x}_i$ = x${}_m$x${}_{m+1}$ $\dots$ x${}_{k-1}$x${}_k$
• 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 $\in$ $\mathbb{N}$
    • If statements 1 and 2 are both true:
      • P(1)
      • For all k $\in$ $\mathbb{N}$, if P(k), then P(k + 1)
    • then statement 3 is true:
      • For all n $\in$ $\mathbb{N}$, P(n)
• Axiom 2 - Principle of Strong Induction (POSI)
  • Let P(n) be an open sentence that depends on n $\in$ $\mathbb{N}$
  • If statements 1 and 2 are both true
    1. P(1)
    2. For all k $\in$ $\mathbb{N}$, if P(1) $\wedge$ P(2) $\wedge$ $\dots$ $\wedge$ P(k) then P(k + 1)
  • then statement 3 is true: 3. For all n $\in$ $\mathbb{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 $\mathcal{U}$ - contains all the objects we might encounter in a given situation
• {x $\in$ $\mathcal{U}$ : P(x)}
  • x is an element of $\mathcal{U}$
  • P(x) is true
• {f(x) : x $\in$ $\mathcal{U}$}
  • containing all objects of the form f(x) such that x is an element of $\mathcal{U}$
• {f(x) : x $\in$ $\mathcal{U}$, P(x)} or {f(x) : P(x), x $\in$ $\mathcal{U}$}
  • x is an element of $\mathcal{U}$
  • P(x) is true
• Union of two sets S and T written S $\cup$ T is the set of all elements belonging to either set S or set T(or both)
  • S $\cup$ T = {x: x $\in$ S OR x $\in$ T} = {x: (x $\in$ S) $\vee$ (x $\in$ T)}
• The intersection of two sets S and T, written S $\cap$ T is the set of all elements belonging to both set S and set T
  • S $\cap$ T = {x: x $\in$ S AND x $\in$ T} = {x: (x $\in$ S) $\wedge$ (x $\in$ 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 $\in$ S AND x $\in$ T} = {x : (x $\in$ S) $\wedge$ (x $\notin$ T)} = {x : (x $\in$ S) $\wedge$ ($\neg$(x $\in$ T))}
• Complement of set S, written $\overline{S}$ is set of all elements not in S
  • $\overline{S}$ = {x : x $\notin$ S}
• $\overline{S}$ = $\mathcal{U}$ - $\mathcal{S}$
  • $\overline{S}$ = $\mathcal{U}$ - $\mathcal{S}$
• Two sets are said to be disjoint when S $\cap$ T = $\varnothing$
• A set S is called a subset of set T, written symbolically as S $\subseteq$ 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 $\subseteq$ 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 $\mid$ a and a $\ne$ 0 then b $\le$ $\mid$ a $\mid$
• Division Algorithm (DA) - a = qb + r, 0 $\le$ r < b
• Common Divisor - a, b, c $\in \mathbb{Z}$ if c $\mid$ a and c $\mid$ 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 $\le$ 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) = $\mid$ a $\mid$
  • We have gcd(a, 1) = gcd(a, -1) = 1
  • We have gcd(a, 0) = $\mid$ a $\mid$
• 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 $\lfloor x\rfloor$, is the largest integer less than or equal to x
• Extended Euclidean Algorithm (EEA)
  • Input: Integers a, b with $a\ge b>0$
  • 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 $\ge$ 3
    • $q_i\leftarrow \frac{r_i-2}{r_i-1}$
    • Row${}_i$ $\leftarrow$ Row${}_{i-2}$ - q${}_i$Row${}_{i-1}$
  • Stop: When r${}_i$ = 0
  • Output: Set n = i - 1. Then gcd(a, b) = r${}_n$, and s = x${}_n$ and t = y${}_n$ are a certificate of correctness
• Common Divisor Divides GCD (CDD GCD) - For all integers a, b, and c, if c $\mid$ a and c $\mid$ b then c $\mid$ 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($\frac{a}{d},\frac{b}{d}$) = 1, where d = gcd(a, b)
• Coprimeness and Divisibility (CAD) - For all integers a, b and c, if c $\mid$ ab and gcd(a, c) = 1, then c $\mid$ 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 $\mid$ ab, then p $\mid$ a or p $\mid$ 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 $\sqrt{n}$
• Divisors From Prime Factorization (DFPF)
  • Let n and c be positive integers
  • let n = p${}_1^{{\alpha }_1}$ $\cdot$ p${}_2^{{\alpha }_2}$ $\dots$ p${}_k^{{\alpha }_k}$
  • The integer c is a positive divisor of n if and only if c can be represented as a product
  • c = $p_1^{{\beta }_1}\cdot p_2^{{\beta }_2}\dots p_k^{{\beta }_k}$, where $0\le {\beta }_i\le {\alpha }_i$ for i = 1, 2, $\dots$, k
• GCD From Prime Factorization (GCD PF)
  • Let a and be positive integers, and let
  • a = $p_1^{{\alpha }_1}\cdot p_2^{{\alpha }_2}\dots p_k^{{\alpha }_k}$
  • b = $p_1^{{\beta }_1}\cdot p_2^{{\beta }_2}\dots p_k^{{\beta }_k}$
  • gcd(a, b) = p${}_1^{{\gamma }_1}\cdot p_2^{{\gamma }_2}\dots p_k^{{\gamma }_k}$ where ${\gamma }_i$ = min {${\alpha }_i,{\beta }_i$} for i = 1, 2, $\dots$, 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 $\mid$ 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${}_0$ and y = y${}_0$ 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 = $x_0+\frac{b}{d}n,y=y_0-\frac{a}{d}n,n\in \mathbb{Z}$}

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

$a\equiv b$ (mod m) > when $m\mid (a-b)$. For integers a and b such that $m\nmid (a-b)$, we write $a\cancel{\equiv }b$ (mod m). We refer to $\equiv$ 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. $a\equiv a$ (mod m)
2. If $a\equiv a$ (mod m), then $b\equiv a$ (mod m)
3. If $a\equiv b$ (mod m) and $b\equiv c$ (mod m), then $a\equiv c$ (mod m)

• For all integers $a_1,a_2,b_1$ and $b_2,$ if $a_1\equiv b_1$ (mod m) and $a_2\equiv b_2$ (mod m), then
  • $a_1+a_2\equiv b_1+b_2$ (mod m)
  • $a_1-a_2\equiv b_1-b_2$ (mod m)
  • $a_1{a}_2\equiv b_1{b}_2$ (mod m)

[!Congruence Add and Multiply (CAM)]

For all positive integers n, for all integers $a_1,\dots ,a_n$ and $b_1,\dots ,b_n$ if $a_i\equiv b_i$ (mod m) for all $1\le i\le n$ then

1. $a_1+a_2+\cdots +a_n\equiv b_1+b_2+\cdots +b_n$ (mod m)
2. $a_1{a}_2\dots a_n\equiv b_1{b}_2\dots b_n$ (mod m)

[!Congruence Power (CP)]

For all positive integers n and integers a and b if $a\equiv b$ (mod m), then $a^n\equiv b^n$ (mod m)

[!Congruence Divide (CD)]

For all integers a, b and c, if $ac\equiv bc$ (mod m) and gcd(c, m) = 1, then $a\equiv b$ (mod m)

[!Congruent Iff Same Reminder (CISR)]

For all integers a and b, $a\equiv 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 $0\le b<m,a\equiv b$ (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 $S_e-S_o$ is divisible by 11
  • $S_e$ is the sum of the digits of even powers (of 10) in digits of a
  • $S_o$ is the sum of digits of odd powers (of 10) in digits of a

[!Congruence Class]

$[a]=x\in \mathbb{Z}:x\equiv a(modm)$

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

In modular arithmetic, following properties hold for all [a] $\in {\mathbb{Z}}_m$:

1. $[a]+[0]=[0]+[a]=[a]$
2. $[a][0]=[0][a]=[0]$
3. $[a]+[-a]=[-a]+[a]=[0]$
4. $[a][1]=[1][a]=[a]$

[!Modular Arithmetic Theorem (MAT)]

For all integers a and c, with a non-zero, the equation $[a][x]=[c]$

in ${\mathbb{Z}}_m$ has a solution if and only if $d\mid c$ where d = gcd(a, m). When $d\mid c$ there are d solutions given by

$[x_0],[x_0+\frac{m}{d}],[x_0+2\frac{m}{d}],\dots ,[x_0+(d-1)\frac{m}{d}]$ Where $[x]=[x_0]$ is one particular solution

[!Fermat’s Little Theorem (FLT)]

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

$a^{p-1}\equiv 1$ (mod $p$)

[!flt variation]

For all prime numbers p and integers a, we have $a^p\equiv a$ (mod $p$)

[!Chinese Remainder Theorem]

For all integers $a_1$ and $a_2$ and positive integers $m_1$ and $m_2$, if gcd($m_1,m_2$) = 1, then the simultaneous linear congruences

• $n\equiv a_1$ (mod $m_1$)
• $n\equiv a_2$ (mod $m_2$)

have a unique solution modulo $m_1{m}_2$. Thus if $n=n_0$ is one particular solution, then the solutions are given by the set of all integers n such that

$n\equiv n_0$ (mod $m_1{m}_2$)