Chapter 6 — Front Matter

Purpose and Overview

This chapter introduces the mathematical structure of the integers: how numbers divide each other, what makes a number prime, how the greatest common divisor connects to algorithms, and how remainders give rise to a complete and self-consistent number system called modular arithmetic. These ideas belong to a branch of mathematics called number theory, and they form the backbone of modern computing, digital security, error detection, and cryptography.

Number theory does not require calculus. It rests on careful reasoning about whole numbers: how they factor, how they divide, how they relate to each other through division and remainder, and how that remainder structure can be used to build systems that work in cycles. By the end of this chapter, students will understand not just how to compute with modular arithmetic, but why it works and where it is used.

Opening Question

Suppose two friends want to agree on a shared secret number to use in a message. They want to communicate over a public channel, where anyone can see what they send. Is there a mathematical method that lets them arrive at the same secret number without ever directly revealing it, even if an observer watches every message they exchange?

The answer is yes — and the mathematics behind it is built almost entirely from the ideas in this chapter: prime numbers, greatest common divisors, and modular arithmetic. The protocol that makes this possible is called Diffie-Hellman key exchange. You will see the mathematical ideas that make it work by the end of this chapter.

14Sections

11Objectives

18Key Terms

12+Worked Examples

Why This Chapter Matters

When a student first learns about division, they learn it as a way to split numbers evenly. But integers have a far richer structure than simple division suggests. The way numbers factor, the special role of primes, the patterns that arise from remainders, and the algorithms used to find common divisors are not just arithmetic curiosities. They are the foundations of cryptography, hashing, checksums, cyclic systems, and algorithm design. This chapter gives students those tools in their most fundamental form.

Learning Objectives

1Define divisibility and apply the definition to prove and disprove divisibility claims.
2Identify prime and composite numbers and explain the Fundamental Theorem of Arithmetic.
3Compute the greatest common divisor and least common multiple of integers.
4Apply the Euclidean Algorithm to find the GCD of large integers efficiently.
5State and apply Bézout's Identity as an introductory result.
6Define congruence modulo n and interpret congruence as an equivalence relation.
7Perform modular addition, subtraction, and multiplication.
8Compute modular exponentiation using repeated squaring as an introduction.
9Solve simple modular equations.
10Apply modular arithmetic to clocks, checksums, hashing, and cryptographic ideas.
11Identify and avoid common modular arithmetic mistakes.

Chapter 6 — Contents

Sections at a Glance

6.1Integers in Discrete MathematicsThe role of integers; discrete vs. continuous; integers as separate objects; why integer structure matters
6.2DivisibilityDefinition of divisibility; divisors and multiples; properties of divisibility; the Division Algorithm; direct proofs
6.3Prime and Composite NumbersPrimes and composites; Fundamental Theorem of Arithmetic; prime factorization; infinitely many primes
6.4Greatest Common DivisorDefinition of GCD; computing by prime factorization; coprime integers; applications
6.5Least Common Multiple ReviewDefinition of LCM; computing from factorizations; the GCD-LCM product formula
6.6The Euclidean AlgorithmKey lemma; repeated division procedure; efficiency; worked examples; why it matters
6.7Bézout's Identity: An IntroductionLinear combinations; back-substitution; Bézout coefficients; importance for modular inverses
6.8Congruence Modulo nDefinition of congruence; equivalence relation; residue classes; notation and meaning
6.9Modular Addition and MultiplicationArithmetic of congruences; addition tables; consistency of modular systems
6.10Modular Exponentiation: An IntroductionRepeated squaring; computing large powers efficiently; cryptographic relevance
6.11Solving Simple Modular EquationsWhen solutions exist; modular inverse; solving ax ≡ b (mod n); examples
6.12Modular Arithmetic in Clocks, Codes, and ComputingClock arithmetic; checksums; ISBN-13; hashing; cryptographic preview
6.13Common Modular Arithmetic MistakesSix recurring errors; treating ≡ as =; cancellation; negative remainders; missing inverses
6.14Preparing for Cryptography and AlgorithmsSummary of tools; connections to Chapter 12, cryptography, hashing, and data structures

Section 6.1

Integers in Discrete Mathematics

The integers are the numbers …, −3, −2, −1, 0, 1, 2, 3, …, denoted by the symbol ℤ. They include all positive whole numbers, all negative whole numbers, and zero.

Discrete mathematics is largely the mathematics of integers and finite structures. Integers show up everywhere in discrete reasoning: counting outcomes, indexing lists and arrays, labeling vertices in graphs, measuring algorithm steps, and controlling repeating patterns. Each integer is a separate object, and the relationships between integers — which ones divide which, which ones share common factors, which ones are equivalent in a given modular system — are precisely the kind of structural questions that discrete mathematics studies.

Section 6.2

Divisibility

Definition — Divisibility

Let a and b be integers with b ≠ 0. We say that b divides a, written b | a, if there exists an integer k such that a = b · k. If b divides a, we call b a divisor (or factor) of a, and we call a a multiple of b. If no such integer k exists, we write b ∤ a.

Important Distinction

The statement "b divides a" is not the same as computing a ÷ b. It is a claim about existence: there must be some integer k that makes the equation a = bk true. The key word in the definition is "exists."

Example 6.2.1

Checking Divisibility

ProblemDetermine whether 6 | 42 and whether 6 | 45.
ThinkTo check whether 6 | 42, find an integer k such that 42 = 6k. To check 6 | 45, find an integer k such that 45 = 6k.
Solve 6 | 42: Set 42 = 6k → k = 7. Since 7 is an integer, 6 | 42. ✓ 6 | 45: Set 45 = 6k → k = 7.5. Since 7.5 is not an integer, 6 ∤ 45. ✗
Check6 × 7 = 42 ✓. And 6 × 7 = 42 ≠ 45 while 6 × 8 = 48 ≠ 45, so no integer multiple of 6 equals 45 ✓.

