Discrete Mathematics

Mathematical Proofs

Foundations of logic, direct proofs, induction, GCD, Fermat's Little Theorem, and modular arithmetic

• Statements and Mathematical Jargon

  What is a Statement?

  A statement is a sentence that is either true or false, but not both. This is the fundamental unit of mathematical discourse.

  Examples of Statements

  • $e^{i\pi} + 1 = 0$
  • “17 is a prime number”
  • “There are infinitely many primes”

  Non-examples

  • “This statement is false” (paradox)
  • “Is 7 prime?” (question, not a statement)
  • “Let $x = 5$” (command, not a statement)

  Predicates

  A predicate is a statement whose truth depends on the value of one or more free variables.

  Examples

  • $P(n) : \equiv$ ”$n$ is even”
  • $Q(x, y) : \equiv$ "$x^2 + y^2 = 1$"
  • “The function $f$ is differentiable”

  A predicate becomes a statement once we substitute specific values for its free variables.

  The Hierarchy of Mathematical Results

  Mathematicians distinguish different types of true statements:

  Axiom

  A statement assumed true without proof. Axioms form the foundation of a mathematical theory.

  Example: The axioms of Zermelo-Fraenkel set theory (ZF).

  Definition

  A name given to a concept, establishing terminology.

  Example: “A prime number is a natural number greater than 1 divisible only by 1 and itself.”

  Theorem

  A major proved result of significant importance.

  Example: Fermat’s Last Theorem, the Fundamental Theorem of Arithmetic.

  Proposition

  A proved result of lesser importance than a theorem.

  Lemma

  A result proved chiefly to support the proof of another result. Lemmas are “helper theorems.”

  Example: The “lifting the exponent lemma” used in number theory proofs.

  Corollary

  A statement that follows easily from a previously proved theorem or proposition.

  Example: “There are infinitely many primes congruent to 3 mod 4” is a corollary of Dirichlet’s theorem.

  Conjecture

  A statement believed to be true but not yet proved.

  Example: The Goldbach Conjecture (every even integer greater than 2 is the sum of two primes).

  Why Precision Matters

  Consider the statement: “The product of two odd integers is odd.”

  This hides significant logical structure. More precisely:

  $\text{For all integers } m, n: \text{ if } m \text{ and } n \text{ are odd, then } m \cdot n \text{ is odd.}$

  Even more formally:

  $\forall m, n \in \mathbb{Z}. \left( \text{Odd}(m) \land \text{Odd}(n) \right) \Rightarrow \text{Odd}(m \cdot n)$

  Tripos Credit

  Marks are awarded for making such logical structure explicit, not just for getting the right answer. A solution that correctly proves the result but fails to exhibit awareness of the quantifiers and implication structure may lose marks.

  Variables and Scope

  Free Variables

  A variable is free in a statement if the statement’s truth depends on its value.

  In "$x > 5$", the variable $x$ is free.

  Bound Variables

  A variable is bound if it is quantified by $\forall$ or $\exists$.

  In "$\forall x \in \mathbb{R}. x^2 \geq 0$", the variable $x$ is bound by the universal quantifier.

  Common Notation

  Logical Symbols

  Symbol	Meaning
  $\land$	and (conjunction)
  $\lor$	or (disjunction)
  $\neg$	not (negation)
  $\Rightarrow$	implies
  $\Leftrightarrow$	if and only if
  $\forall$	for all
  $\exists$	there exists

  Set Notation

  Symbol	Meaning
  $\in$	element of
  $\subseteq$	subset
  $\cup$	union
  $\cap$	intersection
  $\setminus$	set difference
  $\mathbb{N}$	natural numbers $\{0, 1, 2, \ldots\}$
  $\mathbb{Z}$	integers $\{\ldots, -1, 0, 1, \ldots\}$
  $\mathbb{Q}$	rational numbers
  $\mathbb{R}$	real numbers

  Number Notation

  • $a \mid b$ means ”$a$ divides $b$”
  • $a \equiv b \pmod{n}$ means ”$a$ is congruent to $b$ modulo $n$”
  • $\gcd(a, b)$ means “greatest common divisor of $a$ and $b$“

  ---

  Summary

  • A statement is a sentence that is either true or false
  • A predicate is a statement with free variables
  • Mathematical results form a hierarchy: axiom, definition, theorem, proposition, lemma, corollary, conjecture
  • Precision in stating logical structure is essential for rigorous proof and earns Tripos credit

• Implication and Direct Proof

  The Implication Connective

  An implication is a statement of the form “If $P$, then $Q$”, written $P \Rightarrow Q$.

  • $P$ is the antecedent (or hypothesis, premise)
  • $Q$ is the consequent (or conclusion)

  Truth Table

  $P$	$Q$	$P \Rightarrow Q$
  T	T	T
  T	F	F
  F	T	T
  F	F	T

  The implication $P \Rightarrow Q$ is false only when $P$ is true and $Q$ is false.

  Vacuous Truth

  When $P$ is false, the implication $P \Rightarrow Q$ is true regardless of $Q$. This is called vacuous truth.

  Example: “If $0 = 1$, then pigs fly” is true (vacuously).

  Logical Equivalences

  Contrapositive

  The contrapositive of $P \Rightarrow Q$ is $\neg Q \Rightarrow \neg P$.

  Theorem: An implication is logically equivalent to its contrapositive: $P \Rightarrow Q \equiv \neg Q \Rightarrow \neg P$

  Converse

  The converse of $P \Rightarrow Q$ is $Q \Rightarrow P$.

  Important: The converse is NOT equivalent to the original. Proving the converse does not prove the original implication.

  $P$	$Q$	$P \Rightarrow Q$	$Q \Rightarrow P$
  T	T	T	T
  T	F	F	T
  F	T	T	F
  F	F	T	T

  Inverse

  The inverse of $P \Rightarrow Q$ is $\neg P \Rightarrow \neg Q$.

  Important: The inverse is equivalent to the converse (not to the original).

  Proof Strategies for Implication

  Method 1: Direct Proof

  To prove $P \Rightarrow Q$:

  1. Assume $P$ is true
  2. Using logical steps, derive $Q$

  Method 2: Proof by Contrapositive

  To prove $P \Rightarrow Q$:

  1. Assume $\neg Q$ is true
  2. Using logical steps, derive $\neg P$

  The contrapositive is useful when $\neg Q$ provides a “stronger” starting point than $P$.

  Example: Direct Proof

  Statement: If $n$ is even, then $n^2$ is even.

  Direct proof:

  1. Assume $n$ is even
  2. Then $n = 2k$ for some integer $k$
  3. So $n^2 = (2k)^2 = 4k^2 = 2(2k^2)$
  4. Since $2k^2$ is an integer, $n^2$ is even

  Example: Proof by Contrapositive

  Statement: If $n^2$ is even, then $n$ is even.

  Contrapositive: If $n$ is odd, then $n^2$ is odd.

  Proof:

  1. Assume $n$ is odd
  2. Then $n = 2k + 1$ for some integer $k$
  3. So $n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$
  4. Since $2k^2 + 2k$ is an integer, $n^2 = 2m + 1$ for some integer $m$
  5. Therefore $n^2$ is odd

  By the contrapositive, if $n^2$ is even, then $n$ is even.

  Combining Implications

  Transitivity

  If $P \Rightarrow Q$ and $Q \Rightarrow R$, then $P \Rightarrow R$.

  Hypothetical Syllogism

  From $P \Rightarrow Q$ and $Q \Rightarrow R$, conclude $P \Rightarrow R$.

  Common Pitfalls

  Confusing Converse and Implication

  Trap: Proving $Q \Rightarrow P$ does not prove $P \Rightarrow Q$.

  Example: “If $x > 5$, then $x > 3$” is true. Its converse “If $x > 3$, then $x > 5$” is false (consider $x = 4$).

  Assuming the Conclusion

  Trap: When proving $P \Rightarrow Q$, do not assume $Q$ at the start. This is circular reasoning.

  Forgetting the Antecedent

  Trap: When proving $P \Rightarrow Q$, you must begin by assuming $P$. If you forget this, your proof structure is incorrect.

  Multiple Antecedents

  Implications can have multiple antecedents:

  $P_1 \land P_2 \land P_3 \Rightarrow Q$

  To prove this:

  1. Assume all of $P_1$, $P_2$, $P_3$
  2. Derive $Q$

  ---

  Summary

  • $P \Rightarrow Q$ means “if $P$ then $Q$”
  • The contrapositive $\neg Q \Rightarrow \neg P$ is logically equivalent
  • The converse $Q \Rightarrow P$ is NOT equivalent
  • Direct proof: assume $P$, derive $Q$
  • Proof by contrapositive: assume $\neg Q$, derive $\neg P$

