Training Discrete Mathematics & Number Theory Modular Arithmetic and Graphs
4 / 5

Modular Arithmetic and Graphs

23 min Discrete Mathematics & Number Theory
Modular arithmetic studies remainders: a ≡ b (mod n) means n divides (a − b). Addition, subtraction, and multiplication work naturally mod n, but division requires finding modular inverses via the extended Euclidean algorithm. Applications include clock arithmetic, check digits (ISBN, credit cards), and the RSA cryptosystem. Graph theory models relationships as vertices connected by edges: adjacency, degrees, paths, cycles, and trees are the fundamental concepts. Euler paths traverse every edge exactly once; Hamiltonian paths visit every vertex exactly once. Graph coloring, planarity, and shortest-path algorithms (Dijkstra, BFS) round out the essentials.

Modular Arithmetic and Graphs

Modular arithmetic studies remainders. Graph theory studies networks of vertices and edges.

Congruence Modulo $n$

We write $$a \equiv b \pmod{n}$$ if $a$ and $b$ have the same remainder when divided by $n$.

Example 1

Compute $17 \bmod 5$.

  1. The remainder is $2$.
Example 2

Is $23 \equiv 5 \pmod 9$?

  1. Yes, both leave remainder $5$.
Graph Vocabulary

A graph has vertices (points) and edges (connections). The degree of a vertex is the number of edges touching it.

Practice Problems

1. Compute $14 \bmod 4$.
2. Compute $31 \bmod 6$.
3. What does $a \equiv b \pmod n$ mean?
4. What is a vertex?
5. What is the degree of a vertex?
Show Answer Key

1. $2$

2. $1$

3. They have the same remainder when divided by $n$

4. A node or point in a graph

5. The number of incident edges

🕐 Modular Arithmetic Calculator
a mod n
(a + b) mod n
(a × b) mod n
aᵇ mod n
Sequences, Recursion, and Induction Placement Test Practice — Other Math