Answer: 6 | 42 is true. 6 | 45 is false.

Properties of Divisibility

Theorem 6.2.1 — Properties of Divisibility

Let a, b, c be integers.

1. If a | b and a | c, then a | (b + c).

2. If a | b and a | c, then a | (b − c).

3. If a | b, then a | bc for any integer c.

4. If a | b and b | c, then a | c. (Transitivity)

Example 6.2.2 — Proof

Proving Property 1: If a | b and a | c, then a | (b + c)

Claim. If a | b and a | c, then a | (b + c).

Think. This is a direct proof. Start from the definitions of the two hypotheses and show the conclusion follows algebraically.

Proof. Assume a | b and a | c. By definition, there exist integers j and k such that b = aj and c = ak. Adding these two equations:

b + c = aj + ak = a(j + k)

Since j + k is an integer (the integers are closed under addition), we have expressed b + c as a times an integer. Therefore, a | (b + c).

□

The Division Algorithm

Theorem 6.2.2 — Division Algorithm

Let a be an integer and b be a positive integer. There exist unique integers q and r such that a = bq + r and 0 ≤ r < b. Here q is the quotient and r is the remainder.

Student Note

The Division Algorithm is a theorem, not a procedure. It guarantees that the quotient and remainder exist and are unique. The actual computation is done by ordinary long division. The remainder r is always in the range 0 ≤ r < b — this constraint is essential and becomes the foundation of modular arithmetic.

Practice 6.2Divisibility

Determine whether each statement is true or false. Justify your answer using the definition.
1. 7 | 49
2. 6 | 50
3. 12 | 144
4. 5 | 0
5. 0 | 5
6. 1 | n for every integer n
Prove that if a | b, then a | bc for any integer c.
Prove or disprove: if a | bc, then a | b or a | c. (Try a counterexample first.)

Section 6.3

Prime and Composite Numbers

Definition — Prime and Composite

An integer p > 1 is prime if its only positive divisors are 1 and itself. An integer n > 1 that is not prime is composite. By convention, 1 is neither prime nor composite.

The first several primes are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, …

The number 2 is the smallest prime and the only even prime.

Theorem 6.3.1 — Fundamental Theorem of Arithmetic

Every integer n > 1 can be written as a product of prime numbers, and this factorization is unique up to the order of the factors.

Example 6.3.1

Finding a Prime Factorization

ProblemFind the prime factorization of 360.
ThinkDivide by the smallest prime repeatedly until the result is 1.
Solve 360 ÷ 2 = 180 180 ÷ 2 = 90 90 ÷ 2 = 45 45 ÷ 3 = 15 15 ÷ 3 = 5 5 ÷ 5 = 1
Check2³ × 3² × 5 = 8 × 9 × 5 = 8 × 45 = 360 ✓

Answer: 360 = 2³ × 3² × 5

Testing for Primality

To determine whether n is prime, check whether any prime p ≤ √n divides n. If none does, then n is prime. For example, to test 97: check primes up to √97 ≈ 9.8. The primes to check are 2, 3, 5, 7. None divides 97, so 97 is prime. No calculus is needed — only ordinary square roots as estimates.

Theorem 6.3.2 — Proof

There are infinitely many prime numbers

Think. Use proof by contradiction (Chapter 4). Assume there are only finitely many primes, list them, form a special number, and show this forces a prime not on the list.

Proof. Suppose for contradiction that there are only finitely many primes, listed as p₁, p₂, …, pₖ. Consider the number N = p₁ · p₂ · ··· · pₖ + 1. By the Fundamental Theorem of Arithmetic, N has at least one prime factor; call it q. If q = pᵢ for some i, then q divides p₁p₂···pₖ, and q divides N, so q divides their difference N − p₁p₂···pₖ = 1. No prime divides 1, contradiction. Therefore q is a prime not on our list, contradicting the assumption that the list was complete.

□ Therefore, there are infinitely many prime numbers.

Practice 6.3Primes and Factorization

Is 91 prime? Show reasoning.
Is 97 prime? Show reasoning.
Is 111 prime? Show reasoning.
Is 127 prime? Show reasoning.
Factor 180 completely.
Factor 504 completely.
Factor 1000 completely.
Factor 2310 completely.

Section 6.4

Greatest Common Divisor

Definition — GCD

Let a and b be integers, not both zero. The greatest common divisor of a and b, written gcd(a, b), is the largest positive integer that divides both a and b. When gcd(a, b) = 1, we say a and b are coprime (or relatively prime).

Example 6.4.1

Computing GCD by Factoring

ProblemFind gcd(36, 60).
ThinkFind the prime factorization of each number and take the smallest power of each shared prime.
Solve 36 = 2² × 3² 60 = 2² × 3 × 5 Shared primes: 2 and 3. Smallest power of 2: 2² = 4 Smallest power of 3: 3¹ = 3 (Factor 5 appears only in 60) gcd(36, 60) = 2² × 3 = 4 × 3 = 12
Check36 = 12 × 3 ✓. 60 = 12 × 5 ✓. Is 18 a common divisor? 18 ∤ 60. So 12 is the greatest. ✓

Answer: gcd(36, 60) = 12

Section 6.5

Least Common Multiple Review

Definition — LCM

The least common multiple of positive integers a and b, written lcm(a, b), is the smallest positive integer divisible by both a and b. To compute from prime factorizations, take the highest power of each prime appearing in either factorization.