• Bi-implication

  The Bi-implication Connective

  A bi-implication is a statement of the form ”$P$ if and only if $Q$”, written $P \Leftrightarrow Q$ or ”$P$ iff $Q$”.

  Truth Table

  $P$	$Q$	$P \Leftrightarrow Q$
  T	T	T
  T	F	F
  F	T	F
  F	F	T

  $P \Leftrightarrow Q$ is true exactly when $P$ and $Q$ have the same truth value.

  Logical Equivalence

  $P \Leftrightarrow Q \equiv (P \Rightarrow Q) \land (Q \Rightarrow P)$

  This decomposition is crucial for proofs.

  Proof Strategy for Bi-implication

  To prove $P \Leftrightarrow Q$, you must prove both directions:

  1. Forward direction: Prove $P \Rightarrow Q$
  2. Reverse direction: Prove $Q \Rightarrow P$

  These two proofs are typically separate and may use different techniques.

  Example

  Statement: An integer $n$ is even if and only if $n^2$ is even.

  Proof:

  $(\Rightarrow)$ If $n$ is even, then $n^2$ is even:

  • If $n$ is even, then $n = 2k$ for some integer $k$
  • So $n^2 = 4k^2 = 2(2k^2)$
  • Since $2k^2$ is an integer, $n^2$ is even

  $(\Leftarrow)$ If $n^2$ is even, then $n$ is even:

  • By contrapositive: if $n$ is odd, then $n^2$ is odd
  • If $n = 2k + 1$ for some integer $k$
  • Then $n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2+2k) + 1$
  • This is odd, so by contrapositive the claim holds

  Therefore $n$ is even if and only if $n^2$ is even.

  Alternative Proofs

  Sometimes both directions can be proved simultaneously using logical equivalences.

  Example

  Statement: $P \Rightarrow Q$ is logically equivalent to $\neg P \lor Q$.

  Proof:

  Compare truth tables:

  $P$	$Q$	$\neg P$	$P \Rightarrow Q$	$\neg P \lor Q$
  T	T	F	T	T
  T	F	F	F	F
  F	T	T	T	T
  F	F	T	T	T

  Since both columns are identical, $P \Rightarrow Q \Leftrightarrow \neg P \lor Q$.

  Chain of Bi-implications

  For a chain of equivalences:

  $P_1 \Leftrightarrow P_2 \Leftrightarrow P_3 \Leftrightarrow \cdots \Leftrightarrow P_n$

  you can prove:

  $P_1 \Rightarrow P_2 \Rightarrow P_3 \Rightarrow \cdots \Rightarrow P_n \Rightarrow P_1$

  This proves all pairwise equivalences by transitivity.

  Example

  Statement: $x = 1 \Leftrightarrow x^2 = 1$ (for real $x$).

  This is false! Check: $x = -1$ gives $x^2 = 1$ but $x \neq 1$.

  Correct statement: For real $x \geq 0$, $x = 1 \Leftrightarrow x^2 = 1$.

  Common Pitfalls

  Proving Only One Direction

  Trap: Proving $P \Rightarrow Q$ does not prove $P \Leftrightarrow Q$.

  You must prove both directions separately.

  Assuming Equivalence

  Trap: Do not assume $P \Leftrightarrow Q$ before proving it.

  If you use logical equivalences in scratch work, verify each step is truly an equivalence.

  Missing Cases

  Trap: A bi-implication over a domain may fail for certain values.

  Always check the domain: ”$n$ is prime” $\Leftrightarrow$ ”$n$ has exactly two divisors” fails for $n = 1$.

  ---

  Summary

  • $P \Leftrightarrow Q$ means ”$P$ if and only if $Q$”
  • Equivalent to $(P \Rightarrow Q) \land (Q \Rightarrow P)$
  • Prove both directions separately
  • Check that the domain is correct for the equivalence to hold

• Universal Quantification

  The Universal Quantifier

  The universal quantifier $\forall$ means “for all” or “for every”.

  The statement $\forall x. P(x)$ means: $P(x)$ is true for every element $x$ in the domain of discourse.

  Syntax

  $\forall x \in S. P(x)$

  means “for all $x$ in the set $S$, $P(x)$ holds.”

  Examples

  • $\forall n \in \mathbb{N}. n \geq 0$ (true)
  • $\forall n \in \mathbb{Z}. n^2 \geq 0$ (true)
  • $\forall n \in \mathbb{Z}. n > 0$ (false: $-1$ is a counterexample)

  Proof Strategy: Universal Generalisation

  To prove $\forall x \in S. P(x)$:

  1. Fix an arbitrary $x$: “Let $x \in S$ be arbitrary”
  2. Prove $P(x)$: Show that $P(x)$ holds for this fixed $x$
  3. Conclude: Since $x$ was arbitrary, the statement holds for all $x \in S$

  Key Point

  The $x$ you work with must be arbitrary, not a specific value. You cannot assume anything about $x$ beyond what every element of $S$ satisfies.

  Example

  Statement: For all integers $n$, if $n$ is even then $n + 2$ is even.

  Proof:

  Let $n \in \mathbb{Z}$ be arbitrary. Assume $n$ is even.

  Then $n = 2k$ for some integer $k$.

  We have $n + 2 = 2k + 2 = 2(k + 1)$.

  Since $k + 1$ is an integer, $n + 2$ is even.

  Since $n$ was arbitrary, the statement holds for all integers.

  Nested Quantifiers

  Multiple quantifiers can be nested. The order matters:

  $\forall x. \forall y. P(x, y)$

  “For all $x$ and for all $y$, $P(x, y)$ holds.”

  $\forall y. \forall x. P(x, y)$

  These are equivalent: $\forall x. \forall y. P(x, y) \equiv \forall y. \forall x. P(x, y)$

  However, when mixing $\forall$ and $\exists$, order matters critically.

  Scope and Binding

  Example

  In $\forall x \in \mathbb{N}. x + y > 0$:

  • $x$ is bound by $\forall$
  • $y$ is free (the statement depends on $y$)

  In $\forall x. \forall y. x + y > 0$:

  • Both $x$ and $y$ are bound

  Restricted Quantification

  Instead of $\forall x \in S. P(x)$, you may see:

  $\forall x. (x \in S \Rightarrow P(x))$

  These are logically equivalent.

  Example

  $\forall n \in \mathbb{N}. n \geq 0$ is equivalent to $\forall n. (n \in \mathbb{N} \Rightarrow n \geq 0)$.

  Common Structures

  Universal Implication

  $\forall x. (P(x) \Rightarrow Q(x))$ means “for all $x$, if $P(x)$ then $Q(x)$”.

  To prove:

  1. Fix arbitrary $x$
  2. Assume $P(x)$
  3. Prove $Q(x)$

  Hidden Quantifiers

  Many statements hide quantifiers:

  “The product of two odd integers is odd.”

  Formally: $\forall m, n \in \mathbb{Z}. (\text{Odd}(m) \land \text{Odd}(n)) \Rightarrow \text{Odd}(m \cdot n)$

  Common Pitfalls

  Forgetting to Fix Arbitrarily

  Trap: Proving for a specific value does not prove “for all”.

  Proving $P(0)$, $P(1)$, $P(2)$ does not prove $\forall n. P(n)$.

  Using Non-arbitrary Values

  Trap: If you pick $x = 5$ and prove $P(5)$, you have not proved $\forall x. P(x)$.

  You must prove it for an arbitrary, unspecified $x$.

  Assuming the Consequent

  Trap: When proving $\forall x. (P(x) \Rightarrow Q(x))$, you assume $P(x)$, not $Q(x)$.

  ---

  Summary

  • $\forall x. P(x)$ means ”$P(x)$ is true for all $x$”
  • Proof by universal generalisation: fix arbitrary $x$, prove $P(x)$
  • $\forall x. \forall y. P(x, y) \equiv \forall y. \forall x. P(x, y)$
  • Hidden quantifiers must be made explicit for rigorous proof

