Integer

The building blocks of discrete mathematics.

Simply put, an integer is a number with no fractional component. Integers can be positive, negative, or $0$. The set of all integers is symbolized by $\mathbb{Z}.$ Within the context of discrete math, integers are often referred to as "numbers."

Contents

Parity

All integers are either even or odd. This dichotomy, known as parity, can only be exhibited by integers.

An integer $n$ is even if and only if an integer $k$ exists such that:$$n=2k$$

For example, $8$ is even because it can be expressed in the form $8=2(4).$

An integer $n$ is odd if and only if an integer $k$ exists such that:$$n=2k+1$$

Likewise, $9$ is odd because it can be written as $9=2(4)+1.$

Two integers have the same parity if they are both even or both odd, and opposite parity if one is even while the other is odd.

Any two consecutive integers have opposite parity.

Divisibility

When an integer divides another integer, their division results in an integer with no remainder.

An integer $m$ divides an integer $n$ if and only if an integer $k$ exists such that:$$n=km$$

$3$ divides $15$ because $15=(5)(3).$

If $m$ divides $n$, this relation can be written as $m \mid n.$ Alternatively, if $m$ does not divide $n$, it's written as $m \nmid n.$

⚠ The notation $m \mid n$ can be confusing at first if you're used to seeing division as $m / n$, where $m$ is being divided by $n.$ It is important to clarify that the statement $m \mid n$ means that $n / m$ has no remainder. Make sure you clear up this confusion early on!

If $m \mid n$, then $m$ is a factor (or divisor) of $n$, and $n$ is an integer multiple of $m.$

Primality

Prime numbers (primes) are special numbers that have been studied for thousands of years. The only positive integers that can divide a prime are itself and $1.$

An integer $n$ is prime if and only if $n > 1$ and for every integer $m$ such that $1 < m < n$:$$m \nmid n$$

$7$ is prime because $7>1$ and $2$, $3$, $4$, $5$, and $6$ fail to divide it.

On the flipside, a composite number has a factor other than itself and $1.$

An integer $n$ is composite if and only if $n > 1$ and an integer $m$ exists, $1 < m < n$, such that:$$m \mid n$$

$6$ is composite because $6>1$ and $2$ divides it. You could also mention $3$ divides it, but just one example is needed.

⚠ Note that $1$ is neither prime nor composite.

⚠ As you might guess, primes are sort of rare. Many questions about primes are still left unanswered to this day.

Logic & Proofs

Integer • Rational number • Inequality • Real number • Theorem • Proof • Statement • Proof by exhaustion • Universal generalization • Counterexample • Existence proof • Existential instantiation • Axiom • Logic • Truth • Proposition • Compound proposition • Logical operation • Logical equivalence • Tautology • Contradiction • Logic law • Predicate • Domain • Quantifier • Argument • Rule of inference • Logical proof • Direct proof • Proof by contrapositive • Irrational number • Proof by contradiction • Proof by cases • Summation • Disjunctive normal form

Set Theory

Set • Element • Empty set • Universal set • Subset • Power set • Cartesian product • String • Binary string • Empty string • Set operation • Set identity • Set proof

Functions

Function • Floor function • Ceiling function • Inverse function

Algorithms

Algorithm • Pseudocode • Command • Asymptotic notation • Time complexity • Atomic operation • Brute-force algorithm

Relations

Relation • Reflexive relation • Symmetric relation • Transitive relation • Relation composition • Equivalence relation • Equivalence class

Number Theory

Integer division • Linear combination • Division algorithm • Modular arithmetic • Prime factorization • Greatest common divisor • Least common multiple • Primality test • Factoring algorithm • Euclid's theorem • Prime number theorem • Euclidean algorithm

Induction

Proof by induction • Fibonacci sequence • Proof by strong induction • Well-ordering principle • Sequence • Factorial • Recursive definition

Combinatorics

Rule of product • Rule of sum • Bijection rule • Permutation • Combination • Complement rule • Experiment • Outcome • Sample space • Event • Probability • Probability distribution • Uniform distribution • Multiset • Sixfold way • Inclusion-exclusion principle • Pigeonhole principle

Graph Theory

Graph • Walk • Subgraph • Regular graph • Complete graph • Empty graph • Cycle graph • Hypercube graph • Bipartite graph • Component • Eulerian circuit • Eulerian trail • Hamiltonian cycle • Hamiltonian path • Tree • Huffman tree • Substring • Forest • Path graph • Star • Spanning tree • Weighted graph • Minimum spanning tree • Greedy algorithm • Prim's algorithm

Recursion

Recursion • Recursive algorithm • Correctness proof • Divide-and-conquer algorithm • Sorting algorithm • Merge sort