GCD-LCM Product Formula

gcd(a, b) × lcm(a, b) = a × b

This formula lets you find the LCM quickly once you know the GCD, and vice versa.

Example: gcd(36, 60) = 12, so lcm(36, 60) = (36 × 60) / 12 = 2160 / 12 = 180. Verify: 12 × 180 = 2160 = 36 × 60. ✓

Practice 6.4 – 6.5GCD and LCM

gcd(48, 18)
gcd(100, 75)
lcm(48, 18)
lcm(100, 75)
gcd(84, 36)
lcm(84, 36)
gcd(35, 14)
Are 15 and 28 coprime?

Section 6.6

The Euclidean Algorithm

Finding the prime factorization of large numbers is computationally expensive. The Euclidean Algorithm gives a faster method for computing GCDs without factoring. It is based on a single key observation:

Lemma 6.6.1 — Key Lemma

If a = bq + r, then gcd(a, b) = gcd(b, r).

The GCD of two numbers equals the GCD of the smaller number and the remainder when the larger is divided by the smaller. We can replace the pair (a, b) with (b, r) until the remainder is 0.

Euclidean Algorithm — Procedure

Given positive integers a ≥ b:

1. Divide a by b. Write a = bq + r.

2. If r = 0, then gcd(a, b) = b. Stop.

3. Replace a with b and b with r. Return to step 1.

Example 6.6.1

Euclidean Algorithm

ProblemFind gcd(252, 198) using the Euclidean Algorithm.
ThinkApply the Division Algorithm repeatedly, replacing the pair (a, b) with (b, r) at each step.
Solve Step 1: 252 = 198 × 1 + 54 → gcd(252, 198) = gcd(198, 54) Step 2: 198 = 54 × 3 + 36 → gcd(198, 54) = gcd( 54, 36) Step 3: 54 = 36 × 1 + 18 → gcd( 54, 36) = gcd( 36, 18) Step 4: 36 = 18 × 2 + 0 → gcd( 36, 18) = 18
Check252 = 18 × 14 ✓. 198 = 18 × 11 ✓. Prime factorizations: 252 = 2² × 3² × 7, 198 = 2 × 3² × 11. GCD = 2 × 3² = 18 ✓.

Answer: gcd(252, 198) = 18

Why the Euclidean Algorithm Matters

The algorithm runs in a number of steps proportional to the number of digits in the inputs — far faster than factoring. For two 100-digit numbers, factoring might take longer than the age of the universe, while the Euclidean Algorithm finishes in milliseconds. This efficiency makes it practical in cryptographic systems that work with very large numbers.

MGU Library Connection

The efficiency of the Euclidean Algorithm will be revisited in Chapter 12, Algorithms and Complexity, where running time is analyzed using Big-O notation.
Appendix H: Divisibility and Modular Arithmetic Reference — quick reference for all results in this chapter.

Section 6.7

Bézout's Identity: An Introduction

The Euclidean Algorithm does more than find the GCD. It can be used to express the GCD as a linear combination of the original two numbers — a sum of multiples of those numbers, possibly with negative coefficients.

Theorem 6.7.1 — Bézout's Identity

If a and b are integers, not both zero, then there exist integers s and t such that gcd(a, b) = sa + tb. The integers s and t are called Bézout coefficients. They are found by working the Euclidean Algorithm in reverse, a process called back-substitution.

Example 6.7.1

Finding Bézout Coefficients by Back-Substitution

ProblemExpress gcd(252, 198) = 18 as a linear combination of 252 and 198.
ThinkWork through the Euclidean Algorithm steps in Example 6.6.1, then substitute backwards to express each remainder in terms of 252 and 198.
Solve From Example 6.6.1: 252 = 198 × 1 + 54 → 54 = 252 − 198 × 1 198 = 54 × 3 + 36 → 36 = 198 − 54 × 3 54 = 36 × 1 + 18 → 18 = 54 − 36 × 1 Back-substitute: Step 1: 18 = 54 − 36 × 1 Step 2: Replace 36 = 198 − 54 × 3: 18 = 54 − (198 − 54 × 3) × 1 = 54 − 198 + 54 × 3 = 4 × 54 − 198 Step 3: Replace 54 = 252 − 198 × 1: 18 = 4 × (252 − 198 × 1) − 198 = 4 × 252 − 4 × 198 − 198 = 4 × 252 − 5 × 198
Check4 × 252 − 5 × 198 = 1008 − 990 = 18 ✓. And gcd(252, 198) = 18 ✓.

Answer: 18 = 4 × 252 + (−5) × 198. Bézout coefficients: s = 4, t = −5.

Why Bézout's Identity Matters

This result is essential in modular arithmetic. When we want to find a "modular inverse" — an integer that acts like a reciprocal in a modular system — Bézout's Identity gives us the tool to compute it. This is a core step in RSA encryption and other cryptographic methods studied in later courses.

Practice 6.6 – 6.7Euclidean Algorithm and Bézout Coefficients

Use the Euclidean Algorithm to find each GCD.
1. gcd(48, 18)
2. gcd(100, 75)
3. gcd(391, 299)
4. gcd(1001, 143)
Express each GCD as a linear combination of the original two numbers using back-substitution.
1. gcd(48, 18): write d = 48s + 18t
2. gcd(100, 75): write d = 100s + 75t
Prove the key lemma used in the Euclidean Algorithm: if a = bq + r, then gcd(a, b) = gcd(b, r).

Section 6.8

Congruence Modulo n

Definition — Congruence