• Existential Quantification

  The Existential Quantifier

  The existential quantifier $\exists$ means “there exists” or “there is”.

  The statement $\exists x. P(x)$ means: there is at least one element $x$ (in the domain) such that $P(x)$ holds.

  Syntax

  $\exists x \in S. P(x)$

  means “there exists an $x$ in the set $S$ such that $P(x)$ holds.”

  Examples

  • $\exists n \in \mathbb{N}. n > 10$ (true: $n = 11$ works)
  • $\exists n \in \mathbb{Z}. n^2 = 4$ (true: $n = 2$ or $n = -2$)
  • $\exists n \in \mathbb{Z}. n^2 = 2$ (false: no integer squared equals 2)

  Proof Strategy: Constructive Existence

  To prove $\exists x \in S. P(x)$:

  1. Exhibit a witness: Find a specific value $x_0 \in S$
  2. Verify: Prove that $P(x_0)$ holds

  This is called a constructive proof of existence.

  Example

  Statement: There exists an even prime number.

  Proof:

  Take $x_0 = 2$.

  We verify: $2$ is even (since $2 = 2 \cdot 1$) and $2$ is prime (its only divisors are $1$ and $2$).

  Therefore, $\exists n \in \mathbb{N}$ such that $n$ is even and prime.

  Non-constructive Existence

  Sometimes we can prove $\exists x. P(x)$ without exhibiting a specific witness.

  Example: “There exist irrational numbers $a, b$ such that $a^b$ is rational.”

  Non-constructive proof: Consider $\sqrt{2}^{\sqrt{2}}$.

  • If it’s rational, take $a = \sqrt{2}$, $b = \sqrt{2}$
  • If it’s irrational, take $a = \sqrt{2}^{\sqrt{2}}$, $b = \sqrt{2}$, and note $a^b = (\sqrt{2}^{\sqrt{2}})^{\sqrt{2}} = \sqrt{2}^2 = 2$

  In either case, such $a, b$ exist.

  Nested Quantifiers

  $\exists x. \forall y. P(x, y)$

  “There exists an $x$ such that for all $y$, $P(x, y)$ holds.”

  $\forall y. \exists x. P(x, y)$

  “For all $y$, there exists an $x$ such that $P(x, y)$ holds.”

  Order Matters!

  These are NOT equivalent:

  $\exists x. \forall y. P(x, y) \not\equiv \forall y. \exists x. P(x, y)$

  Example

  Consider $P(x, y) : \equiv$ ”$x$ loves $y$” over people.

  • $\exists x. \forall y. P(x, y)$: There is someone who loves everyone.
  • $\forall y. \exists x. P(x, y)$: Everyone is loved by someone.

  The second is much weaker.

  Example over $\mathbb{R}$

  • $\exists x. \forall y. x \leq y$: False (no smallest real)
  • $\forall y. \exists x. x \leq y$: True (take $x = y - 1$)

  De Morgan’s Laws for Quantifiers

  Negation of Universal

  $\neg(\forall x. P(x)) \equiv \exists x. \neg P(x)$

  “It is not the case that all $x$ satisfy $P$” means “there exists an $x$ that does not satisfy $P$.”

  Negation of Existential

  $\neg(\exists x. P(x)) \equiv \forall x. \neg P(x)$

  “It is not the case that some $x$ satisfes $P$” means “all $x$ fail to satisfy $P$.”

  Example

  $\neg(\forall n \in \mathbb{N}. n > 0) \equiv \exists n \in \mathbb{N}. n \leq 0$

  The witness is $n = 0$.

  Common Structures

  Existential Implication

  $\exists x. (P(x) \Rightarrow Q(x))$ is tricky.

  Note: $P(x) \Rightarrow Q(x)$ is equivalent to $\neg P(x) \lor Q(x)$.

  So $\exists x. (P(x) \Rightarrow Q(x))$ is equivalent to $\exists x. (\neg P(x) \lor Q(x))$.

  Example

  $\exists x \in \mathbb{R}. (x < 0 \Rightarrow x^2 < 0)$

  This is true: take $x = 1$. Then $x < 0$ is false, so the implication is vacuously true.

  Common Pitfalls

  Unverified Witness

  Trap: Claiming $\exists x. P(x)$ without verifying $P(x)$ for your candidate.

  Example: To prove $\exists n. n^2 + n + 41$ is prime, you cannot just say “take $n = 40$” without checking.

  Wrong Quantifier Order

  Trap: Confusing $\exists x. \forall y$ with $\forall y. \exists x$.

  They are NOT equivalent.

  Using a Variable Without Introduction

  Trap: Using $x$ in a proof without specifying where it comes from.

  When proving $\forall x. \exists y. P(x, y)$, for each $x$ you must say how to find $y$.

  ---

  Summary

  • $\exists x. P(x)$ means “there exists an $x$ such that $P(x)$”
  • Prove constructively: exhibit a witness $x_0$ and verify $P(x_0)$
  • Quantifier order matters: $\exists x. \forall y \not\equiv \forall y. \exists x$
  • De Morgan: $\neg\forall x. P(x) \equiv \exists x. \neg P(x)$ and $\neg\exists x. P(x) \equiv \forall x. \neg P(x)$

• Conjunction and Disjunction

  Conjunction (And)

  The conjunction $P \land Q$ means ”$P$ and $Q$”.

  Truth Table

  $P$	$Q$	$P \land Q$
  T	T	T
  T	F	F
  F	T	F
  F	F	F

  $P \land Q$ is true only when both $P$ and $Q$ are true.

  Proof Strategy

  To prove $P \land Q$:

  1. Prove $P$
  2. Prove $Q$

  Both must be proved separately.

  Disjunction (Or)

  The disjunction $P \lor Q$ means ”$P$ or $Q$”.

  In mathematics, “or” is inclusive: $P \lor Q$ is true if at least one of $P$, $Q$ is true.

  Truth Table

  $P$	$Q$	$P \lor Q$
  T	T	T
  T	F	T
  F	T	T
  F	F	F

  Proof Strategies for Disjunction

  Method 1: Prove One Disjunct

  Prove $P$ (then $P \lor Q$ follows) or prove $Q$.

  Method 2: Proof by Cases (Disjunction Elimination)

  To prove $R$ from $P \lor Q$:

  1. Case 1: Assume $P$, prove $R$
  2. Case 2: Assume $Q$, prove $R$
  3. Since $P \lor Q$ and $R$ follows in either case, conclude $R$

  Method 3: Proof by Contradiction

  To prove $P \lor Q$:

  1. Assume $\neg(P \lor Q)$
  2. By De Morgan, this means $\neg P \land \neg Q$
  3. Derive a contradiction

  Example: Proof by Cases

  Statement: For all integers $n$, $n^2 \geq n$.

  This is false. But let us prove: For all integers $n$, $n^2 \geq 0$.

  Proof by cases on $n \geq 0$ or $n < 0$:

  Case 1: $n \geq 0$.

  Then $n^2 \geq 0 \cdot n = 0$.

  Case 2: $n < 0$.

  Then $n = -k$ for some $k > 0$. So $n^2 = (-k)^2 = k^2 > 0$.

  In either case, $n^2 \geq 0$.

  De Morgan’s Laws

  For Statements

  $\neg(P \land Q) \equiv \neg P \lor \neg Q$ $\neg(P \lor Q) \equiv \neg P \land \neg Q$

  For Sets

  $S \setminus (A \cap B) = (S \setminus A) \cup (S \setminus B)$ $S \setminus (A \cup B) = (S \setminus A) \cap (S \setminus B)$

  Verification by Truth Table

  $P$	$Q$	$\neg(P \land Q)$	$\neg P \lor \neg Q$
  T	T	F	F
  T	F	T	T
  F	T	T	T
  F	F	T	T

  Distributivity

  Conjunction over Disjunction

  $P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R)$

  Disjunction over Conjunction

  $P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)$

  Associativity and Commutativity

  Both $\land$ and $\lor$ are:

  • Associative: $P \land (Q \land R) \equiv (P \land Q) \land R$
  • Commutative: $P \land Q \equiv Q \land P$

  This allows us to write $P_1 \land P_2 \land \cdots \land P_n$ and $P_1 \lor P_2 \lor \cdots \lor P_n$ without parentheses.

  Absorption Laws

  $P \land (P \lor Q) \equiv P$ $P \lor (P \land Q) \equiv P$

  Idempotent Laws

  $P \land P \equiv P$ $P \lor P \equiv P$

  Identity Laws

  $P \land \text{True} \equiv P$ $P \lor \text{False} \equiv P$

  Domination Laws

  $P \land \text{False} \equiv \text{False}$ $P \lor \text{True} \equiv \text{True}$

  Using Logical Equivalences

  These equivalences allow us to transform statements into simpler or more convenient forms.

  Example

  Simplify $\neg(P \land Q) \land P$.

  $\neg(P \land Q) \land P \equiv (\neg P \lor \neg Q) \land P$ (De Morgan) $\equiv (\neg P \land P) \lor (\neg Q \land P)$ (Distributivity) $\equiv \text{False} \lor (\neg Q \land P)$ (Contradiction) $\equiv \neg Q \land P$ (Identity)

  Common Pitfalls

  Confusing And/Or

  Trap: “P or Q” in mathematics includes the case where both are true.

  This is different from everyday English where “or” often means “exactly one”.

  Forgetting a Case

  Trap: When using proof by cases, check you have covered all possibilities.

  If your cases are $n > 0$ and $n < 0$, you forgot $n = 0$.

  Overlapping Cases

  Trap: Cases need not be disjoint, but each case must be proved.

  Cases may overlap; what matters is each case individually leads to the conclusion.

  ---

  Summary

  • $P \land Q$ requires proving both $P$ and $Q$
  • $P \lor Q$ can be proved by proving one, or by cases
  • De Morgan’s laws: $\neg(P \land Q) \equiv \neg P \lor \neg Q$ and $\neg(P \lor Q) \equiv \neg P \land \neg Q$
  • Both connectives are associative, commutative, and distributive over each other

