4. Number Theory, Graphs
4.1 Sets, Relations, Functions, and Operations
A set is determined by its elements. The empty set is
Basic set operations:
| Operation | Definition |
|---|---|
| Union | |
| Intersection | |
| Difference | |
| Complement | If |
| Symmetric difference |
Useful identities include associativity and commutativity of
An ordered pair
Important relation properties:
| Property | Meaning |
|---|---|
| Reflexive | |
| Irreflexive | No |
| Symmetric | |
| Antisymmetric | |
| Transitive | |
| Dichotomous / total comparability | For any |
An equivalence relation is reflexive, symmetric, and transitive. It partitions a set into disjoint equivalence classes, and every partition defines an equivalence relation by putting elements in relation exactly when they belong to the same block.
A partial order is reflexive, antisymmetric, and transitive. If every two elements are comparable, it is a total order. In a partial order, the smallest element is below every element; a minimal element only has no strictly smaller element. Similarly, the largest element is above every element, while a maximal element has no strictly larger element. Bounds, infimum, and supremum describe lower and upper constraints on subsets.
A function is a relation that assigns at most one value to each input. For
Operations are functions with algebraic meaning:
| Operation type | Form |
|---|---|
| Nullary operation | Chooses an element of |
| Unary operation | |
| Binary operation |
A binary operation may be associative, commutative, have identity elements, have inverses, and distribute over another operation. A structure-preserving map between two sets with operations is a homomorphism: if
These ideas lead to algebraic structures. A set with a binary operation is a groupoid; associativity gives a semigroup; an identity gives a monoid; inverses give a group; a commutative group is Abelian. A ring combines additional Abelian-group structure with multiplication and distributivity. A field is a ring where every nonzero element has a multiplicative inverse.
What to Emphasize in an Oral Answer
- Start with sets: membership, subset, power set, and the basic operations union, intersection, difference, complement, and symmetric difference.
- Mention the main set identities, especially distributivity and De Morgan's laws.
- Define relations as subsets of Cartesian products and list the key relation properties: reflexive, symmetric, antisymmetric, transitive, and total comparability.
- Contrast equivalence relations with partial orders: equivalences partition into classes, while partial orders support comparisons, bounds, minimal/maximal, and smallest/largest elements.
- Define functions as single-valued relations and distinguish injective, surjective, and bijective maps.
- Explain operations as functions on a set, then connect associativity, identity, inverses, and distributivity to structures such as semigroups, monoids, groups, rings, and fields.
- Mention homomorphisms as maps preserving operations.
Suggested answer
The basic language of this topic starts with sets. A set is determined by its elements, so the central questions are membership, inclusion, and how sets are combined. The empty set has no elements, a subset contains only elements of another set, and the power set contains all subsets. The basic operations are union, intersection, difference, complement, and symmetric difference. Their algebraic laws, such as associativity, commutativity, distributivity, and De Morgan's laws, let us transform set expressions in the same way arithmetic laws let us transform numeric expressions.
Relations add structure between elements. A binary relation is a subset of a Cartesian product, so it consists of ordered pairs. On one set, the important properties are reflexivity, symmetry, antisymmetry, transitivity, and comparability. Equivalence relations are reflexive, symmetric, and transitive; they express "same type as" and divide the set into disjoint equivalence classes. Partial orders are reflexive, antisymmetric, and transitive; they express ordering where not every two elements must be comparable. If every pair is comparable, the partial order becomes a total order.
Functions are special relations: each input has at most one output. A function can be injective, meaning no two different inputs share one output; surjective, meaning every target element is reached; or bijective, meaning both. Bijections are especially important because they show two sets have the same size or the same structure.
Operations are functions that take elements of a set and produce elements of the same set. Unary operations take one argument, binary operations take two, and nullary operations can be viewed as choosing a distinguished element. Properties such as associativity, commutativity, identity, inverse, and distributivity determine the algebraic behavior of the operation. This is how we arrive at structures such as semigroups, monoids, groups, rings, integral domains, and fields. The point is that sets provide the universe of objects, relations describe comparisons or classifications among them, functions describe deterministic mappings, and operations provide the internal algebraic rules.
4.2 Complex Numbers
The complex numbers are defined as
and
The element
Core forms and operations:
| Concept | Formula |
|---|---|
| Real and imaginary parts | If |
| Conjugate | |
| Modulus | |
| Inverse | If |
| Product with conjugate |
Conjugation preserves addition and multiplication:
The modulus is multiplicative and satisfies the triangle inequality:
If
Arguments are not unique: adding
Multiplication and powers are simple in trigonometric form. If
then
and de Moivre's formula gives
The
Complex numbers form a field but not an ordered field compatible with multiplication, because
What to Emphasize in an Oral Answer
- Define
as with special multiplication, introduce , and note . - Explain algebraic form
, real/imaginary parts, conjugate, modulus, and inverse for . - State useful identities:
, conjugation respects addition/multiplication, and . - Give the geometric/trigonometric form
and note that arguments are defined modulo . - Explain multiplication, powers, and roots through moduli and arguments, including de Moivre's formula.
- Finish with the structural point:
is a field but not an ordered field compatible with multiplication.
Suggested answer
Complex numbers extend the real numbers so that equations such as
The algebraic form
Complex numbers also have a geometric interpretation as points or vectors in the plane. The modulus is the distance from the origin, and the argument is the angle with the positive real axis. In trigonometric form,
This leads to de Moivre's formula: raising a complex number to the
The complex numbers form a field, so addition, subtraction, multiplication, and division by nonzero elements all work. However, they cannot be ordered like the real numbers in a way compatible with field multiplication, because
4.3 Enumeration Problems
Enumeration studies finite sets by counting possible choices, arrangements, and mappings. Two finite sets have the same cardinality if there is a bijection between them. The pigeonhole principle says that if
Basic formulas:
| Problem | Meaning | Count |
|---|---|---|
| Permutation | Order all | |
| Variation without repetition | Ordered choice of | |
| Combination without repetition | Unordered choice of | |
| Permutation with repetitions | Arrange multiset counts | |
| Variation with repetition | Ordered length- | |
| Combination with repetition | Unordered choice of |
The binomial theorem is
The multinomial theorem generalizes it:
The inclusion-exclusion principle counts elements outside or inside unions by alternating intersections. For finite sets
What to Emphasize in an Oral Answer
- Frame enumeration as counting finite choices, arrangements, and mappings; mention cardinality through bijections.
- State the pigeonhole principle as the basic non-injectivity obstruction.
- Organize formulas by two questions: does order matter, and is repetition allowed?
- Give the no-repetition counts: permutations
, ordered variations , and combinations . - Give the repetition counts: ordered choices
, combinations with repetition , and multiset permutations . - Include binomial and multinomial theorem coefficients as counting choices from factors.
- Mention inclusion-exclusion for overlapping conditions, with alternating sums of intersections.
Suggested answer
Enumeration problems ask how many possibilities a finite construction has. The starting point is cardinality: finite sets have the same size when a bijection exists between them. The pigeonhole principle is the simplest counting obstruction. If more objects are assigned to fewer boxes, then at least two objects must share a box, so the assignment cannot be injective.
The main distinction in elementary enumeration is whether order matters and whether repetition is allowed. If we arrange all
When repetition is allowed, the formulas change. Ordered length-
Two important theorems organize these counts. The binomial theorem expands
4.4 Undirected Graphs, Trees, Eulerian and Hamiltonian Graphs
An undirected graph consists of a vertex set
Basic graph notions:
| Concept | Meaning |
|---|---|
| Isolated vertex | A vertex incident with no edge. |
| Loop | An edge whose two endpoints coincide. |
| Parallel edges | Distinct edges with the same endpoints. |
| Adjacent vertices | Vertices joined by an edge. |
| Degree | Number of incident edge ends at |
| Every vertex has degree | |
| Complete graph | Simple graph where every pair of distinct vertices is adjacent. |
| Bipartite graph | Vertices split into two disjoint parts and edges run only between the parts. |
| Complete bipartite graph | Every vertex in one part is joined to every vertex in the other. |
| Subgraph | Uses subsets of the original vertices and edges with inherited incidence. |
A walk is an alternating sequence of vertices and edges where each edge joins its neighboring vertices in the sequence. A trail has no repeated edge. A path has no repeated vertex. A graph is connected if every two vertices are joined by a path; the connected components are the equivalence classes of the reachability relation.
A tree is a connected acyclic graph. For a finite simple graph with
- It is a tree.
- It is connected and has
edges. - It is acyclic and has
edges. - Between every two distinct vertices there is exactly one path.
- Deleting any edge destroys connectedness.
- Adding any new edge creates a cycle.
A spanning tree of a graph
An Eulerian trail uses every edge exactly once. If it starts and ends at the same vertex, it is an Eulerian circuit. A connected finite undirected graph has an Eulerian circuit exactly when every vertex has even degree. A connected finite graph has an open Eulerian trail exactly when exactly two vertices have odd degree; those vertices are the start and end.
A Hamiltonian path visits every vertex exactly once. A Hamiltonian cycle returns to the starting vertex after visiting all vertices. Unlike the Eulerian condition, Hamiltonian graphs do not have one equally simple degree-parity characterization; Hamiltonian questions are generally harder because the restriction is on vertices rather than edges.
Also note planar graphs. A connected planar graph satisfies Euler's formula
Graph representations are usually adjacency lists or matrices. Lists are economical for sparse graphs; adjacency matrices are simple and efficient for dense graphs or constant-time adjacency tests.
What to Emphasize in an Oral Answer
- Define an undirected graph by vertices, edges, and incidence; in a simple graph, edges are unordered pairs with no loops or parallel edges.
- Cover local vocabulary: adjacency, degree, isolated vertices, regular, complete, bipartite, complete bipartite, and subgraph.
- Distinguish walks, trails, and paths, then define connectedness and connected components.
- State equivalent characterizations of finite trees: connected acyclic,
edges, unique path between vertices, edge deletion disconnects, edge addition creates a cycle. - Explain spanning trees as minimal connected backbones of connected graphs.
- Contrast Eulerian and Hamiltonian traversal: Eulerian uses every edge once and has a degree-parity criterion; Hamiltonian visits every vertex once and has no comparable simple test.
- Mention graph representations briefly: adjacency lists for sparse graphs, matrices for dense graphs or fast adjacency checks.
Suggested answer
An undirected graph is a structure made of vertices and edges, where each edge connects vertices without direction. In a simple graph there are no loops and no parallel edges, so each edge just joins two distinct vertices. Basic terminology describes local structure: adjacent vertices share an edge, the degree of a vertex is the number of incident edge ends, an isolated vertex has degree zero, and an
Movement through a graph is described by walks, trails, and paths. A walk may repeat vertices and edges. A trail may repeat vertices but not edges. A path repeats no vertex. Connectivity means every pair of vertices is joined by some path, and the connected components are the maximal connected pieces.
Trees are the most important special connected graphs. A tree is connected and acyclic. This definition has several equivalent forms for finite simple graphs: a tree with
Eulerian and Hamiltonian graphs ask for global traversals, but they ask for different things. An Eulerian trail uses every edge exactly once, and an Eulerian circuit returns to its starting vertex. In a connected finite undirected graph, an Eulerian circuit exists exactly when all vertices have even degree, because every time the traversal enters a vertex it must also leave it. If exactly two vertices have odd degree, an open Eulerian trail can start at one and end at the other.
A Hamiltonian path visits every vertex exactly once, and a Hamiltonian cycle returns to the starting vertex. This is a vertex-covering condition rather than an edge-covering condition. The contrast is important: Eulerian existence has a clean parity test, while Hamiltonian existence is much harder and does not have a simple universal characterization. In applications, adjacency lists and adjacency matrices are common representations; lists fit sparse graphs, while matrices fit dense graphs or fast adjacency lookup.
4.5 Divisibility, Congruence, and Primes
For integers,
for every integer . if and only if . for every integer . - Divisibility is reflexive and transitive.
- If
for several , then divides every integer linear combination .
The greatest common divisor
The Euclidean algorithm computes
An integer greater than
Congruence modulo
It is an equivalence relation on
Euler-Fermat theorem:
Fermat's little theorem is the prime-modulus special case:
A linear congruence
For two congruences
a common solution exists if and only if
What to Emphasize in an Oral Answer
- Define divisibility
and mention reflexivity, transitivity, and closure under integer linear combinations. - Define gcd, lcm, relative primality, and Bezout's identity from the extended Euclidean algorithm.
- Explain primes through divisors and the product-divisibility property; state unique prime factorization and the sieve idea.
- Define congruence modulo
by , residue classes, complete residue systems, reduced residue systems, and Euler's . - State Euler-Fermat and Fermat's little theorem as the key exponent results.
- Explain solvability of
: solutions exist exactly when . - Include the Chinese remainder theorem: compatibility for non-coprime moduli and unique solution modulo the product when moduli are pairwise coprime.
Suggested answer
Divisibility is the relation behind elementary number theory. We say that
The greatest common divisor of two integers is the common divisor that is divisible by all other common divisors. If the gcd is
Primes are the building blocks of the integers. A prime integer has no positive divisors except
Congruence modulo
Euler-Fermat's theorem states that if
4.6 Polynomials and Division With Remainder
Let
If
Polynomial operations:
| Operation | Rule |
|---|---|
| Addition | Add coefficients componentwise: |
| Negation/subtraction | Use additional inverses coefficientwise. |
| Multiplication | Convolution of coefficients: |
If
Division with remainder: if
Over a field this works for every nonzero divisor polynomial
Horner's scheme evaluates
by rewriting it as
This reduces the number of multiplications and also supports testing whether
What to Emphasize in an Oral Answer
- Define a polynomial over a ring
as a finite formal sum and identify leading coefficient and degree. - State how
operations work: coefficientwise addition and convolution-style multiplication. - Mention inherited structure: commutativity or a multiplicative identity in
carries to when applicable. - Explain division with remainder
, , and the condition needed: the leading coefficient of is invertible; over fields every nonzero divisor works. - State uniqueness of quotient and remainder under the division hypotheses.
- Present Horner's scheme as efficient nested evaluation and connect it to the remainder theorem/root test for division by
.
Suggested answer
A polynomial over a ring
Polynomials form a ring
Division with remainder generalizes integer division. Given polynomials
Horner's scheme is a practical consequence of polynomial structure. Instead of evaluating
4.7 Additional Material: Coding Theory
Coding theory is included here as related material for number theory, graphs, and discrete mathematics.
Letter-by-Letter Encoding
Encoding maps messages into another set of messages, usually over a different alphabet. If messages are words over an alphabet
This mapping extends to whole words by concatenation:
For decoding to be unambiguous, the extended mapping
Word terminology:
| Term | Meaning |
|---|---|
| Nonempty words over alphabet | |
| All words over | |
| Prefix | A beginning part of a word. |
| Infix | A contiguous middle part of a word. |
| Suffix | An ending part of a word. |
| Prefix code | No code word is a prefix of another code word. |
| Uniform code | All code words have the same length. |
| Comma code | A special comma word terminates code words and appears neither as prefix nor infix of code words. |
A code tree represents code words as root-to-vertex paths labelled by alphabet symbols. Prefix-free codes correspond to choosing code words at vertices none of which is an ancestor of another chosen code-word vertex.
Frequency, Information, Entropy, and Average Length
If a source emits
is the relative frequency. The distribution is
The information content of symbol
where
Entropy is the average information content:
If code word
An optimal uniquely decodable code minimizes average word length for the given alphabet size and source distribution.
Shannon Code
A Shannon-code construction for an
- Sort source letters by decreasing relative frequency.
- Choose code lengths
such that
- Assign code words in lexicographic tree order with those lengths.
For the example with code alphabet
| Letter | Frequency | Shannon length | Shannon code |
|---|---|---|---|
| f | 0.31 | 2 | 00 |
| a | 0.17 | 2 | 01 |
| h | 0.17 | 2 | 02 |
| c | 0.13 | 2 | 10 |
| j | 0.09 | 3 | 110 |
| i | 0.06 | 3 | 111 |
| b | 0.02 | 4 | 1120 |
| d | 0.02 | 4 | 1121 |
| g | 0.02 | 4 | 1122 |
| e | 0.01 | 5 | 12000 |
The original tree image is represented by the table: each code is the path label from the root to the leaf for that symbol.
Huffman Code
Huffman coding builds an optimal prefix code by repeatedly merging least frequent symbols.
For an
symbols. After that, each reduction merges the
The ternary Huffman example has final code table:
| Letter | Frequency | Huffman code |
|---|---|---|
| f | 0.31 | 1 |
| a | 0.17 | 00 |
| h | 0.17 | 01 |
| c | 0.13 | 02 |
| j | 0.09 | 20 |
| i | 0.06 | 22 |
| b | 0.02 | 211 |
| d | 0.02 | 212 |
| g | 0.02 | 2100 |
| e | 0.01 | 2101 |
The original Huffman tree image is replaced by the reduction description plus this code table. The important mechanism is that frequent symbols get short paths and rare symbols get longer paths.
Error-Control Codes and Hamming Distance
Error-control codes add redundancy so that transmission errors can be detected or corrected. Error-detecting codes report that something went wrong; error-correcting codes choose a likely original code word. For error-control codes, code words usually have a fixed length.
For words
; exactly when ; ; .
The minimum distance of a code
If the alphabet is an Abelian group with zero, the Hamming weight
A code corrects all errors of size at most
errors.
The Hamming bound for a
If equality holds, the code is perfect.
Linear Codes, Polynomial Codes, and CRC
Over a finite field
Polynomial coding represents a message vector
Choosing a fixed monic polynomial
The resulting code length is
A cyclic code is a polynomial code where
The transmitted polynomial is divisible by
What to Emphasize in an Oral Answer
- Frame coding theory around three goals: representation, compression/short average length, and error detection or correction.
- For letter-by-letter codes, explain extension by concatenation and the need for injectivity of the extended map for unique decoding.
- Mention prefix codes and code trees as the clean practical way to decode unambiguously.
- Define information content, entropy, and average code-word length; stress that frequent symbols should get shorter code words.
- Contrast Shannon coding with Huffman coding: Shannon uses probability-based lengths, while Huffman constructs an optimal prefix code by merging least frequent symbols.
- Explain Hamming distance, minimum distance, and correction capability
; mention the Hamming bound. - Describe linear codes as subspaces
with generator matrices, and polynomial/cyclic codes including CRC as mainly error-detecting.
Suggested answer
Coding theory studies how messages can be represented so that they are compact, uniquely decodable, or robust against errors. In letter-by-letter encoding, each source symbol from an alphabet
The efficiency of a code depends on the source distribution. If symbol
Coding theory also handles transmission errors. For fixed-length code words, the Hamming distance counts how many positions differ. The minimum distance of a code determines its error-control ability: a code with distance
Linear codes use algebraic structure. Over a finite field, a linear code is a subspace of