Let n be a positive integer called the modulus. We say that a is congruent to b modulo n, written a ≡ b (mod n), if n divides a − b. Equivalently, a ≡ b (mod n) if and only if a and b have the same remainder when divided by n.

Example 6.8.1

Checking Congruence

ProblemDetermine whether 17 ≡ 5 (mod 4) and whether 23 ≡ 9 (mod 7).
ThinkCheck whether n divides the difference a − b.
Solve 17 ≡ 5 (mod 4): 17 − 5 = 12. Does 4 | 12? 12 = 4 × 3. ✓ Yes. 23 ≡ 9 (mod 7): 23 − 9 = 14. Does 7 | 14? 14 = 7 × 2. ✓ Yes.

Answer: Both congruences are true.

Congruence as an Equivalence Relation

Congruence modulo n is an equivalence relation on the integers. It satisfies reflexivity (a ≡ a), symmetry (if a ≡ b then b ≡ a), and transitivity (if a ≡ b and b ≡ c then a ≡ c). This groups integers into congruence classes — sets of integers sharing the same remainder when divided by n.

For n = 5, every integer belongs to one of exactly five equivalence classes:

Class	Representative	Elements (sample)
[0]₅	0	…, −10, −5, 0, 5, 10, 15, …
[1]₅	1	…, −9, −4, 1, 6, 11, 16, …
[2]₅	2	…, −8, −3, 2, 7, 12, 17, …
[3]₅	3	…, −7, −2, 3, 8, 13, 18, …
[4]₅	4	…, −6, −1, 4, 9, 14, 19, …

Residues

Every integer has a unique representative in the range {0, 1, 2, …, n − 1} when working modulo n. This representative is called the residue of the integer modulo n. When we reduce an integer modulo n, we find its residue.

Section 6.9

Modular Addition and Multiplication

Theorem 6.9.1 — Arithmetic of Congruences

If a ≡ b (mod n) and c ≡ d (mod n), then:

a + c ≡ b + d (mod n)

a − c ≡ b − d (mod n)

a × c ≡ b × d (mod n)

These rules say that operations can be performed before or after reducing modulo n, and the result is the same. Modular arithmetic is a complete, self-consistent system.

Example 6.9.1

Modular Addition

ProblemCompute (27 + 43) mod 8.
ThinkEither compute the sum first and reduce, or reduce each term first and then add.
Solve Method 1: 27 + 43 = 70. 70 = 8 × 8 + 6. So 70 ≡ 6 (mod 8). Method 2: 27 ≡ 3 (mod 8), 43 ≡ 3 (mod 8). 3 + 3 = 6 ≡ 6 (mod 8).

Answer: (27 + 43) ≡ 6 (mod 8)

Example 6.9.2

Modular Multiplication

ProblemCompute (17 × 23) mod 6.
ThinkReduce each factor modulo 6 first, then multiply and reduce again.
Solve 17 = 6 × 2 + 5, so 17 ≡ 5 (mod 6) 23 = 6 × 3 + 5, so 23 ≡ 5 (mod 6) 5 × 5 = 25 = 6 × 4 + 1, so 25 ≡ 1 (mod 6)
Check17 × 23 = 391. 391 = 6 × 65 + 1. So 391 ≡ 1 (mod 6). ✓

Answer: (17 × 23) ≡ 1 (mod 6)

Addition Table for ℤ₅

The table below shows that modular systems are closed: all sums wrap back into the set {0, 1, 2, 3, 4}.

+	0	1	2	3	4
0	0	1	2	3	4
1	1	2	3	4	0
2	2	3	4	0	1
3	3	4	0	1	2
4	4	0	1	2	3

Practice 6.8 – 6.9Congruence and Modular Arithmetic

25 ≡ 7 (mod 9)?
100 ≡ 3 (mod 7)?
−4 ≡ 8 (mod 6)?
0 ≡ 12 (mod 4)?
(38 + 57) mod 10
(83 − 47) mod 12
(15 × 17) mod 8
(99 × 99) mod 7

Section 6.10

Modular Exponentiation: An Introduction

In cryptography, it is common to compute large powers modulo a number — for example, 3¹⁰⁰ mod 7. Even though 3¹⁰⁰ is astronomically large, we do not need to compute it directly. We use the fact that intermediate results can be reduced modulo n at each step. A method called repeated squaring makes these computations efficient.

Repeated Squaring Strategy

To compute aᵉ (mod n):

1. Write e in binary.

2. Compute successive squares of a modulo n, reducing at each step.

3. Multiply together only the squares corresponding to 1-bits in the binary expansion of e.

This requires at most about 2 log₂ e multiplications — vastly better than the naïve e − 1 multiplications.

Example 6.10.1

Modular Exponentiation by Repeated Squaring

ProblemCompute 3¹³ (mod 7).
ThinkWrite 13 in binary: 13 = 8 + 4 + 1 = 1101₂. Compute successive squares of 3 modulo 7, then multiply the squares at positions 8, 4, and 1.
Solve 3¹ ≡ 3 (mod 7) 3² ≡ 9 ≡ 2 (mod 7) 3⁴ ≡ (3²)² ≡ 2² = 4 (mod 7) 3⁸ ≡ (3⁴)² ≡ 4² = 16 ≡ 2 (mod 7) Since 13 = 8 + 4 + 1: 3¹³ = 3⁸ × 3⁴ × 3¹ ≡ 2 × 4 × 3 = 24 ≡ 3 (mod 7)
Check3¹³ = 1,594,323. Then 1,594,323 ÷ 7 = 227,760 remainder 3. So 3¹³ ≡ 3 (mod 7). ✓