• Negation and Proof by Contradiction

  Negation

  The negation of a statement $P$, written $\neg P$, is true when $P$ is false and false when $P$ is true.

  Truth Table

  $P$	$\neg P$
  T	F
  F	T

  Double Negation

  $\neg(\neg P) \equiv P$

  Negation of Compound Statements

  Negation of Conjunction and Disjunction

  $\neg(P \land Q) \equiv \neg P \lor \neg Q$ $\neg(P \lor Q) \equiv \neg P \land \neg Q$

  Negation of Implication

  $\neg(P \Rightarrow Q) \equiv P \land \neg Q$

  This is because $P \Rightarrow Q \equiv \neg P \lor Q$, so:

  $\neg(P \Rightarrow Q) \equiv \neg(\neg P \lor Q) \equiv P \land \neg Q$

  Negation of Quantifiers

  $\neg(\forall x. P(x)) \equiv \exists x. \neg P(x)$ $\neg(\exists x. P(x)) \equiv \forall x. \neg P(x)$

  Negation of Bi-implication

  $\neg(P \Leftrightarrow Q) \equiv (P \land \neg Q) \lor (\neg P \land Q)$

  The negation says “exactly one of $P$, $Q$ holds.”

  Proof by Contradiction

  The Principle

  To prove $P$ by contradiction:

  1. Assume $\neg P$
  2. Derive a contradiction (e.g., $Q \land \neg Q$ for some statement $Q$)
  3. Conclude $P$ must be true

  This is also called reductio ad absurdum.

  Logical Justification

  From $\neg P \Rightarrow \text{False}$, we conclude $P$.

  Since $\neg P \Rightarrow \text{False}$ is equivalent to $\neg(\neg P) \lor \text{False} \equiv P \lor \text{False} \equiv P$.

  Examinable Proof: Irrationality of $\sqrt{2}$

  Theorem: $\sqrt{2}$ is irrational.

  Proof by contradiction:

  Suppose $\sqrt{2}$ is rational. Then $\sqrt{2} = \frac{p}{q}$ for integers $p, q$ with $\gcd(p, q) = 1$ (the fraction is in lowest terms).

  Squaring: $2 = \frac{p^2}{q^2}$, so $p^2 = 2q^2$.

  This means $p^2$ is even. Since $n$ even implies $n^2$ even, and $n^2$ even implies $n$ even (contrapositive), we have $p$ is even.

  Write $p = 2k$ for some integer $k$.

  Substituting: $4k^2 = 2q^2$, so $q^2 = 2k^2$.

  Thus $q^2$ is even, so $q$ is even.

  But $p$ and $q$ are both even, contradicting $\gcd(p, q) = 1$.

  Therefore $\sqrt{2}$ is irrational.

  Examinable Proof: Infinitude of Primes

  Theorem: There are infinitely many prime numbers.

  Proof by contradiction (Euclid):

  Suppose there are finitely many primes: $p_1, p_2, \ldots, p_n$.

  Let $N = p_1 \cdot p_2 \cdot \cdots \cdot p_n + 1$.

  Since $N > 1$, the Fundamental Theorem of Arithmetic says $N$ has a prime divisor $p$.

  If $p = p_i$ for some $i$, then $p \mid p_1 \cdot p_2 \cdot \cdots \cdot p_n$ and $p \mid N$.

  This implies $p \mid (N - p_1 \cdot p_2 \cdot \cdots \cdot p_n) = 1$.

  But no prime divides 1. Contradiction.

  Therefore $p$ is not in our list, so there is a prime not among $p_1, \ldots, p_n$.

  This contradicts the assumption of finitely many primes.

  Therefore there are infinitely many primes.

  When to Use Contradiction

  Contradiction is useful when:

  1. The negation gives better structure (e.g., proving irrationals)
  2. Direct proof seems impossible or awkward
  3. The statement asserts non-existence or impossibility

  Example: Negation Simplifies Structure

  Statement: There are no integers $a, b$ such that $a^2 = 2b^2$.

  If we negate: “There exist integers $a, b$ such that $a^2 = 2b^2$.”

  This gives us something to work with algebraically.

  Contradiction vs Contrapositive

  If you find yourself assuming $\neg P$ and deriving $\neg Q$, you might instead prove the contrapositive $Q \Rightarrow P$ directly.

  Both are valid; contrapositive is often clearer when applicable.

  Example

  Statement: If $n^2$ is even, then $n$ is even.

  • Contrapositive proof: If $n$ is odd, then $n^2$ is odd. (Direct)
  • Contradiction proof: Suppose $n^2$ is even and $n$ is odd. Then $n^2$ is odd. Contradiction.

  Both work; contrapositive is simpler here.

  Common Pitfalls

  Forgetting to Negate Assumptions

  Trap: In proof by contradiction, you assume $\neg P$. Some students assume $P$ instead.

  Circular Reasoning

  Trap: Assuming what you want to prove within the proof.

  This defeats the purpose of proof by contradiction.

  Overusing Contradiction

  Trap: Using contradiction when a direct proof is simpler.

  Direct proofs are often clearer. Use contradiction when necessary.

  ---

  Summary

  • $\neg(P \land Q) \equiv \neg P \lor \neg Q$ and $\neg(P \lor Q) \equiv \neg P \land \neg Q$
  • $\neg(P \Rightarrow Q) \equiv P \land \neg Q$
  • Proof by contradiction: assume $\neg P$, derive $\text{False}$
  • Examinable proofs: irrationality of $\sqrt{2}$, infinitude of primes