Answer: 3¹³ ≡ 3 (mod 7)

Why This Matters in Cryptography

Modular exponentiation is the computational engine behind RSA encryption and Diffie-Hellman key exchange. The same operation that seems like a curiosity with small numbers becomes a powerful security primitive when performed with numbers that have hundreds of digits. Repeated squaring keeps these computations manageable.

Section 6.11

Solving Simple Modular Equations

A modular equation has the form ax ≡ b (mod n), where a, b, and n are known integers and x is the unknown. The key question is: when does a solution exist, and how do we find it?

Theorem 6.11.1 — Existence of Solutions

The equation ax ≡ b (mod n) has a solution if and only if gcd(a, n) | b. When gcd(a, n) = 1, the equation has exactly one solution modulo n. In this case, a has a modular inverse — an integer a⁻¹ such that a · a⁻¹ ≡ 1 (mod n), found using Bézout's Identity.

Example 6.11.1

Finding a Modular Inverse

ProblemFind the modular inverse of 3 modulo 7. That is, find x such that 3x ≡ 1 (mod 7).
ThinkSince gcd(3, 7) = 1, the inverse exists. Use Bézout's Identity: write 1 = 3s + 7t, and s is the inverse modulo 7.
Solve Euclidean Algorithm: 7 = 3 × 2 + 1 Back-substitution: 1 = 7 − 3 × 2 = (−2) × 3 + 1 × 7 Bézout coefficient for 3 is −2. Reduce: −2 ≡ 5 (mod 7)
Check3 × 5 = 15 = 7 × 2 + 1. So 3 × 5 ≡ 1 (mod 7). ✓

Answer: The modular inverse of 3 modulo 7 is 5.

Example 6.11.2

Solving a Modular Equation

ProblemSolve 3x ≡ 4 (mod 7).
ThinkMultiply both sides by the modular inverse of 3 modulo 7, which is 5.
Solve 5 × 3x ≡ 5 × 4 (mod 7) 15x ≡ 20 (mod 7) x ≡ 6 (mod 7) [since 15 ≡ 1 and 20 ≡ 6]
Check3 × 6 = 18 = 7 × 2 + 4. So 3 × 6 ≡ 4 (mod 7). ✓

Answer: x ≡ 6 (mod 7)

Section 6.12

Modular Arithmetic in Clocks, Codes, and Computing

Clocks and Cyclic Systems

A clock is the most natural model of modular arithmetic. On a 12-hour clock, if it is 10:00 and we add 5 hours, we get 3:00, not 15:00. The calculation is 10 + 5 = 15 ≡ 3 (mod 12). The same reasoning applies to days of the week (modulus 7), months (modulus 12), and any periodic system.

Example 6.12.1

Day of the Week

ProblemToday is Wednesday (day 3, with Sunday = 0). What day will it be 100 days from now?
Solve 3 + 100 = 103. 103 = 7 × 14 + 5. 103 ≡ 5 (mod 7). Day 5 = Friday (Sun=0, Mon=1, Tue=2, Wed=3, Thu=4, Fri=5)

Answer: 100 days from Wednesday is Friday.

Checksums and Error Detection

Modular arithmetic is used to detect errors in transmitted data. The ISBN-13 system computes a check digit using an alternating weighted sum. Given the first 12 digits d₁, d₂, …, d₁₂, the check digit d₁₃ satisfies:

(d₁ + 3d₂ + d₃ + 3d₄ + ··· + d₁₁ + 3d₁₂ + d₁₃) ≡ 0 (mod 10)

If even one digit is changed or misread, the sum will almost certainly not be divisible by 10, and the error is detected.

Example 6.12.2

Checking an ISBN-13

ProblemVerify that the ISBN-13 number 9780306406157 is valid.
ThinkCompute the alternating weighted sum of all 13 digits with weights 1, 3, 1, 3, … and check divisibility by 10.
Solve Digits: 9 7 8 0 3 0 6 4 0 6 1 5 7 Weights: 1 3 1 3 1 3 1 3 1 3 1 3 1 Products: 9+21+8+0+3+0+6+12+0+18+1+15+7 = 100 100 ≡ 0 (mod 10) ✓

Answer: The ISBN-13 is valid.

Hashing in Computer Science

A hash function maps data of arbitrary size to a fixed-size output. One simple family uses modular arithmetic: given a value k and a hash table with m slots, the hash is k mod m. This distributes keys across storage locations. For example, if a database has 1000 slots, a record with key 7,492,381 would be stored at slot 7,492,381 mod 1000 = 381.

MGU Library Connection

A full treatment of RSA encryption and Diffie-Hellman key exchange appears in the MGU Cryptography course. The number theory in this chapter is the required mathematical foundation.
Hash functions and their properties are studied in detail in Data Structures and Algorithms courses.
Appendix O: Boolean Algebra and Logic Gate Reference — see also Appendix H for modular arithmetic formulas.

Practice 6.10 – 6.12Exponentiation, Equations, and Applications

Compute each using repeated squaring.
1. 2¹⁰ (mod 7)
2. 5⁸ (mod 13)
3. 3²⁰ (mod 11)
Find the modular inverse of each value, or state that it does not exist.
1. 5⁻¹ (mod 11)
2. 4⁻¹ (mod 9)
3. 6⁻¹ (mod 9)
Solve each modular equation.
1. 3x ≡ 2 (mod 5)
2. 7x ≡ 3 (mod 11)
3. 4x ≡ 2 (mod 6)
Today is Monday. What day of the week will it be 100 days from now? 365 days from now?
A hash table has 37 slots. Using h(k) = k mod 37, find the slot for k = 1000, k = 5923, and k = 73.