• Divisibility and the Division Theorem

  Divisibility

  Definition

  For integers $a$ and $b$, we say $a$ divides $b$, written $a \mid b$, if and only if there exists an integer $k$ such that $b = ak$.

  $a \mid b \iff \exists k \in \mathbb{Z}. b = ak$

  Terminology

  • $a$ is a divisor or factor of $b$
  • $b$ is a multiple of $a$
  • If $a \nmid b$, then $a$ does not divide $b$

  Examples

  • $3 \mid 12$ since $12 = 3 \cdot 4$
  • $-3 \mid 12$ since $12 = (-3) \cdot (-4)$
  • $5 \nmid 12$ since no integer $k$ satisfies $12 = 5k$
  • $a \mid 0$ for all $a \neq 0$ since $0 = a \cdot 0$

  Properties of Divisibility

  Reflexivity

  $a \mid a \quad \text{for all } a \in \mathbb{Z}$

  Transitivity

  $a \mid b \land b \mid c \Rightarrow a \mid c$

  Proof: If $b = ak$ and $c = b\ell$, then $c = ak\ell = a(k\ell)$.

  Linearity

  $a \mid b \land a \mid c \Rightarrow a \mid (bx + cy) \text{ for all } x, y \in \mathbb{Z}$

  Proof: If $b = ak$ and $c = a\ell$, then $bx + cy = akx + a\ell y = a(kx + \ell y)$.

  Antisymmetry (up to sign)

  $a \mid b \land b \mid a \Rightarrow a = \pm b$

  Proof: If $a \mid b$ and $b \mid a$, then $b = ak$ and $a = b\ell$ for integers $k, \ell$.

  Hence $a = ak\ell$, so $a(1 - k\ell) = 0$.

  If $a = 0$, then $b = 0$ and $a = b$.

  If $a \neq 0$, then $k\ell = 1$. Since $k, \ell \in \mathbb{Z}$, we have $(k, \ell) = (1, 1)$ or $(-1, -1)$.

  Thus $b = a$ or $b = -a$.

  The Division Theorem

  Statement

  Theorem (Division Theorem): For any integer $a$ and positive integer $b > 0$, there exist unique integers $q$ and $r$ such that:

  $a = bq + r \quad \text{with } 0 \leq r < b$

  • $q$ is the quotient (how many times $b$ fits into $a$)
  • $r$ is the remainder (what is left over)
  • We write $r = a \bmod b$

  Examples

  $a$	$b$	$q$	$r$	Verification
  17	5	3	2	$17 = 5 \cdot 3 + 2$
  -17	5	-4	3	$-17 = 5 \cdot (-4) + 3$
  20	7	2	6	$20 = 7 \cdot 2 + 6$
  14	2	7	0	$14 = 2 \cdot 7 + 0$

  Proof Outline

  Existence:

  Consider the set $S = \{a - bk : k \in \mathbb{Z}, a - bk \geq 0\}$.

  This set is non-empty (take $k$ large and negative if $a < 0$, or $k = 0$ if $a \geq 0$).

  Let $r$ be the smallest element of $S$. Then $r = a - bq \geq 0$ for some $q$.

  If $r \geq b$, then $r - b = a - b(q+1) \geq 0$, contradicting minimality.

  So $0 \leq r < b$.

  Uniqueness:

  If $a = bq_1 + r_1 = bq_2 + r_2$ with $0 \leq r_1, r_2 < b$:

  Then $b(q_1 - q_2) = r_2 - r_1$.

  We have $|r_2 - r_1| < b$, so $b \mid (r_2 - r_1)$ forces $r_2 - r_1 = 0$.

  Thus $r_1 = r_2$ and hence $q_1 = q_2$.

  Computing Quotient and Remainder

  For Non-negative $a$

  $q = \lfloor a/b \rfloor \quad \text{and} \quad r = a - bq$

  For Negative $a$

  Be careful: $-17 \bmod 5 = 3$, not $-2$.

  The standard convention requires $0 \leq r < b$:

  $r = a - b \cdot \left\lfloor \frac{a}{b} \right\rfloor$

  Properties of Remainder

  Invariance under Addition

  If $a \equiv r \pmod{b}$ and $c \equiv s \pmod{b}$ with $0 \leq r, s < b$, then:

  $a + c \equiv r + s \pmod{b}$

  Invariance under Multiplication

  If $a \equiv r \pmod{b}$ and $c \equiv s \pmod{b}$ with $0 \leq r, s < b$, then:

  $ac \equiv rs \pmod{b}$

  ---

  Summary

  • $a \mid b$ means there exists $k$ with $b = ak$
  • Divisibility is reflexive, transitive, and antisymmetric up to sign
  • The Division Theorem: for $b > 0$, unique $q, r$ with $a = bq + r$ and $0 \leq r < b$
  • Remainder satisfies $0 \leq r < b$ even for negative $a$

• Modular Arithmetic

  Congruence Modulo $n$

  Definition

  For integers $a, b$ and a positive integer $n \geq 1$, we say $a$ is congruent to $b$ modulo $n$, written $a \equiv b \pmod{n}$, if and only if:

  $n \mid (a - b)$

  Equivalently, $a \equiv b \pmod{n}$ iff $a$ and $b$ have the same remainder when divided by $n$.

  Examples

  • $17 \equiv 5 \pmod{12}$ since $17 - 5 = 12$ and $12 \mid 12$
  • $23 \equiv 2 \pmod{7}$ since $23 - 2 = 21$ and $7 \mid 21$
  • $-5 \equiv 3 \pmod{8}$ since $-5 - 3 = -8$ and $8 \mid -8$

  Congruence is an Equivalence Relation

  Reflexivity

  $a \equiv a \pmod{n}$

  Since $n \mid (a - a) = 0$ for all $n$.

  Symmetry

  $a \equiv b \pmod{n} \Rightarrow b \equiv a \pmod{n}$

  Since $n \mid (a - b)$ implies $n \mid (b - a)$.

  Transitivity

  $a \equiv b \pmod{n} \land b \equiv c \pmod{n} \Rightarrow a \equiv c \pmod{n}$

  Proof: $n \mid (a - b)$ and $n \mid (b - c)$ implies $n \mid [(a-b) + (b-c)] = a - c$.

  Congruence Classes

  The congruence class of $a$ modulo $n$ is:

  $[a]_n = \{b \in \mathbb{Z} : a \equiv b \pmod{n}\} = \{a + kn : k \in \mathbb{Z}\}$

  Examples

  • $[0]_3 = \{\ldots, -6, -3, 0, 3, 6, 9, \ldots\}$
  • $[1]_3 = \{\ldots, -5, -2, 1, 4, 7, 10, \ldots\}$
  • $[2]_3 = \{\ldots, -4, -1, 2, 5, 8, 11, \ldots\}$

  Number of Classes

  There are exactly $n$ congruence classes modulo $n$: $[0]_n, [1]_n, \ldots, [n-1]_n$.

  The standard representatives are $\mathbb{Z}_n = \{0, 1, 2, \ldots, n-1\}$.

  Arithmetic Operations on Congruences

  Addition

  If $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$, then:

  $a + c \equiv b + d \pmod{n}$

  Multiplication

  If $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$, then:

  $ac \equiv bd \pmod{n}$

  Powers

  If $a \equiv b \pmod{n}$, then for any $k \geq 0$:

  $a^k \equiv b^k \pmod{n}$

  Proof (Multiplication)

  Given $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$:

  $ac - bd = ac - bc + bc - bd = c(a - b) + b(c - d)$

  Since $n \mid (a - b)$ and $n \mid (c - d)$, we have $n \mid [c(a-b) + b(c-d)] = ac - bd$.

  Thus $ac \equiv bd \pmod{n}$.

  Common Pitfall: Cancellation

  The Problem

  $ac \equiv bc \pmod{n} \not\Rightarrow a \equiv b \pmod{n}$

  Counterexample

  $2 \cdot 3 \equiv 2 \cdot 0 \pmod{6}$ but $3 \not\equiv 0 \pmod{6}$.

  When Does Cancellation Work?

  If $\gcd(c, n) = 1$ and $ac \equiv bc \pmod{n}$, then $a \equiv b \pmod{n}$.

  Proof: $ac \equiv bc \pmod{n}$ means $n \mid c(a - b)$.

  Since $\gcd(c, n) = 1$, Euclid’s lemma gives $n \mid (a - b)$.

  Thus $a \equiv b \pmod{n}$.

  Divisibility Tests

  Test for 2

  $|\overline{a_k a_{k-1} \ldots a_1 a_0}|$ is divisible by 2 iff $a_0$ (the last digit) is even.

  Reason: $10 \equiv 0 \pmod{2}$, so $a_k \cdot 10^k + \cdots + a_1 \cdot 10 + a_0 \equiv a_0 \pmod{2}$.

  Test for 3

  A number is divisible by 3 iff the sum of its digits is divisible by 3.

  Reason: $10 \equiv 1 \pmod{3}$, so $a_k \cdot 10^k + \cdots + a_1 \cdot 10 + a_0 \equiv a_k + \cdots + a_0 \pmod{3}$.

  Test for 9

  A number is divisible by 9 iff the sum of its digits is divisible by 9.

  Reason: $10 \equiv 1 \pmod{9}$.

  Test for 11

  A number is divisible by 11 iff the alternating sum of digits $(a_0 - a_1 + a_2 - \cdots)$ is divisible by 11.

  Reason: $10 \equiv -1 \pmod{11}$.

  ---

  Summary

  • $a \equiv b \pmod{n}$ iff $n \mid (a - b)$
  • Congruence is an equivalence relation
  • Congruences preserve addition and multiplication
  • Cancellation requires $\gcd(c, n) = 1$
  • Divisibility tests use modular arithmetic

• Greatest Common Divisor and Euclid's Algorithm

  Greatest Common Divisor

  Definition

  For integers $a$ and $b$ (not both zero), the greatest common divisor $\gcd(a, b)$ is the largest positive integer $d$ such that $d \mid a$ and $d \mid b$.

  By convention, $\gcd(0, 0) = 0$.

  Examples

  • $\gcd(12, 18) = 6$
  • $\gcd(17, 5) = 1$
  • $\gcd(100, 0) = 100$

  Coprimality

  We say $a$ and $b$ are coprime or relatively prime if $\gcd(a, b) = 1$.

  Properties of GCD

  Symmetry

  $\gcd(a, b) = \gcd(b, a)$

  Absolute Value

  $\gcd(a, b) = \gcd(|a|, |b|)$

  If $a \mid b$

  If $a \neq 0$ and $a \mid b$, then $\gcd(a, b) = |a|$.

  Adding Multiples

  For any integers $k, \ell$:

  $\gcd(a, b) = \gcd(a - kb, b)$

  This is the key insight behind Euclid’s algorithm.

  Euclid’s Algorithm

  The Key Lemma

  $\gcd(a, b) = \gcd(b, a \bmod b)$

  Proof: Let $a = bq + r$ with $0 \leq r < b$.

  Any common divisor of $a$ and $b$ divides $r = a - bq$.

  Any common divisor of $b$ and $r$ divides $a = bq + r$.

  Thus $\{d : d \mid a \land d \mid b\} = \{d : d \mid b \land d \mid r\}$.

  Taking the maximum, $\gcd(a, b) = \gcd(b, r) = \gcd(b, a \bmod b)$.

  The Algorithm

  Euclid’s algorithm computes $\gcd(a, b)$ recursively:

  function gcd(a, b):
      if b = 0:
          return a
      else:
          return gcd(b, a mod b)

  Termination

  The second argument strictly decreases at each step: $a \bmod b < b$.

  Since $b \geq 0$ and the non-negative integers are well-ordered, the algorithm terminates.

  Example

  Compute $\gcd(48, 18)$:

  Step	$a$	$b$	$a \bmod b$
  1	48	18	12
  2	18	12	6
  3	12	6	0
  4	6	0	—

  $\gcd(48, 18) = 6$.

  Bézout’s Identity

  Statement

  Theorem (Bézout’s Identity): For integers $a$ and $b$ (not both zero), there exist integers $x$ and $y$ such that:

  $ax + by = \gcd(a, b)$

  Extended Euclidean Algorithm

  We compute $x$ and $y$ alongside the GCD by tracking linear combinations.

  Example: Find integers $x, y$ with $48x + 18y = \gcd(48, 18) = 6$.

  Working through Euclid’s algorithm:

  • $48 = 2 \cdot 18 + 12$
  • $18 = 1 \cdot 12 + 6$
  • $12 = 2 \cdot 6 + 0$

  Back-substituting:

  • $6 = 18 - 1 \cdot 12$
  • $6 = 18 - 1 \cdot (48 - 2 \cdot 18) = 3 \cdot 18 - 1 \cdot 48$

  So $x = -1$ and $y = 3$ verify $48 \cdot (-1) + 18 \cdot 3 = -48 + 54 = 6$.

  Euclid’s Lemma

  Statement

  Lemma (Euclid’s Lemma): If $p$ is prime and $p \mid ab$, then $p \mid a$ or $p \mid b$.

  Proof

  Suppose $p \nmid a$. Since $p$ is prime, $\gcd(p, a) = 1$.

  By Bézout’s Identity, there exist $x, y$ with $px + ay = 1$.

  Multiply by $b$: $pxb + aby = b$.

  Since $p \mid ab$, we have $p \mid aby$. Clearly $p \mid pxb$.

  Thus $p \mid (pxb + aby) = b$.

  Multiplicativity of GCD

  Statement

  If $\gcd(b, c) = 1$, then:

  $\gcd(a, bc) = \gcd(a, b) \cdot \gcd(a, c)$

  Proof Sketch

  Let $d_1 = \gcd(a, b)$ and $d_2 = \gcd(a, c)$.

  Since $\gcd(b, c) = 1$ and $d_1 \mid b$, $d_2 \mid c$, we have $\gcd(d_1, d_2) = 1$.

  Both $d_1$ and $d_2$ divide $a$, so $d_1 d_2$ divides $a$.

  Both $d_1$ and $d_2$ divide $bc$ (since $d_1 \mid b$ and $d_2 \mid c$), so $d_1 d_2$ divides $bc$.

  Thus $d_1 d_2 \mid \gcd(a, bc)$.

  For the reverse, use Bézout’s identity with the coprimality assumptions.

  ---

  Summary

  • $\gcd(a, b)$ is the largest common divisor, defined for $a, b$ not both zero
  • Key lemma: $\gcd(a, b) = \gcd(b, a \bmod b)$
  • Euclid’s algorithm terminates by well-foundedness
  • Bézout’s Identity: $ax + by = \gcd(a, b)$ for some $x, y$
  • Euclid’s Lemma: if prime $p \mid ab$, then $p \mid a$ or $p \mid b$