Section 6.13

Common Modular Arithmetic Mistakes

Mistake 1 — Treating ≡ as =

"Since 17 ≡ 5 (mod 4), we have 17 = 5."

Correct: The congruence symbol ≡ does not mean "is equal to." It means "is equivalent modulo n." The numbers 17 and 5 are not equal; they simply have the same remainder when divided by 4. There are infinitely many integers congruent to any given residue.

Mistake 2 — Forgetting to State the Modulus

"17 ≡ 5" (written without modulus)

Correct: Congruence is always relative to a specific modulus. "17 ≡ 5" is incomplete and meaningless without specifying the modulus. Always write the modulus explicitly: 17 ≡ 5 (mod 4).

Mistake 3 — Cancellation Without Care

"Since 6 × 4 ≡ 6 × 10 (mod 12), I can cancel 6 to get 4 ≡ 10 (mod 12)."

Correct: In modular arithmetic, cancellation requires that gcd(c, n) = 1. Here gcd(6, 12) = 6 ≠ 1, so cancellation is not valid. In fact, 4 ≢ 10 (mod 12). The arithmetic 6 × 4 = 24 ≡ 0 (mod 12) and 6 × 10 = 60 ≡ 0 (mod 12) are both 0 mod 12, but 4 and 10 are not congruent.

Mistake 4 — Assuming Modular Inverses Always Exist

"Find the inverse of 4 modulo 6." (attempted when gcd(4,6) = 2)

Correct: The modular inverse of a modulo n exists only when gcd(a, n) = 1. Since gcd(4, 6) = 2 ≠ 1, the number 4 has no inverse modulo 6. The equation 4x ≡ 1 (mod 6) has no solution.

Mistake 5 — Negative Remainders

"−13 mod 5 = −3"

Correct: Remainders must always be in the range {0, 1, …, n − 1}. For negative values, use the Division Algorithm: −13 = 5 × (−3) + 2, so −13 ≡ 2 (mod 5). Check: −13 − 2 = −15 = 5 × (−3). ✓

Mistake 6 — Dividing Both Sides Without Using the Inverse

"Solve 3x ≡ 9 (mod 12) by dividing both sides by 3 to get x ≡ 3 (mod 12)."

Correct: Since gcd(3, 12) = 3, which divides 9, solutions exist — but there are multiple. Dividing naïvely gives only one. The correct approach: 3x ≡ 9 (mod 12) simplifies to x ≡ 3 (mod 4), giving three solutions modulo 12: x = 3, 7, 11. Dividing by 3 in modular arithmetic is only straightforward when gcd(3, n) = 1.

Section 6.14

Preparing for Cryptography and Algorithms

The integers, as studied in this chapter, are the mathematical substrate of much of modern computing. Every tool developed here appears in subsequent chapters and later courses:

Tool	Application
Divisibility and Primes	Foundation of public-key cryptography; primality testing; RSA encryption
Euclidean Algorithm	Efficient GCD computation; Chapter 12 algorithm analysis; cryptographic key generation
Bézout's Identity	Computing modular inverses; solving linear congruences; extended Euclidean algorithm
Modular Arithmetic	Clock systems; checksums; hash functions; cyclic data structures
Modular Exponentiation	RSA encryption/decryption; Diffie-Hellman key exchange; discrete logarithm problem

Chapter 6 — Back Matter

Chapter Summary