• Fermat's Little Theorem

  Statement of Fermat’s Little Theorem

  Theorem

  Fermat’s Little Theorem: If $p$ is a prime and $a$ is an integer not divisible by $p$, then:

  $a^{p-1} \equiv 1 \pmod{p}$

  Equivalent Formulation

  For any integer $a$ and prime $p$:

  $a^p \equiv a \pmod{p}$

  This form works even when $p \mid a$ (both sides are $0 \bmod p$).

  Examples

  • $p = 5$, $a = 2$: $2^4 = 16 \equiv 1 \pmod{5}$
  • $p = 7$, $a = 3$: $3^6 = 729 \equiv 1 \pmod{7}$
  • $p = 11$, $a = 2$: $2^{10} = 1024 \equiv 1 \pmod{11}$

  Examinable Proof

  The Proof Strategy

  We show that $a, 2a, 3a, \ldots, (p-1)a$ modulo $p$ form a permutation of $1, 2, 3, \ldots, p-1$.

  Step 1: Non-zeroness

  Each $ia \pmod{p}$ is non-zero for $1 \leq i \leq p-1$.

  Reason: $p \nmid a$ by hypothesis, and $p \nmid i$ since $1 \leq i < p$ and $p$ is prime.

  Thus $p \nmid ia$.

  Step 2: Distinctness

  If $ia \equiv ja \pmod{p}$ for $1 \leq i, j \leq p-1$, then $i = j$.

  Proof: $ia \equiv ja \pmod{p}$ means $p \mid (i-j)a$.

  Since $p \nmid a$ and $p$ is prime, Euclid’s lemma gives $p \mid (i-j)$.

  But $|i - j| \leq p - 2 < p$, so $|i - j| = 0$ and $i = j$.

  Step 3: Permutation Argument

  The numbers $1, 2, \ldots, p-1$ are $p-1$ distinct non-zero residues modulo $p$.

  By Steps 1 and 2, $a, 2a, \ldots, (p-1)a$ are also $p-1$ distinct non-zero residues modulo $p$.

  Therefore:

  $\{a, 2a, \ldots, (p-1)a\} = \{1, 2, \ldots, p-1\} \pmod{p}$

  Step 4: Product Equality

  Taking products:

  $a \cdot 2a \cdot 3a \cdot \cdots \cdot (p-1)a \equiv 1 \cdot 2 \cdot 3 \cdot \cdots \cdot (p-1) \pmod{p}$

  This simplifies to:

  $a^{p-1} \cdot (p-1)! \equiv (p-1)! \pmod{p}$

  Step 5: Cancellation

  Since $1 \leq (p-1)! < p!$ and $(p-1)!$ is the product of integers $1$ through $p-1$, none of which are divisible by $p$, we have $p \nmid (p-1)!$.

  Thus $\gcd(p, (p-1)!) = 1$.

  By the cancellation property of modular arithmetic:

  $a^{p-1} \equiv 1 \pmod{p}$

  Applications

  Modular Exponentiation

  To compute $a^k \bmod p$ where $p$ is prime:

  1. Reduce $k$ modulo $p-1$: $k = q(p-1) + r$ with $0 \leq r < p-1$
  2. Then $a^k \equiv a^r \pmod{p}$

  Example: Compute $3^{100} \bmod 7$.

  $100 = 16 \cdot 6 + 4$, so $3^{100} \equiv 3^4 = 81 \equiv 4 \pmod{7}$.

  Primality Testing

  If there exists $a$ with $p \nmid a$ such that $a^{p-1} \not\equiv 1 \pmod{p}$, then $p$ is not prime.

  Note: The converse is not true in general. A Carmichael number is composite but satisfies $a^{n-1} \equiv 1 \pmod{n}$ for all $a$ coprime to $n$.

  Diffie-Hellman Key Exchange

  Two parties agree on:

  • A large prime $p$
  • A generator $g$ of $(\mathbb{Z}/p\mathbb{Z})^\times$

  Each picks a secret:

  • Alice picks secret $a$, sends $g^a \bmod p$
  • Bob picks secret $b$, sends $g^b \bmod p$

  Shared secret: $(g^a)^b = (g^b)^a = g^{ab} \bmod p$.

  Security relies on the difficulty of computing discrete logarithms.

  Fermat’s Theorem and Wilson’s Theorem

  Wilson’s Theorem

  $(p-1)! \equiv -1 \pmod{p}$ iff $p$ is prime.

  Connection

  In our proof of Fermat’s Little Theorem, we used that $(p-1)!$ is coprime to $p$. Wilson’s theorem gives its exact value.

  Generalisations

  Euler’s Theorem

  For $a$ coprime to $n$: $a^{\phi(n)} \equiv 1 \pmod{n}$, where $\phi(n)$ is Euler’s totient function.

  When $n$ is prime, $\phi(n) = n-1$, giving Fermat’s Little Theorem.

  ---

  Summary

  • Fermat’s Little Theorem: $a^{p-1} \equiv 1 \pmod{p}$ for prime $p$ and $p \nmid a$
  • Proof uses permutation argument and cancellation
  • Applications: fast modular exponentiation, cryptography (Diffie-Hellman), primality testing
  • Generalised by Euler’s theorem to composite moduli

• Principles of Induction

  Simple Induction

  Principle

  To prove $\forall n \in \mathbb{N}. P(n)$:

  1. Base case: Prove $P(0)$
  2. Inductive step: Prove that for arbitrary $n \in \mathbb{N}$, $P(n) \Rightarrow P(n+1)$

  If both hold, then by the principle of mathematical induction, $P(n)$ is true for all $n \in \mathbb{N}$.

  Why It Works

  Induction is justified by the well-ordering of $\mathbb{N}$.

  Suppose $P(0)$ holds and $P(n) \Rightarrow P(n+1)$ for all $n$, but some $k$ fails $P(k)$.

  Let $S = \{n \in \mathbb{N} : \neg P(n)\}$. By assumption, $S \neq \emptyset$.

  By well-ordering, $S$ has a least element $m$.

  Since $P(0)$ holds, $m > 0$.

  Thus $m - 1 \in \mathbb{N}$ and $m - 1 \notin S$, so $P(m-1)$ holds.

  By the inductive step, $P(m)$ holds. Contradiction.

  Example: Sum Formula

  Statement: $\displaystyle\sum_{i=0}^{n-1} i = \frac{n(n-1)}{2}$ for all $n \in \mathbb{N}$.

  Base case ($n = 0$): Empty sum = 0. And $\frac{0 \cdot (-1)}{2} = 0$.

  Inductive step: Assume $\displaystyle\sum_{i=0}^{n-1} i = \frac{n(n-1)}{2}$.

  Then: $\sum_{i=0}^{n} i = \frac{n(n-1)}{2} + n = \frac{n(n-1) + 2n}{2} = \frac{n(n+1)}{2}$

  This is $\frac{(n+1)(n)}{2}$, establishing $P(n+1)$.

  Induction from a Basis

  Principle

  To prove $\forall n \geq k. P(n)$ for some fixed $k$:

  1. Base case: Prove $P(k)$
  2. Inductive step: Prove $P(n) \Rightarrow P(n+1)$ for arbitrary $n \geq k$

  When to Use

  When the property $P(n)$ is only meaningful or true for $n \geq k$.

  Example

  Statement: $2^n > n^2$ for all $n \geq 5$.

  Base case ($n = 5$): $2^5 = 32 > 25 = 5^2$.

  Inductive step: Assume $2^n > n^2$ for $n \geq 5$.

  Then $2^{n+1} = 2 \cdot 2^n > 2n^2$.

  For $n \geq 5$: $2n^2 - (n+1)^2 = 2n^2 - n^2 - 2n - 1 = n^2 - 2n - 1 \geq 25 - 10 - 1 = 14 > 0$.

  So $2n^2 > (n+1)^2$, giving $2^{n+1} > (n+1)^2$.

  Strong Induction

  Principle

  To prove $\forall n \in \mathbb{N}. P(n)$:

  1. Inductive step: Prove that for arbitrary $n$: $\left(\forall m < n. P(m)\right) \Rightarrow P(n)$

  No explicit base case needed: when $n = 0$, the hypothesis "$\forall m < 0. P(m)$" is vacuously true.

  When to Use

  When proving $P(n)$ requires multiple previous cases, not just $P(n-1)$.

  Example: Fibonacci

  The Fibonacci sequence: $F_0 = 0$, $F_1 = 1$, $F_{n+1} = F_n + F_{n-1}$.

  Statement: $F_n < 2^n$ for all $n \in \mathbb{N}$.

  Strong induction:

  Assume $\forall m < n. F_m < 2^m$.

  If $n \leq 1$: $F_0 = 0 < 1 = 2^0$ and $F_1 = 1 < 2 = 2^1$.

  For $n \geq 2$: $F_n = F_{n-1} + F_{n-2} < 2^{n-1} + 2^{n-2} = \frac{3}{4} \cdot 2^n < 2^n$

  Common Pitfalls

  Wrong Inductive Hypothesis

  Trap: Assuming $P(n-1)$ when $P(n-2)$ is also needed.

  This happens in Fibonacci-style recurrences. Use strong induction instead.

  Forgetting the Base Case

  Trap: Proving $P(n) \Rightarrow P(n+1)$ without checking $P$ holds somewhere.

  Assuming What You Prove

  Trap: The inductive step must assume $P(n)$ and derive $P(n+1)$.

  Do not assume $P(n+1)$.

  Inductive Step Fails for Small $n$

  Trap: Check the inductive step works for the transition from base case.

  Example of Failure

  False claim: All horses are the same colour.

  “Proof” by induction on herd size $n$:

  • Base ($n = 1$): Trivial.
  • Inductive step: If all horses in a herd of $n$ have the same colour, then in a herd of $n+1$:
    • First $n$ horses have same colour (by IH)
    • Last $n$ horses have same colour (by IH)
    • Therefore all $n+1$ horses have same colour.

  Error: When $n = 1$, there is no overlap between “first $n$” and “last $n$” (both are single horses). The argument fails.

  ---

  Summary

  • Simple induction: prove $P(0)$, then $P(n) \Rightarrow P(n+1)$
  • Induction from basis: $P(k)$, then $P(n) \Rightarrow P(n+1)$ for $n \geq k$
  • Strong induction: $(\forall m < n. P(m)) \Rightarrow P(n)$
  • Strong induction needed for recurrences depending on multiple predecessors

• Abstract Algebra: Monoids, Groups, Semirings, and Fields

  The Hierarchy of Algebraic Structures

  Abstract algebra studies mathematical structures by specifying the operations and properties they must satisfy. Each structure adds more requirements, making it more powerful but more restrictive.

  

  ---

  Monoids

  Definition

  A monoid is a triple $(S, \bullet, e)$ where:

  • $S$ is a set
  • $\bullet : S \times S \to S$ is a binary operation (closed)
  • $e \in S$ is the identity element

  satisfying:

  1. Associativity: $(x \bullet y) \bullet z = x \bullet (y \bullet z)$ for all $x, y, z \in S$
  2. Identity: $e \bullet x = x = x \bullet e$ for all $x \in S$

  Examples

  Monoid	Operation	Identity
  $(\mathbb{N}, +, 0)$	Addition	$0$
  $(\mathbb{N}, \times, 1)$	Multiplication	$1$
  $(\Sigma^*, \cdot, \varepsilon)$	String concatenation	$\varepsilon$
  $(\text{Rel}(A, A), \circ, \text{id}_A)$	Relational composition	$\text{id}_A$
  $(\mathcal{P}(A), \cup, \emptyset)$	Union	$\emptyset$
  $(\mathcal{P}(A), \cap, A)$	Intersection	$A$

  Commutative Monoid

  A monoid is commutative (or abelian) if $x \bullet y = y \bullet x$ for all $x, y \in S$.

  Examples: $(\mathbb{N}, +, 0)$, $(\mathcal{P}(A), \cup, \emptyset)$.

  Non-example: $(\Sigma^*, \cdot, \varepsilon)$ is NOT commutative ($ab \neq ba$ in general).

  Examinable: Endo-Relations Form a Monoid

  Theorem: For any set $A$, the endo-relations $(\text{Rel}(A, A), \circ, \text{id}_A)$ form a monoid.

  Proof:

  • Closure: Composition of relations $R : A \nrightarrow A$ and $S : A \nrightarrow A$ yields $S \circ R : A \nrightarrow A$.
  • Associativity: Already proved: $(T \circ S) \circ R = T \circ (S \circ R)$.
  • Identity: $\text{id}_A \circ R = R = R \circ \text{id}_A$.

  ---

  Groups

  Definition

  A group is a monoid $(G, \bullet, e)$ where every element has an inverse.

  For each $x \in G$, there exists $x^{-1} \in G$ such that:

  $x \bullet x^{-1} = e = x^{-1} \bullet x$

  Examples

  Group	Operation	Identity	Inverse
  $(\mathbb{Z}, +, 0)$	Addition	$0$	$-x$
  $(\mathbb{Q} \setminus \{0\}, \times, 1)$	Multiplication	$1$	$1/x$
  $(\mathbb{Z}_n, +, 0)$ mod $n$	Addition mod $n$	$0$	$n - x$
  Symmetric group $S_n$	Permutation composition	Identity permutation	Inverse permutation

  Abelian Group

  A group is abelian if the operation is commutative.

  Key Property

  In a group, equations are always solvable: for any $a, b \in G$, there exists a unique $x$ with $a \bullet x = b$ (namely $x = a^{-1} \bullet b$).

  Non-examples

  • $(\mathbb{N}, +, 0)$ is NOT a group (no additive inverses)
  • $(\mathbb{Z}, \times, 1)$ is NOT a group (most elements lack multiplicative inverses)

  ---

  Semirings

  Definition

  A semiring is a structure $(S, 0, \oplus, 1, \otimes)$ where:

  1. $(S, 0, \oplus)$ is a commutative monoid (addition)
  2. $(S, 1, \otimes)$ is a monoid (multiplication)
  3. Distributivity: $x \otimes (y \oplus z) = (x \otimes y) \oplus (x \otimes z)$ and $(x \oplus y) \otimes z = (x \otimes z) \oplus (y \otimes z)$
  4. Annihilation: $0 \otimes x = 0 = x \otimes 0$

  Examples

  Semiring	Addition $\oplus$	Multiply $\otimes$	Zero	One
  $(\mathbb{N}, +, \times)$	$+$	$\times$	$0$	$1$
  Boolean semiring $\mathbb{B}$	$\lor$ (OR)	$\land$ (AND)	$0$	$1$
  Min-plus (tropical)	$\min$	$+$	$\infty$	$0$
  Max-plus	$\max$	$+$	$-\infty$	$0$

  The Boolean Semiring

  $\mathbb{B} = (\{0, 1\}, 0, \lor, 1, \land)$

  This is the foundation for:

  • Relational composition via matrix multiplication
  • Reachability in graphs

  The Min-Plus Semiring (Tropical)

  $(\mathbb{R} \cup \{\infty\}, \infty, \min, 0, +)$

  Applications:

  • Shortest path algorithms
  • Dynamic programming optimisation

  

  ---

  Rings

  Definition

  A ring is a semiring where $(S, 0, \oplus)$ is an abelian group.

  Every element has an additive inverse.

  Examples

  • $(\mathbb{Z}, +, \times)$: integers (additive inverse is negation)
  • $(\mathbb{Z}_n, +, \times)$: integers mod $n$
  • Polynomials over $\mathbb{Z}$

  Non-example

  $(\mathbb{N}, +, \times)$ is NOT a ring (no additive inverses).

  ---

  Fields

  Definition

  A field is a commutative ring where every non-zero element has a multiplicative inverse.

  $(F, 0, +, 1, \times)$ satisfies:

  1. $(F, 0, +)$ is an abelian group
  2. $(F \setminus \{0\}, 1, \times)$ is an abelian group
  3. Distributivity holds

  Examples

  • $\mathbb{Q}$: rational numbers
  • $\mathbb{R}$: real numbers
  • $\mathbb{C}$: complex numbers
  • $\mathbb{Z}_p$: integers mod $p$, where $p$ is prime

  Key Theorem

  Theorem: $\mathbb{Z}_p$ (integers mod $p$) is a field if and only if $p$ is prime.

  Proof:

  • If $p$ is prime and $a \not\equiv 0 \pmod{p}$, then $\gcd(a, p) = 1$.
  • By Bézout’s identity, $\exists x, y$ with $ax + py = 1$.
  • Thus $ax \equiv 1 \pmod{p}$, so $a$ has a multiplicative inverse.
  • If $p$ is composite, say $p = ab$ with $1 < a, b < p$, then $a, b$ are zero divisors and cannot have inverses.

  Why This Matters for Cryptography

  $\mathbb{Z}_p$ being a field is essential for:

  • Diffie-Hellman key exchange: relies on exponentiation in $\mathbb{Z}_p^*$
  • RSA: requires computing inverses mod $\varphi(n)$

  ---

  Summary Table

  Structure	Addition	Multiplication	Key Property
  Monoid	Associative + Identity	—	Minimal structure
  Group	Inverses exist	—	Equations solvable
  Semiring	Commutative monoid	Monoid	Matrix multiplication works
  Ring	Abelian group	Monoid	Can subtract
  Field	Abelian group	Abelian group (except 0)	Can divide

  ---

  Tripos Questions

  2016 P2 Q6: Prove that the set of all strings over alphabet $\{a, b\}$ under concatenation forms a monoid. Is it a group?

  2020 P2 Q9: Show that $\mathbb{Z}_p$ is a field when $p$ is prime. Explain why $a^{p-1} \equiv 1 \pmod{p}$ for $a \not\equiv 0 \pmod{p}$.

  ---

  Summary

  • Monoid: set + operation + identity + associativity
  • Group: monoid + inverses
  • Semiring: two operations, distributivity, additive identity annihilates
  • Ring: semiring + additive inverses
  • Field: ring + multiplicative inverses (except zero)
  • $\mathbb{Z}_p$ is a field iff $p$ is prime (foundational for cryptography)