Sec 6.1The integers ℤ are the foundation of discrete mathematics. Integer structure — divisibility, factoring, and cyclic systems — appears throughout computing, algorithms, and cryptography.
Sec 6.2Divisibility is defined by existence: b | a if there is an integer k with a = bk. Key properties: sums, differences, and scalar multiples of multiples are multiples. The Division Algorithm guarantees a unique quotient and remainder 0 ≤ r < b.
Sec 6.3A prime is an integer > 1 with no positive divisors other than 1 and itself. The Fundamental Theorem of Arithmetic: every integer > 1 has a unique prime factorization. There are infinitely many primes (Euclid's proof by contradiction).
Sec 6.4The GCD of a and b is the largest integer dividing both. Computed by taking the minimum power of each shared prime. When gcd(a, b) = 1, a and b are coprime — a key condition for modular inverses.
Sec 6.5The LCM is the smallest positive multiple of both a and b. Computed by taking the maximum power of each prime. The formula gcd(a, b) × lcm(a, b) = a × b connects the two.
Sec 6.6The Euclidean Algorithm computes gcd(a, b) by repeated application of the Division Algorithm. It is far more efficient than factoring — running time is proportional to the number of digits. Key lemma: if a = bq + r, then gcd(a, b) = gcd(b, r).
Sec 6.7Bézout's Identity: gcd(a, b) = sa + tb for some integers s and t. The Bézout coefficients are found by back-substitution through the Euclidean Algorithm steps. This is the tool for computing modular inverses.
Sec 6.8Congruence modulo n: a ≡ b (mod n) if n divides a − b. Congruence is an equivalence relation partitioning ℤ into n residue classes {[0], [1], …, [n−1]}. Every integer has a unique residue in this range.
Sec 6.9Modular arithmetic is consistent: congruences can be added, subtracted, and multiplied. Results can be reduced before or after the operation. The residues modulo n form a complete, closed arithmetic system.
Sec 6.10Modular exponentiation computes aᵉ (mod n) efficiently using repeated squaring, requiring about 2 log₂ e multiplications. This is the engine behind RSA encryption and Diffie-Hellman key exchange.
Sec 6.11The equation ax ≡ b (mod n) has a solution iff gcd(a, n) | b. When gcd(a, n) = 1, a has a modular inverse a⁻¹, found via Bézout's Identity, and the equation has a unique solution modulo n.
Sec 6.12Applications: clocks (mod 12 or 7), ISBN-13 checksums (alternating weights mod 10), hash functions (k mod m), and cryptographic systems (modular exponentiation with large primes).
Sec 6.13Six common errors: treating ≡ as =; missing the modulus; invalid cancellation when gcd ≠ 1; assuming all inverses exist; producing negative remainders; dividing without using the modular inverse.
Sec 6.14All tools in this chapter reappear in Chapter 12 (algorithm analysis), cryptography (RSA, Diffie-Hellman), data structures (hashing), and Chapter 14 (discrete modeling). This chapter is the number-theoretic foundation for the rest of the book.

Key Terms Review

divisor

An integer b that divides a with no remainder: b | a means a = bk for some integer k.

multiple

An integer a is a multiple of b if b | a. Every integer bk is a multiple of b.

prime

An integer > 1 whose only positive divisors are 1 and itself. The building blocks of all integers.

composite

An integer > 1 that has a positive divisor other than 1 and itself. It can be factored into smaller integers.

GCD

Greatest common divisor: the largest integer dividing both a and b. Written gcd(a, b).

LCM

Least common multiple: the smallest positive multiple of both a and b. Related to GCD by gcd × lcm = a × b.

coprime

Two integers a and b with gcd(a, b) = 1. Also called relatively prime. Essential for modular inverses.

Euclidean Algorithm

An efficient repeated-division procedure for computing GCDs. Runs in time proportional to the number of digits.

Bézout's Identity

The GCD of a and b can be written as sa + tb for integers s and t (the Bézout coefficients).

congruence mod n

a ≡ b (mod n) if n divides a − b. Equivalently, a and b have the same remainder when divided by n.

residue

The remainder of a divided by n. The unique representative of a congruence class in {0, 1, …, n − 1}.

congruence class

The set of all integers congruent to a given integer modulo n. Also called an equivalence class or residue class.

modular inverse

An integer a⁻¹ such that a · a⁻¹ ≡ 1 (mod n). Exists only when gcd(a, n) = 1. Found using Bézout's Identity.

modular exponentiation

Computing aᵉ (mod n) efficiently using repeated squaring. Requires about 2 log₂ e multiplications.

linear combination

An expression of the form sa + tb for integers s and t. Bézout's Identity says gcd(a,b) is always such a combination.

hash function

A function that maps data to a fixed-size value. Modular hash functions use k mod m to assign keys to slots.

checksum

A value derived from data using modular arithmetic, used to detect transmission or transcription errors.

Division Algorithm

For any integer a and positive integer b, there exist unique q and r with a = bq + r and 0 ≤ r < b.

Concept Review Questions

What does it mean for b to divide a? State the definition precisely using the word "exists."
What does the Division Algorithm guarantee? What are q and r called?
What is a prime number? How does it differ from a composite?
What does the Fundamental Theorem of Arithmetic say?
What is the greatest common divisor of two integers?
What does it mean for two integers to be coprime? Why does this matter?
Describe the Euclidean Algorithm in one paragraph, including why it terminates.
What does Bézout's Identity state? How are the coefficients found?
What does a ≡ b (mod n) mean? Give two equivalent definitions.
What three properties make congruence modulo n an equivalence relation?
What is a modular inverse? When does it exist?
What kind of problem does modular exponentiation solve, and why is efficiency important?

Skill Practice

Part ADivisibility and Primality

Find all positive divisors of 60.
Is 91 prime? Justify.
Is 143 prime? (Check primes up to √143 ≈ 12.)
Factor 420 completely.
Prove: if a | b and a | c, then a | (2b − 3c).
Prove: if p is prime and p | ab, then p | a or p | b. (Euclid's Lemma)

Part BGCD, LCM, and Euclidean Algorithm

gcd(168, 126) by Euclidean Algorithm
lcm(168, 126) using the GCD result
Express gcd(168, 126) as a linear combination
gcd(391, 299) by Euclidean Algorithm
gcd(1001, 143) by Euclidean Algorithm
Prove Lemma 6.6.1: if a = bq + r, then gcd(a, b) = gcd(b, r).

Part CCongruence and Modular Arithmetic

Find residue of 100 mod 11
Find residue of −7 mod 5
5⁻¹ (mod 11)
7⁻¹ (mod 12) or state it doesn't exist
Solve 3x ≡ 2 (mod 5)
Solve 5x ≡ 7 (mod 13)
Compute 2¹⁰ (mod 7)
Compute 3²⁰ (mod 11)

Part DProof Problems

Prove: if n is an even integer, then n² ≡ 0 (mod 4).
Prove: if n is an odd integer, then n² ≡ 1 (mod 8).
Prove: if gcd(a, n) = 1, then a has a modular inverse modulo n. (Use Bézout's Identity.)
Find a pattern in the powers of 2 modulo 7: compute 2¹, 2², …, 2⁷ (mod 7). What is the period? Explain why powers cycle.

Applications

Clock Arithmetic. Today is Thursday. What day is it: (a) 30 days from now? (b) 100 days from now? (c) 365 days from now?
ISBN Check. An ISBN-13 has first 12 digits 978045152493. Compute the required check digit using the ISBN-13 formula.
Hashing. A hash table has 37 slots. Using h(k) = k mod 37, find the slot for k = 1000, k = 5923, and k = 73.
Cyclic Scheduling. A factory runs three shifts on a 3-day cycle: morning (0), afternoon (1), night (2). If today is day 0 (morning shift), which shift is working on day 47?
Affine Cipher. In a simple cipher, each letter m (encoded as 0–25) is encrypted as c = 3m + 5 (mod 26). Decrypt the letter encoded as c = 14 by solving for m.
Simultaneous Activation. A light flashes every 4 seconds and a buzzer sounds every 7 seconds. They both activate at time 0. After how many seconds do they next activate simultaneously? Use modular arithmetic to explain.

Error Analysis

Each problem shows a student's work containing one or more errors. Identify the error and write the correct solution.

Problem 1 — Faulty Cancellation

6 × 4 ≡ 6 × 10 (mod 12), so cancel 6: 4 ≡ 10 (mod 12).

Is the initial arithmetic correct? Is the cancellation valid? What went wrong, and what is the correct conclusion?

Problem 2 — Negative Remainder

−13 mod 5 = −3

What is the correct result? Rewrite −13 in the form 5q + r with 0 ≤ r < 5.

Problem 3 — Non-Existent Inverse

Find the inverse of 4 modulo 6: since 4 × 4 = 16 ≡ 4 and 4 × 2 = 8 ≡ 2, there's no exact inverse, so guess x = 3.

Why does 4 have no inverse modulo 6? Why does the equation 4x ≡ 1 (mod 6) have no solution?

Problem 4 — Congruence Versus Equality

"Since 23 ≡ 2 (mod 7), the number 23 equals 2."

Correct the student's understanding. What does ≡ mean, and what does it not mean?

Problem 5 — Wrong Set of Solutions

"Solve 3x ≡ 9 (mod 12). Divide both sides by 3: x ≡ 3 (mod 12). The unique solution is x = 3."

What is wrong with this reasoning? Find all solutions to 3x ≡ 9 (mod 12).

Chapter 6 Checkpoint

Complete without assistance — assesses all key skills and concepts from Chapter 6

Part A — Divisibility and Primes

State the definition of "b divides a" using the word "exists."
Determine whether each statement is true or false. Briefly justify each.
1. 8 | 64
2. 9 | 100
3. 7 | 0
4. 1 | 243
Find the prime factorization of 420.
Determine whether 143 is prime. Show your reasoning. (Check primes up to √143 ≈ 12.)

Part B — GCD and Euclidean Algorithm

Find gcd(168, 126) using the Euclidean Algorithm. Show all steps.
Find lcm(168, 126) using the GCD result from Problem 5.
Express gcd(168, 126) as a linear combination of 168 and 126.

Part C — Congruence and Modular Arithmetic

Determine whether each congruence is true or false.
1. 35 ≡ 5 (mod 10)
2. 47 ≡ 4 (mod 9)
3. −8 ≡ 4 (mod 6)
Compute each.
1. (47 + 83) mod 9
2. (17 × 23) mod 5
3. 2¹² mod 7 (use repeated squaring)
Find the modular inverse of 5 modulo 13, or explain why it does not exist.
Solve 5x ≡ 7 (mod 13).

Part D — Applications and Proof

Today is Thursday. What day of the week is it 200 days from now?
Prove that if n is an even integer, then n² ≡ 0 (mod 4).
A student says that because 2 × 6 ≡ 2 × 3 (mod 6), we can cancel 2 to conclude 6 ≡ 3 (mod 6). Is this valid? Explain what went wrong and what the correct conclusion is.
Explain in two or three sentences why modular exponentiation is useful in cryptography. What property of modular arithmetic makes large computations manageable?

Answers may be placed in the answer key.

Looking Ahead

Chapter 7: Counting Principles

Chapter 6 developed the integer structure that underlies computing and cryptography. Chapter 7 turns to a different kind of discrete question: how many ways can something happen? Rather than analyzing the internal structure of numbers, we will analyze how to count structured choices — arrangements, selections, groupings, and restricted outcomes — without listing every possibility individually. The tools will be the sum rule, product rule, tree diagrams, and inclusion-exclusion. These counting methods, combined with the number theory developed in Chapter 6, form the mathematical foundation for probability, combinatorics, and algorithm analysis.

MGU Library Connection

Appendix H: Divisibility and Modular Arithmetic Reference — formula sheet for all results in this chapter
Appendix F: Proof Strategy Guide — templates for direct proof and proof by contradiction
Chapter 12: Algorithms and Complexity — Euclidean Algorithm revisited with Big-O analysis
MGU Cryptography course — RSA encryption and Diffie-Hellman key exchange
MGU Cybersecurity course — checksums, hashing, and error detection in practice
MGU Dictionary entries: divisibility, prime number, GCD, modular arithmetic, congruence, modular inverse

Chapter 6:Integers, Divisibility,and Modular Arithmetic

Purpose and Overview

Why This Chapter Matters

Learning Objectives

Sections at a Glance

Integers in Discrete Mathematics

Divisibility

Properties of Divisibility

The Division Algorithm

Prime and Composite Numbers

Greatest Common Divisor

Least Common Multiple Review

The Euclidean Algorithm

Bézout's Identity: An Introduction

Congruence Modulo n

Congruence as an Equivalence Relation

Modular Addition and Multiplication

Addition Table for ℤ₅

Modular Exponentiation: An Introduction

Solving Simple Modular Equations

Modular Arithmetic in Clocks, Codes, and Computing

Clocks and Cyclic Systems

Checksums and Error Detection

Hashing in Computer Science

Common Modular Arithmetic Mistakes

Preparing for Cryptography and Algorithms

Chapter Summary

Key Terms Review

Concept Review Questions

Skill Practice

Applications

Error Analysis

Chapter 6 Checkpoint

Chapter 6:
Integers, Divisibility,
and Modular Arithmetic