Elementary Number Theory PDF Download – Barrus & Clark (LibreTexts, 2021) BS Math

Elementary Number Theory by Mike Barrus and W. Edwin Clark is a free university textbook on the whole numbers: divisibility, primes, congruences and the arithmetic behind modern encryption. Barrus, of the University of Rhode Island, adapted it from a 2002 text by Clark, now Professor Emeritus at the University of South Florida. It is published on Mathematics LibreTexts under a Creative Commons licence, so you can read it online or save it as a PDF.

For BS Mathematics students this is where proof writing meets real arithmetic. The book starts from the axioms for the integers and induction, then proves the Division Algorithm, Bezout’s Lemma, unique factorisation, the Chinese Remainder Theorem and the theorems of Wilson, Euler and Fermat. It ends with RSA encryption and the question of which integers are sums of two, three or four squares. Every chapter closes with exercises, which makes it as useful for semester exam preparation as for self-study.

Book Overview

Chapter List

Chapter 1.1: What Is Number Theory?

Difficulty: Easy · Key topics: sums of squares, primes, integer equations, prime-generating formulas, RSA preview, “mod”

The opening chapter is a tour of questions, not a list of theorems. It quotes Gauss, who called number theory “arithmetic,” and then poses puzzles: which integers are sums of two, three or four squares; whether n³ + n² + 17 is prime for every n; whether 3x + 17y = 10 and 154x − 33y = 10 have integer solutions; and whether xⁿ + yⁿ = zⁿ can be solved for n > 2. A toy RSA example encrypts 1234 with exponent 43 modulo 1517 to get 1253, and shows why real moduli must be huge. The chapter ends with its “three wishes”: notice patterns in the integers, see their applications, and gain mathematical maturity.

Key Points:

• Number theory studies the integers; a prime is an integer greater than 1 whose only positive divisors are 1 and itself
• The list of sums of two squares (0, 1, 2, 4, 5, 8, 9, 10, 13, …) skips 3, 6, 7, 11 and 12
• 7, 15 and 23 are not sums of three squares, yet every integer from 0 to 100 is a sum of four squares (for example 23 = 9 + 9 + 4 + 1)
• n³ + n² + 17 is prime for n = 0 to 10, but a pattern in small cases is not a proof that it always works
• “a mod b” is shorthand for “the remainder after dividing a by b”
• Recurring themes: ways to write integers, producing and recognising primes, integer solutions of equations, and algorithms built on integer properties

Memory Tip: Before reading Section 1.28, list the sums of two squares up to 50 yourself and circle the gaps. The book suggests small programs or a computer algebra system for this kind of experiment.

Common Mistake: Treating a pattern found in a few cases as a proof. n³ + n² + 17 looks prime for the first eleven values of n, but n = 17 gives 17 × 307 = 5219.

Important Questions:

• Is n³ + n² + 17 prime for every n? No. It is prime for n = 0 to 10, but at n = 17 it equals 17 × 307. The chapter uses it to show that a formula which works for many inputs can still fail.
• What do the sums-of-squares experiments ask? Which integers are sums of two squares, whether the gaps in the three-squares list repeat every 8 (7, 15, 23, then 31), and whether every positive integer is a sum of four squares. Section 1.28 answers all three.

Chapter 1.2: Basic Axioms for ℤ

Difficulty: Easy · Key topics: number sets, closure, Archimedean Property, Well-Ordering Principle, induction principle, floor and ceiling

This chapter fixes the ground rules. It names the number sets ℕ ⊂ ℤ ⊂ ℚ ⊂ ℝ ⊂ ℂ and lists the facts about the integers that the book accepts without proof: closure under sum, difference and product; no integer lies strictly between a and a + 1; ab = 1 forces both to be 1 or both −1; laws of exponents and inequalities; the Archimedean Property; the Well-Ordering Principle; and the Principle of Mathematical Induction. It then defines the floor ⌊x⌋ and ceiling ⌈x⌉, proves Lemma 1 (x − 1 < ⌊x⌋ ≤ x) and sets the convention that lowercase letters denote integers.

Key Points:

• Closure: the sum, difference and product of integers are integers, and no integer x satisfies a < x < a + 1
• Well-Ordering Principle: every nonempty subset of ℕ has a least element
• Archimedean Property: for every real r there is a natural number n > r
• ⌊x⌋ is the greatest integer ≤ x and ⌈x⌉ the least integer ≥ x; ⌊x⌋ = n exactly when n ≤ x < n + 1
• Lemma 1: x − 1 < ⌊x⌋ ≤ x for every real x
• ⌊−3.1⌋ = −4 while ⌈−3.1⌉ = −3

Memory Tip: The floor always goes down and the ceiling always goes up, even for negative numbers: the floor of −3.1 is −4, not −3.

Common Mistake: Reading ⌊x⌋ as “drop the decimal part.” That works for positive x only; for negative x the floor moves away from zero.

Important Questions:

• Are ⌊2x⌋ and 2⌊x⌋ always equal? No. Always ⌊2x⌋ ≥ 2⌊x⌋, and the inequality can be strict: for x = 0.5, ⌊2x⌋ = 1 but 2⌊x⌋ = 0. The book asks you to prove this using Lemma 1.
• Why does ⌊x⌋ exist for every real x? The Archimedean Property gives an integer above x, and Well-Ordering then yields a greatest integer not exceeding x. The book leaves the details as Exercise 6.

Chapter 1.3: Proof by Induction

Difficulty: Medium · Key topics: induction principle, base case, induction hypothesis, induction step, sum of squares, 2ⁿ > 5n

Starting from the partial sums of squares 1, 5, 14, 30, 55, … the chapter factors them, notices that each equals n(n+1)(2n+1)/6, and asks how such a pattern can be proved. It restates the Principle of Mathematical Induction as two checks, a starting value n₀ and a step from n₀, …, k to k + 1, and names P(n), the induction hypothesis and the induction step. It lists eight parts of a properly written induction proof, proves the sum-of-squares formula twice (the second time in polished form) and proves 2ⁿ > 5n for n ≥ 5.

Key Points:

• P(n) must be a complete statement (an equation or inequality), not just an expression
• Base case: prove P(n₀). Step: assume P(n₀), …, P(k) and prove P(k + 1)
• 1² + 2² + ⋯ + n² = n(n+1)(2n+1)/6 for every n ≥ 1
• 2ⁿ > 5n holds for n ≥ 5; the starting value matters because 2⁴ = 16 < 20
• A finished proof announces induction, names P(n) and n₀, and ends by concluding “by PMI” and marking the end
• Strategy for the step: find a piece of P(k + 1) that resembles an earlier P(i) and use it

Memory Tip: Check the step like falling dominoes: put k = 1, 2, 3 into your argument and confirm it really produces P(2), P(3), P(4).

Common Mistake: Skipping or mis-stating the base case. Without P(n₀) at the right starting value, a correct-looking induction step proves nothing.

Important Questions:

• Prove 1 + 2 + ⋯ + n = n(n+1)/2 for n ≥ 1. Base case: 1 = 1·2/2. Step: if it holds for k, add k + 1 to get k(k+1)/2 + (k+1) = (k+1)(k+2)/2, which is the formula for k + 1.
• Prove 2ⁿ > 6n for n ≥ 5. Base case: 32 > 30. Step: 2ᵏ⁺¹ = 2·2ᵏ > 12k = 6k + 6k ≥ 6k + 30 > 6(k + 1).

Chapter 1.4: Elementary Divisibility Properties

Difficulty: Easy · Key topics: divisibility, d | n, linear combination, transitivity, linearity, cancellation

Divisibility is defined exactly: d | n means n = dk for some integer k. The chapter separates the relation d | n, which is true or false, from the fraction d/n, which is a number, and gives four ways to read the statement. It stresses learning definitions word for word. Theorem 1 collects ten basic properties: reflexivity, transitivity, linearity (d | n and d | m give d | an + bm), multiplication and cancellation, the roles of 1 and 0, and the rule that d ≤ n when positive d divides positive n. It also defines a linear combination, which prepares the way for Bezout’s Lemma.

Key Points:

• d | n means n = dk for some integer k; d ∤ n is the negation
• The bar d | n is a true-or-false statement; the slash n/d is a number
• Transitivity: d | n and n | m give d | m
• Linearity: if d | n and d | m, then d | (an + bm) for all integers a, b
• 1 divides everything, everything divides 0, and n | 1 forces n = ±1
• If d and n are positive and d | n, then d ≤ n

Memory Tip: Whenever a proof says “d divides x,” immediately write x = dk with a named k. Most proofs in this chapter then take two lines.

Common Mistake: Using d | n as if it were a number, for example writing “6 | 2 = 3.” The bar makes a statement; only the slash makes a fraction.

Important Questions:

• Prove that if d | a and d | b then d | (a − b). Write a = dk and b = dl; then a − b = d(k − l). This is also linearity with coefficients 1 and −1.
• Show that (6n + 1)² − 1 is divisible by 4 for every n ≥ 0. The book asks for induction, but direct expansion also works: (6n+1)² − 1 = 36n² + 12n = 4·(9n² + 3n).

Chapter 1.5: The Division Algorithm

Difficulty: Medium · Key topics: Division Algorithm, quotient and remainder, floor, parity, a mod b

Theorem 1.5.1 says that for integers a and b with b > 0 there are unique integers q and r with a = bq + r and 0 ≤ r < b. Existence is proved by taking the set of nonnegative values a − kb and using the Well-Ordering Principle to find its least element; uniqueness follows by subtracting two representations and using the comparison property of divisibility. The chapter names quotient, remainder, dividend and divisor, ties q and r to the floor function, defines even, odd and parity, and defines a mod b as the remainder r.

Key Points:

• a = bq + r with 0 ≤ r < b, and q, r are unique
• q = ⌊a/b⌋ and r = a − b⌊a/b⌋
• n is even if n = 2k and odd if n = 2k + 1; parity is whether an integer is even or odd
• a mod b is the remainder r: 23 mod 7 = 2 and −4 mod 5 = 1
• “Divisor” here means the number you divide by (2 in 7 = 2·3 + 1), which is different from the divisibility sense of Chapter 1.4
• Sorting integers by their remainder is the idea behind residue classes

Memory Tip: For a negative a, step down to the nearest multiple of b below it. For −4 and 5 the multiple below is −5, so the remainder is 1.

Common Mistake: Giving a negative remainder, such as −4 = 5·0 + (−4). The algorithm requires 0 ≤ r < b.

Important Questions:

• Show that every integer is either even or odd, but never both. Divide n by 2: n = 2q + r with r equal to 0 or 1, and uniqueness of q and r means exactly one of the two cases occurs.
• Show that n³ − n always has 3 as a factor. n³ − n = (n − 1)n(n + 1). Write n = 3q + r with r = 0, 1 or 2; in each case one of the three consecutive factors is a multiple of 3.

Chapter 1.6: The Base b Representation of n

Difficulty: Medium · Key topics: decimal, binary, octal, hexadecimal, base b digits, repeated division, existence and uniqueness

The decimal system is generalised. For b ≥ 2, the notation [a_k, …, a_0]_b means a_k·bᵏ + … + a_1·b + a_0 with every digit between 0 and b − 1. The main theorem proves that every n > 0 has exactly one such representation with leading digit nonzero, using repeated division by b and the uniqueness part of the Division Algorithm. The chapter names binary, ternary, octal, decimal and hexadecimal (digits A to F), converts 1749 to base 7 by repeated division, and gives a greedy powers-of-two method that writes 137 as [1,0,0,0,1,0,0,1]₂.

Key Points:

• n = [a_k, …, a_0]_b means n = a_k·bᵏ + … + a_0 with 0 ≤ a_i ≤ b − 1
• Every n > 0 has exactly one base-b representation with leading digit nonzero
• Repeated division: divide by b, record the remainders and read them from last to first
• Binary digits are bits; hexadecimal uses A–F for the digits 10–15
• 137 = [1,0,0,0,1,0,0,1]₂ and 1749 = [5,0,4,6]₇
• An n-digit decimal number a satisfies n = ⌊log a⌋ + 1, which counts digits without writing the number out

Memory Tip: Repeated division produces the lowest digit first, so read the remainder column from the bottom up to get the number.

Common Mistake: Reading the remainders in the order they were produced, which writes the digits backwards.

Important Questions:

• Write 455 in binary. 455 = 256 + 128 + 64 + 4 + 2 + 1, so 455 = [1,1,1,0,0,0,1,1,1]₂ (repeated division by 2 gives the same answer).
• How many decimal digits does 2^3321928 have? Use n = ⌊y·log 2⌋ + 1 with y = 3321928. Since 3321928 × 0.30103 is just under 1,000,000, the number has exactly 1,000,000 digits.

Chapter 1.7: Greatest Common Divisor and Least Common Multiple

Difficulty: Easy · Key topics: gcd, common divisors, gcd(0,0), lcm, absolute values

Earlier chapters asked when one integer divides another; this one studies divisors and multiples that two integers share. For integers a and b, not both zero, gcd(a, b) is the largest integer dividing both, and gcd(0, 0) = 0 by convention because every integer divides 0. A string of small lemmas shows that signs and order do not matter and that, for nonzero a and b, the gcd lies between 1 and the smaller of |a| and |b|. The least common multiple is defined for natural numbers. Examples find gcd(18, 30) = 6, gcd(48, 732) by testing divisors of 48, and lcm(6, 10) = 30.

Key Points:

• gcd(a, b) is the largest integer that divides both a and b; gcd(0, 0) = 0 by convention
• gcd(a, b) = gcd(|a|, |b|) = gcd(b, a)
• For nonzero a, b: 0 < gcd(a, b) ≤ min{|a|, |b|}
• lcm(a, b) is the smallest positive integer divisible by both a and b
• gcd(18, 30) = 6 and lcm(6, 10) = 30
• The set of common divisors of a and b is the same as the set for |a| and |b|

Memory Tip: To find a small gcd by hand, list the positive divisors of the smaller number and keep the largest one that also divides the other.

Common Mistake: Thinking gcd(0, a) is 0 or 1. Every integer divides 0, so gcd(0, a) = |a| whenever a ≠ 0.

Important Questions:

• Find the gcd and lcm of 58 and 406. Since 406 = 7 × 58, the gcd is 58 and the lcm is 406.
• Why is gcd(0, 0) defined to be 0? Every integer divides 0, so the common divisors of 0 and 0 are all of ℤ, which has no largest element. The book therefore sets the value by convention.

Chapter 1.8: The Euclidean Algorithm

Difficulty: Medium · Key topics: Euclid’s algorithm, gcd(a,0), remainders, algorithm termination, Fibonacci worst case

Credited to Euclid of Alexandria around 300 BCE, the algorithm computes a gcd without knowing the divisors of either number. It rests on two lemmas: gcd(a, 0) = a for a > 0, and if a = bq + r then gcd(a, b) = gcd(b, r), because the common divisors of both pairs are identical. Repeatedly dividing, then replacing the pair by divisor and remainder, must stop since remainders strictly decrease; the last nonzero remainder is the gcd. The worked example finds gcd(803, 154) = 11 in four divisions. Exercises compare step counts with Fibonacci numbers and describe a two-player game whose final number is the gcd.

Key Points:

• gcd(a, 0) = a for every a > 0
• If a = bq + r, then gcd(a, b) = gcd(b, r)
• Stop when the remainder is 0; the answer is the last nonzero remainder
• No factorisation is needed, which is why it is far faster than factoring for large numbers
• 803 = 154·5 + 33, 154 = 33·4 + 22, 33 = 22·1 + 11, 22 = 11·2 + 0, so gcd(803, 154) = 11
• The algorithm always terminates because the remainders strictly decrease

Memory Tip: After each division the old divisor becomes the new dividend and the remainder becomes the new divisor: shift left and repeat.

Common Mistake: Reporting the final remainder 0 as the gcd. The gcd is the last nonzero remainder.

Important Questions:

• Why does gcd(a, b) = gcd(b, r) when a = bq + r? Since r = a − bq, anything dividing a and b divides r; since a = bq + r, anything dividing b and r divides a. The two pairs have the same common divisors.
• Find gcd(377, 233). These are consecutive Fibonacci numbers, so every quotient is 1 until the end and the algorithm takes its maximum number of steps; the gcd is 1.

Chapter 1.9: Bezout’s Lemma

Difficulty: Medium · Key topics: linear combinations, Bezout’s Lemma, smallest positive combination, lcm formula

The chapter starts by asking which integers can be written 9s + 24t. Tables suggest they are exactly the multiples of 3, which is gcd(9, 24). Bezout’s Lemma makes this precise: for integers a and b there are integers s and t with gcd(a, b) = sa + tb, and the linear combinations of a and b are exactly the multiples of the gcd. The proof takes the smallest positive combination d, applies the Division Algorithm to show d | a and d | b, and checks that any common divisor divides d. A corollary and Proposition 1.9.1, lcm(a, b) = ab / gcd(a, b), follow.

Key Points:

• Bezout’s Lemma: gcd(a, b) = sa + tb for some integers s, t
• The linear combinations of a and b are exactly the multiples of gcd(a, b)
• gcd(a, b) is the smallest positive linear combination of a and b
• Every common divisor of a and b divides gcd(a, b)
• lcm(a, b) = ab / gcd(a, b) for positive a, b
• The coefficients are not unique: 1 = (−1)·2 + 1·3 = 2·2 + (−1)·3

Memory Tip: The gcd is at once the largest common divisor and the smallest positive combination. If you ever find a combination equal to 1, the gcd must be 1.

Common Mistake: Concluding gcd(a, b) = d from d = sa + tb. That only shows the gcd divides d; 19s + 7t = 3 does not make gcd(19, 7) equal to 3.

Important Questions:

• What does Bezout’s Lemma say about the integers 9s + 24t? They are exactly the multiples of gcd(9, 24) = 3; for example 3 = 9·(−5) + 24·2.
• Compute lcm(803, 154). gcd(803, 154) = 11, so the lcm is 803 × 154 / 11 = 11242.

Chapter 1.10: Computing Coefficients for Bezout’s Lemma

Difficulty: Medium · Key topics: extended Euclidean algorithm, back substitution, Blankinship’s method, verification

Bezout’s Lemma proves that s and t exist but does not say how to find them; this chapter gives two methods built on the Euclidean Algorithm. The Extended Euclidean Algorithm records each division, solves every equation for its remainder and substitutes backwards, turning gcd(803, 154) = 11 into 11 = 5·803 − 26·154. Blankinship’s method, credited to a 1963 article in the American Mathematical Monthly, starts with rows (a, 1, 0) and (b, 0, 1) and applies Euclid-style row operations until a 0 appears in the first column; the other row then shows the gcd and its coefficients. It yields 1 = 136·1876 − 699·365.

Key Points:

• Extended Euclidean Algorithm: solve each division equation for its remainder, then substitute backwards
• Blankinship’s method: start with rows [a 1 0] and [b 0 1] and row-reduce until the first column has a 0
• The surviving nonzero row [d s t] gives d = sa + tb with d = gcd(a, b)
• 11 = 5·803 − 26·154 and 5 = 1·35 + (−2)·15
• Always check the final identity by multiplying it out
• If 1 = as + bt, then gcd(a, b) = 1

Memory Tip: In Blankinship’s array the first column is just the Euclidean Algorithm; the other two columns record how each entry is built from a and b.

Common Mistake: Making a slip during back substitution and not checking. Multiply out sa + tb at the end; for 1876 and 365 it must give 136 × 1876 − 699 × 365 = 1.

Important Questions:

• Find s and t with 267s + 112t = gcd(267, 112). The gcd is 1 and back substitution gives 1 = −13·267 + 31·112. Check: 31 × 112 = 3472 and 13 × 267 = 3471.
• Use Blankinship’s method on 35 and 15. Rows (35, 1, 0) and (15, 0, 1). Row 1 minus 2 × row 2 gives (5, 1, −2), and row 2 minus 3 × that gives (0, −3, 7). So gcd = 5 = 1·35 + (−2)·15.

Chapter 1.11: Prime Numbers

Difficulty: Medium · Key topics: primes, composites, Euclid’s theorem, sieve of Eratosthenes, trial division, prime counting, Prime Number Theorem, open problems

A prime is an integer p ≥ 2 whose only positive divisors are 1 and p; 1 is neither prime nor composite. The chapter shows that every integer greater than 1 has a prime divisor, proves Euclid’s theorem that there are infinitely many primes by considering p₁⋯pₙ + 1, and proves that a composite n has a prime divisor at most √n. That gives trial division and the Sieve of Eratosthenes, which finds the 25 primes below 100. It then introduces the counting function π(x) and the Prime Number Theorem, shows that arbitrarily long runs of consecutive composites exist, and lists open problems: twin primes, Goldbach and the Riemann Hypothesis.

Key Points:

• A prime p ≥ 2 has only 1 and p as positive divisors; 1 is neither prime nor composite
• Every integer n > 1 has at least one prime divisor
• Euclid: there are infinitely many primes (look at p₁⋯pₙ + 1)
• A composite n has a prime divisor p ≤ √n, so to test 97 you only try 2, 3, 5 and 7
• Prime Number Theorem: π(x) ~ x / ln x, conjectured by Gauss in 1793 and proved by Hadamard and de la Vallée Poussin
• For any n, the integers starting at (n + 1)! + 2 give a run of n consecutive composite numbers

Memory Tip: You only need primes up to √n. For 97 that means 2, 3, 5, 7, since 11² = 121 is already larger than 97.

Common Mistake: Believing Euclid’s number p₁⋯pₙ + 1 is itself always prime. It only has a prime factor missing from the list: 2·3·5·7·11·13 + 1 = 30031 = 59 × 509.

Important Questions:

• Prove that 2 is the only even prime. Any even n > 2 is divisible by 1, 2 and n, so it has a divisor other than 1 and itself and is composite.
• Why does the sieve for numbers up to 100 stop after crossing out multiples of 7? A composite number up to 100 has a prime divisor at most √100 = 10, so it is already crossed out by one of 2, 3, 5 or 7.

Chapter 1.12: Unique Factorization

Difficulty: Medium · Key topics: Fundamental Theorem of Arithmetic, Euclid’s Lemma, relatively prime, prime factorisation, gcd and lcm from exponents

The goal is the Fundamental Theorem of Arithmetic: every integer n > 1 is a product of primes in non-decreasing order in exactly one way. The proof is built from a chain of lemmas. Lemma 1 says a | bc and gcd(a, b) = 1 imply a | c, using Bezout’s Lemma; Euclid’s Lemma follows for primes and extends to products of many factors. Existence is proved by induction on composite numbers, and uniqueness by induction on the number of prime factors. As an application, a gcd takes the minimum exponent of each prime and an lcm takes the maximum, so gcd(600, 252) = 12 and lcm = 12,600.

Key Points:

• Every integer n > 1 is a product of primes p₁ ≤ p₂ ≤ … ≤ p_s, and the list is unique
• Lemma 1: if a | bc and gcd(a, b) = 1, then a | c
• Euclid’s Lemma: if p is prime and p | ab, then p | a or p | b
• a and b are relatively prime when gcd(a, b) = 1
• gcd uses the smallest exponent of each prime and lcm the largest: gcd(600, 252) = 12, lcm(600, 252) = 12,600
• 600 = 2³ · 3 · 5²

Memory Tip: Euclid’s Lemma is the one property of primes that makes uniqueness work. When factorisation fails in a new number system, ask whether Euclid’s Lemma still holds there.

Common Mistake: Using Lemma 1 without checking that gcd(a, b) = 1. Here 6 divides 4 × 9 = 36, yet 6 divides neither 4 nor 9.

Important Questions:

• How many zeros does 100! end with in base 10? Each zero needs a factor 5 (there are plenty of 2s): ⌊100/5⌋ + ⌊100/25⌋ = 20 + 4 = 24 zeros.
• Does the set of positive multiples of 3 have unique factorisation into elements that are not products of two smaller members? No. Calling such elements “S-primes,” 36 = 3 × 12 = 6 × 6 are two different factorisations into S-primes. Unique factorisation depends on the number system, not just on multiplication.

Chapter 1.13: The Gaussian Integers

Difficulty: Hard · Key topics: Gaussian integers, norm, conjugate, units, associates, Gaussian division algorithm, Gaussian primes

The Gaussian integers ℤ[i] are the numbers a + bi with a and b integers, drawn as lattice points in the plane. The norm N(a + bi) = a² + b² measures size and satisfies N(αβ) = N(α)N(β), which gives a quick test for divisibility. The four units are ±1 and ±i, and associates differ by a unit. A division algorithm holds with 0 ≤ N(ρ) < N(β), though quotient and remainder are not unique, so the Euclidean Algorithm works. Gaussian primes are defined, and unique factorisation holds up to order and associates; the example 41 = (4+5i)(4−5i) = (5+4i)(5−4i) shows why that qualifier is needed.

Key Points:

• ℤ[i] = {a + bi : a, b ∈ ℤ}; the norm is N(a + bi) = a² + b² and N(αβ) = N(α)N(β)
• The units are the elements of norm 1: 1, −1, i, −i; associates differ by a unit factor
• If N(α) does not divide N(β), then α does not divide β
• Division algorithm: α = βκ + ρ with 0 ≤ N(ρ) < N(β), but κ and ρ need not be unique
• If N(α) is prime then α is a Gaussian prime; the converse fails, since 3 is prime with norm 9
• Ordinary primes 2, 5, 13, 41 split into Gaussian factors; 3 stays prime

Memory Tip: Use the norm as a filter before any long division: 2 + i cannot divide 6 because N(2 + i) = 5 does not divide N(6) = 36.

Common Mistake: Expecting every ordinary prime to stay prime in ℤ[i]. For example 5 = (2 + i)(2 − i) and 41 = (4 + 5i)(4 − 5i).

Important Questions:

• Does 2 + i divide 6? No. The norm of 2 + i is 5 and the norm of 6 is 36, and 5 does not divide 36.
• Why must “unique factorisation” say “up to order and associates”? Because 41 = (4+5i)(4−5i) = (5+4i)(5−4i), and the factors differ only by the units i and −i, for example 5 + 4i = i(4 − 5i).

Chapter 1.14: Fermat Primes and Mersenne Primes

Difficulty: Hard · Key topics: prime-generating polynomials, Fermat numbers, Mersenne numbers, aⁿ ± 1, Lucas–Lehmer test

The chapter asks whether a formula can produce only primes. n² − n + 41 gives primes for n up to 40 but fails at n = 41, and Goldbach proved in 1752 that no nonconstant integer polynomial always gives primes. Linear forms such as 6n + 5 fare better, and Dirichlet showed an + b takes infinitely many prime values when gcd(a, b) = 1. Theorem 1 shows that if aⁿ − 1 is prime then a = 2 and n is prime, and if aⁿ + 1 is prime then a is even and n is a power of 2. Fermat numbers, Mersenne numbers, record values and the Lucas–Lehmer test follow.

Key Points:

• n² − n + 41 is prime for n = 1 to 40 but equals 41·41 at n = 41; no integer polynomial gives only primes
• If aⁿ − 1 is prime, then a = 2 and n is prime; if aⁿ + 1 is prime, a is even and n = 2ᵏ
• Fermat numbers Fₙ = 2^(2ⁿ) + 1 are prime for n = 0 to 4 (3, 5, 17, 257, 65537)
• Mersenne numbers Mₙ = 2ⁿ − 1; if Mₙ is prime then n is prime, but M₁₁ = 2047 = 23 × 89
• Lucas–Lehmer: for odd prime p, set r₁ = 4 and r_k = (r_{k−1}² − 2) mod Mₚ; Mₚ is prime exactly when r_{p−1} = 0
• Record sizes quoted in the text (such as the Mersenne prime found in December 2018) are dated and may be superseded

Memory Tip: Try Lucas–Lehmer on M₇ = 127: the sequence is 4, 14, 67, 42, 111, 0, so 127 is prime.

Common Mistake: Assuming 2ⁿ − 1 is prime whenever n is prime. The prime n = 11 gives 2047 = 23 × 89.

Important Questions:

• If 2ⁿ − 1 is prime, what must n be? n must be prime. If n = st is composite, 2ⁿ − 1 = (2ˢ)ᵗ − 1 is divisible by 2ˢ − 1.
• Use Lucas–Lehmer to show 31 is prime. For p = 5 the sequence is 4, 14, 8, 0 (mod 31), and r₄ = 0, so M₅ = 31 is prime.

Chapter 1.15: Number Theoretic Functions

Difficulty: Medium · Key topics: τ(n), σ(n), proper divisors, Euler’s totient φ(n), multiplicative functions, Carmichael’s conjecture

Three functions of a positive integer are introduced: τ(n), the number of positive divisors; σ(n), their sum; and Euler’s totient φ(n), the count of integers from 1 to n that share no factor with n. Theorem 1 gives τ and σ from the prime factorisation, τ(n) = (e₁+1)⋯(e_r+1). A function is multiplicative if f(ab) = f(a)f(b) whenever gcd(a, b) = 1, and all three functions are. The proof for φ is deferred to the Chinese Remainder Theorem chapter, but formulas for φ(pⁿ) and for general n are proved here. The chapter closes with Carmichael’s still-open conjecture on φ-values.

Key Points:

• If n = p₁^e₁ ⋯ p_r^e_r, then τ(n) = (e₁ + 1)⋯(e_r + 1) and σ(n) is a product of (pᵉ⁺¹ − 1)/(p − 1) terms
• φ(n) counts the i with 1 ≤ i ≤ n and gcd(i, n) = 1; φ(p) = p − 1 for a prime p
• φ(pⁿ) = pⁿ − pⁿ⁻¹, and φ(ab) = φ(a)φ(b) when gcd(a, b) = 1
• A proper divisor of n is a positive divisor less than n; the sum of proper divisors is σ(n) − n
• Examples: τ(12) = 6, σ(12) = 28, τ(72) = 12, σ(72) = 195, φ(9000) = 2400
• Carmichael’s conjecture (1907), that every φ-value occurs at least twice, is still open

Memory Tip: To compute φ(n), factor first and apply (pᵉ − pᵉ⁻¹) to each prime power: φ(12) = (4 − 2)(3 − 1) = 4.

Common Mistake: Using φ(ab) = φ(a)φ(b) when a and b share a factor. φ(4) = 2, but φ(2)φ(2) = 1.

Important Questions:

• When is τ(n) odd? Exactly when n is a perfect square: divisors pair up as d and n/d, and a pair collapses to one divisor only when d = n/d.
• Why is φ(n) even for every n > 2? An integer a coprime to n pairs with n − a, which is also coprime and different from a unless n = 2.

Chapter 1.16: Perfect Numbers and Mersenne Primes

Difficulty: Medium · Key topics: perfect numbers, σ(n) = 2n, even perfect numbers, Euclid–Euler form, open questions

A number n > 1 is perfect when the sum of its proper divisors equals n, which is the same as σ(n) = 2n. The perfect numbers below 10,000 are 6, 28, 496 and 8128, each of the form 2^(p−1)(2^p − 1) with 2^p − 1 prime. Theorem 1.16.1 proves that whenever 2^p − 1 is a Mersenne prime, that product is perfect, using multiplicativity of σ. Theorem 1.16.2 proves the converse for even numbers, so even perfect numbers correspond one-to-one with Mersenne primes. The chapter notes that Euclid knew the construction and that no odd perfect number is known; any must exceed 10⁵⁰.

Key Points:

• n is perfect when σ(n) = 2n, that is, when its proper divisors sum to n
• 6, 28, 496 and 8128 are perfect; for example 28 = 2²(2³ − 1)
• If 2^p − 1 is prime, then 2^(p−1)(2^p − 1) is perfect
• Every even perfect number has that form
• Even perfect numbers correspond one-to-one with Mersenne primes
• It is unknown whether any odd perfect number exists (any would exceed 10⁵⁰); no perfect number is a perfect square

Memory Tip: Write the first four as 2·3, 4·7, 16·31 and 64·127: a power of 2 times the Mersenne prime just above it.

Common Mistake: Calling 2^(p−1)(2^p − 1) perfect without checking that 2^p − 1 is prime. For p = 11, 2047 = 23 × 89, so the number is not perfect.

Important Questions:

• Is 496 perfect? 496 = 2⁴(2⁵ − 1) with 31 prime, so yes. Its proper divisors 1, 2, 4, 8, 16, 31, 62, 124, 248 add up to 496.
• Show that if n is perfect then the reciprocals of all its positive divisors add to 2. The reciprocals of the divisors d sum to σ(n)/n because d and n/d pair up, and σ(n)/n = 2n/n = 2.

Chapter 1.17: Congruences

Difficulty: Medium · Key topics: congruence, modulus, equivalence relation, compatibility with arithmetic, residues

The chapter defines a ≡ b (mod m) to mean m | (a − b) and carefully separates this relation, which is true or false, from the operation a mod b, which returns a remainder. Theorem 1 links the two: a ≡ b (mod m) exactly when a mod m = b mod m. Theorem 2 shows congruence is reflexive, symmetric and transitive, and Theorem 3 shows it respects addition, subtraction, multiplication, powers and integer polynomials, so congruences behave like equations. A showpiece example proves that 641 divides the Fermat number 2³² + 1 using only small arithmetic. Exercises cover parity, inverses modulo 15 and large powers modulo 7.

Key Points:

• a ≡ b (mod m) means m | (a − b); a ≢ b is the negation
• a ≡ b (mod m) is a relation (true or false); a mod m is an operation that returns a remainder
• Congruence modulo m is reflexive, symmetric and transitive
• If a ≡ b and c ≡ d (mod m), then a ± c ≡ b ± d, ac ≡ bd, and aⁿ ≡ bⁿ
• For every integer polynomial f, a ≡ b implies f(a) ≡ f(b) (mod m)
• a ≡ r (mod m) with 0 ≤ r < m means a mod m = r

Memory Tip: Congruences work like equations for adding, subtracting, multiplying and taking powers. Division is the exception, and Chapter 1.20 explains why.

Common Mistake: Writing “25 = 5 mod 4.” The statement 25 ≡ 5 (mod 4) is true, but 25 mod 4 = 1, so “25 = 5 mod 4” is false.

Important Questions:

• Show that 641 divides 2³² + 1. 2¹⁶ = 65536 ≡ 154 (mod 641), so 2³² ≡ 154² = 23716 ≡ −1 (mod 641), which means 641 divides 2³² + 1.
• If a ≡ b and c ≡ d (mod m), why is ac ≡ bd? ac − bd = a(c − d) + d(a − b), and both terms are multiples of m.

Chapter 1.18: Divisibility Tests for 2, 3, 5, 9, 11

Difficulty: Easy · Key topics: decimal digits, digit sum, alternating sum, casting out nines, last digit of squares

Writing a number as a = Σ aᵢ·10ⁱ and noting how 10 behaves modulo each divisor turns divisibility into a statement about digits. Since 10 ≡ 0 (mod 2 and 5), 10 ≡ 1 (mod 3 and 9) and 10 ≡ −1 (mod 11), Theorem 1.18.1 gives the remainder of a in terms of its digits, and a corollary states the familiar tests. The worked example takes 1457 through each divisor, and “casting out nines” reduces 1487 to remainder 2 by repeated digit sums. Exercises extend the idea to the last two or three digits and show which final digits perfect squares can have.

Key Points:

• a ≡ (sum of digits) modulo 3 and modulo 9, because 10 ≡ 1
• a mod 11 equals a₀ − a₁ + a₂ − ⋯ taken modulo 11, because 10 ≡ −1
• Divisibility by 2 or 5 depends only on the last digit
• Casting out nines: add digits repeatedly to find a mod 9; 1487 leaves remainder 2
• A perfect square ends in 0, 1, 4, 5, 6 or 9
• a mod 10, a mod 100, a mod 1000 are the last one, two or three digits

Memory Tip: Remember how 10 behaves: remainder 0 mod 2 and 5, remainder 1 mod 3 and 9, remainder −1 mod 11. Every test follows from that.

Common Mistake: Starting the alternating sum at the left. For the remainder mod 11, start with the units digit as plus: 1457 gives 7 − 5 + 4 − 1 = 5, whereas starting at the left gives −5, which is the wrong remainder.

Important Questions:

• Why can a perfect square not end in 2, 3, 7 or 8? Squaring the digits 0 to 9 gives last digits 0, 1, 4, 9, 6, 5 only, so every perfect square ends in 0, 1, 4, 5, 6 or 9.
• Why does the digit-sum test work for 9? Because 10 ≡ 1 (mod 9), each 10ⁱ ≡ 1, so a has the same remainder as the sum of its digits.

Chapter 1.19: Divisibility Tests for 7 and 13

Difficulty: Medium · Key topics: tests for 7 and 13, trimming the last digit, repeated reduction, congruence proofs

The tests for 7 and 13 work by trimming the last digit. Write a = 10c + a₀, where c is a with its last digit removed. Theorem 1.19.1 says 7 divides a exactly when 7 divides c − 2a₀, and 13 divides a exactly when 13 divides c − 9a₀. Each step shrinks the number, so the test can be repeated until the answer is obvious: 2481 reduces to 246 and then 12, so 7 does not divide it, while 12987 reduces to 1235 and then 78 = 6 × 13. The proof of the first part uses 1 ≡ −20 (mod 7) and cancels −2 because gcd(7, −2) = 1.

Key Points:

• Write a = 10c + a₀ where a₀ is the last digit
• 7 divides a if and only if 7 divides c − 2a₀
• 13 divides a if and only if 13 divides c − 9a₀ (an exercise also proves a c + 4a₀ version)
• Repeat the test until the number is small enough to judge by eye
• 2481: 248 − 2 = 246, then 24 − 12 = 12, so 7 does not divide 2481
• No power of 10 is divisible by 7 or by 13

Memory Tip: To test 12987 for 13: strip the 7 and subtract 9 × 7 = 63 from 1298 to get 1235; again, 123 − 45 = 78 = 6 × 13.

Common Mistake: Assuming the reduced number leaves the same remainder as a. Only divisibility is preserved, so a mod 7 need not equal (c − 2a₀) mod 7.

Important Questions:

• Is 6993 divisible by 7 or by 13? By 7, yes: 699 − 6 = 693, then 69 − 6 = 63 = 7 × 9. By 13, no: 6993 = 7 × 999 and 999 is not a multiple of 13.
• Why can no power of 10 be divisible by 7 or by 13? 10ⁿ = 2ⁿ · 5ⁿ, and by unique factorisation its only prime factors are 2 and 5.

Chapter 1.20: More Properties of Congruences

Difficulty: Medium · Key topics: inverses modulo m, cancellation, solving linear congruences, gcd preserved by congruence

This chapter introduces the inverse a* of a modulo m, an integer with aa* ≡ 1 (mod m). Theorems 1 and 2 show that a has an inverse exactly when gcd(a, m) = 1, and Bezout’s Lemma supplies it: if as + mt = 1 then s is the inverse. That gives cancellation when gcd(c, m) = 1, plus versions for a common factor: ca ≡ cb (mod m) gives a ≡ b (mod m/d) with d = gcd(c, m). Examples list the units and inverses modulo 9 and solve 7x ≡ 4 (mod 25) by multiplying by 7* = 18 to get x ≡ 22. Congruent numbers are shown to have the same gcd with m.

Key Points:

• a has an inverse modulo m exactly when gcd(a, m) = 1
• If as + mt = 1 then s is an inverse of a modulo m
• Cancellation: if gcd(c, m) = 1 and ca ≡ cb (mod m), then a ≡ b (mod m)
• In general, ca ≡ cb (mod m) gives a ≡ b (mod m/d) where d = gcd(c, m)
• 7x ≡ 4 (mod 25): 7* = 18, so x ≡ 22 (mod 25)
• If a ≡ b (mod m) then gcd(a, m) = gcd(b, m)

Memory Tip: Solve ax ≡ b (mod m) the way you solve an equation, but multiply by the inverse a* instead of dividing.

Common Mistake: Cancelling a factor without checking the gcd. Modulo 6, 2·1 ≡ 2·4, yet 1 ≢ 4.

Important Questions:

• Find the inverse of 8 modulo 13 and solve 8x ≡ 4 (mod 13). 8 × 5 = 40 = 3 × 13 + 1, so 8* = 5. Then x ≡ 5 × 4 = 20 ≡ 7 (mod 13).
• Solve 4x ≡ 6 (mod 10). gcd(4, 10) = 2 divides 6, so reduce to 2x ≡ 3 (mod 5). Since 2* = 3, x ≡ 9 ≡ 4 (mod 5), i.e. x ≡ 4 or 9 (mod 10).

Chapter 1.21: Residue Classes and the Integers Modulo m

Difficulty: Medium · Key topics: residue classes, representatives, the ring ℤ_m, well-defined operations, solving congruences in ℤ_m

For a modulus m, the residue class [a] is the set of all integers congruent to a, which equals {mq + a : q ∈ ℤ}. Two classes are equal exactly when their representatives are congruent, and every class has a unique representative r = a mod m with 0 ≤ r < m, so there are exactly m classes. The set of classes is ℤ_m, with [a] + [b] = [a + b] and [a][b] = [ab]; Theorem 5 shows these are well defined. The chapter prints the addition and multiplication tables of ℤ₄ and shows how a congruence such as 272x ≡ 901 (mod 9) becomes the equation [2][x] = [1] in ℤ₉.

Key Points:

• [a] = {x : x ≡ a (mod m)} = {mq + a : q ∈ ℤ}
• [a] = [b] exactly when a ≡ b (mod m)
• There are exactly m classes: [0], [1], …, [m − 1]
• Operations [a] + [b] = [a + b] and [a][b] = [ab] do not depend on the representatives chosen
• Modulo 5: [2] + [3] = [0] and [2][3] = [1]
• For a prime p, x² ≡ 1 (mod p) only when x ≡ ±1; for composite moduli other solutions can appear

Memory Tip: Rename classes with convenient representatives. Modulo 151, [150] = [−1] and [149] = [−2], so [150][149] = [2].

Common Mistake: Forgetting that [a] is a whole infinite set rather than a single number. Modulo 3, [7] and [1] are the same class.

Important Questions:

• For m = 2, what are [0] and [1]? [0] is the set of even integers and [1] the set of odd integers; together they cover ℤ with no overlap.
• Solve 544x ≡ 863 (mod 7). Modulo 7, 544 ≡ 5 and 863 ≡ 2, so 5x ≡ 2. Since 5·3 = 15 ≡ 1, multiply by 3 to get x ≡ 6 (mod 7).

Chapter 1.22: The Groups Uₘ

Difficulty: Medium · Key topics: units in ℤ_m, group of units, abelian group, Euler’s φ as group order

A class [a] in ℤ_m is a unit if some [b] satisfies [a][b] = [1]. Theorem 1 shows [a] is a unit exactly when gcd(a, m) = 1, drawing on the inverse results of the previous chapter. The set of all units, U_m, is then described explicitly in Theorem 2 and shown in Theorem 3 to be a group under multiplication, with closure, associativity, identity [1], inverses and commutativity. Corollary 1 says |U_m| = φ(m). Example 1 lists the eight elements of U₁₅ with their inverse pairs, and a table compares U_m and φ(m) for m up to 7.

Key Points:

• [a] is a unit in ℤ_m exactly when gcd(a, m) = 1
• U_m = {[i] : 1 ≤ i ≤ m, gcd(i, m) = 1}
• U_m is an abelian group under multiplication with identity [1]
• |U_m| = φ(m)
• U₁₅ = {[1], [2], [4], [7], [8], [11], [13], [14]}; [2] and [8] are inverses, as are [7] and [13]
• [m − 1] = [−1] is always a unit and is its own inverse

Memory Tip: Switch to negative representatives to keep numbers small: in U₁₅, [11] = [−4], so [11][11] = [16] = [1].

Common Mistake: Counting a non-coprime class as a unit. [6] is not a unit modulo 9 because gcd(6, 9) = 3.

Important Questions:

• How big is U_m, and why? |U_m| = φ(m): the units are the classes of the integers from 1 to m coprime to m, and counting those is the definition of φ(m).
• What is U₇? Since 7 is prime, every nonzero class is a unit: U₇ = {[1], [2], [3], [4], [5], [6]} and φ(7) = 6.

Chapter 1.23: Chinese Remainder Theorem

Difficulty: Hard · Key topics: simultaneous congruences, pairwise coprime moduli, Bezout merging, uniqueness modulo M, φ is multiplicative

The chapter opens with a puzzle from the ancient Chinese text Sunzi Suanjing: a pile of fewer than 100 pennies leaves remainders 2, 1 and 7 when counted in groups of 3, 4 and 11. The Chinese Remainder Theorem says that for pairwise relatively prime moduli m₁, …, m_k, the system x ≡ bᵢ (mod mᵢ) has a unique solution modulo M = m₁⋯m_k. The existence proof is an algorithm: use Bezout’s Lemma to merge two congruences at a time. The pennies come to 29, and a four-congruence example gives x ≡ 125 (mod 9009). The chapter finishes the earlier promise by proving φ(ab) = φ(a)φ(b) for coprime a and b.

Key Points:

• CRT: if the moduli are pairwise relatively prime, x ≡ bᵢ (mod mᵢ) has a unique solution modulo M = m₁⋯m_k
• Merge two congruences at a time using s·m₁ + t·m₂ = 1
• x ≡ 2 (mod 3), x ≡ 1 (mod 4), x ≡ 7 (mod 11) gives x ≡ 29 (mod 132)
• If a congruence has a coefficient such as 2x ≡ 5 (mod 7), multiply by an inverse first (here x ≡ 6)
• CRT gives a bijection from U_ab to U_a × U_b, which proves φ(ab) = φ(a)φ(b)
• The theorem also holds in other settings, for example the Gaussian integers

Memory Tip: Keep each merged answer as one congruence modulo the product so far; k congruences need only k − 1 merges.

Common Mistake: Using CRT when the moduli share a factor. x ≡ 3 (mod 6) and x ≡ 4 (mod 8) have no solution: the first forces x odd and the second forces it even.

Important Questions:

• Solve x ≡ 1 (mod 8) and x ≡ 2 (mod 9). The moduli are coprime, so there is one solution modulo 72. Put x = 1 + 8k; then 8k ≡ 1 (mod 9) gives k ≡ 8, so x = 65.
• Euler’s problem: find two numbers that add up to 100, one divisible by 7 and the other by 11. Let x = 7k; then 100 − x ≡ 0 (mod 11) means x ≡ 1 (mod 11). Solving gives x = 56, and 56 + 44 = 100.

Chapter 1.24: Theorems of Wilson, Euler, and Fermat

Difficulty: Hard · Key topics: Wilson’s Theorem, Fermat’s Little Theorem, Euler’s Theorem, powers in U_m, reducing exponents

Three classical congruence theorems are presented. A table of products of nonzero residues for m = 2 to 13 suggests the pattern behind Wilson’s Theorem: (p − 1)! ≡ −1 (mod p) for prime p. The proof pairs each element of U_p with its inverse, leaving only [1] and [p − 1] unpaired. Fermat’s Little Theorem, a^(p−1) ≡ 1 (mod p) for gcd(a, p) = 1, is then generalised by Euler’s Theorem, a^φ(m) ≡ 1 (mod m), after powers of residue classes are defined. The last example shows how to compute 1234^7865435 mod 11 = 10 by shrinking the base modulo 11 and the exponent modulo 10.

Key Points:

• Wilson: if p is prime then (p − 1)! ≡ −1 (mod p); for composite m ≠ 4 the product of nonzero residues is 0
• Fermat’s Little Theorem: if p is prime and gcd(a, p) = 1 then a^(p−1) ≡ 1 (mod p)
• Euler’s Theorem: if gcd(a, m) = 1 then a^φ(m) ≡ 1 (mod m)
• Fermat’s theorem is Euler’s theorem with φ(p) = p − 1
• In the Wilson proof only [1] and [p − 1] are their own inverses, because x² ≡ 1 forces x ≡ ±1 (mod p)
• 1234^7865435 mod 11 = 10: reduce 1234 ≡ 2 and the exponent modulo 10, giving 2⁵ = 32 ≡ 10

Memory Tip: To compute a huge power modulo a prime p, shrink the base modulo p and the exponent modulo p − 1.

Common Mistake: Reducing the exponent modulo p instead of p − 1, or reducing it at all when gcd(a, p) ≠ 1.

Important Questions:

• What is 10! modulo 11? By Wilson’s Theorem, 10! ≡ −1 ≡ 10 (mod 11).
• What does Euler’s Theorem say for m = 12? φ(12) = 4, so every a coprime to 12 (1, 5, 7, 11) satisfies a⁴ ≡ 1 (mod 12).

Chapter 1.25: Primality Tests

Difficulty: Medium · Key topics: trial division, Wilson test, converse of Fermat, pseudoprimes, probable primes, AKS

Wilson’s and Fermat’s theorems can be turned into primality tests, some definitive and some probabilistic. Test 1 is trial division up to √n. Test 2 checks whether (n − 1)! ≡ −1 (mod n), which is exact but slow. Test 3, the converse of Fermat’s Little Theorem, checks a^(n−1) ≡ 1 (mod n) for every a. Tests 4 and 5 check one base or a short list of bases: failure proves a number composite, while success makes it only probably prime, and the base-2 pseudoprime 341 shows why. The chapter ends with empirical counts up to 10¹⁰ and a note that the 2002 AKS test is definitive but rarely used.

Key Points:

• Definitive tests: trial division to √n, Wilson’s (n − 1)! ≡ −1, and a^(n−1) ≡ 1 for all a from 1 to n − 1
• Test 5 uses the bases 2, 3, 5, 7, 11, 13, 17, 19, 31, 37, 41; the book treats a pass as definite up to 10⁶ and as “probably prime” beyond
• A failure of a^(n−1) ≡ 1 proves n is composite without factoring it
• A Fermat pseudoprime is a composite n with a^(n−1) ≡ 1 (mod n); 341 is one for base 2
• 91 passes base 3 and 1105 passes bases 2 and 3 although both are composite
• The 2002 AKS test is a definitive polynomial-time test but is rarely used in practice

Memory Tip: A Fermat-style test can only disprove primality; a pass is evidence, not proof.

Common Mistake: Treating 2^(n−1) ≡ 1 (mod n) as proof that n is prime. 341 = 11 × 31 passes it.

Important Questions:

• Is 341 prime? No. 341 = 11 × 31, even though 2³⁴⁰ ≡ 1 (mod 341).
• Why is the Wilson test impractical? It needs about n multiplications and reductions (8! mod 9 = 0 shows 9 is composite), so the work grows with n, far worse than trial division up to √n.

Chapter 1.26: Computation of aⁿ mod m

Difficulty: Medium · Key topics: successive squaring, binary method, operation counts, modular exponentiation

Computing aⁿ by repeated multiplication takes n − 1 steps, which is hopeless for large n. Successive squaring computes a^(2ᵏ) in only k steps, and the binary method extends this to any exponent: write n in binary, build x, x², x⁴, … by squaring, then multiply the powers matching the 1-bits. Theorem 1 shows this takes at most 2⌊log₂ n⌋ multiplications. For modular exponentiation the same method is used with a reduction modulo m after every multiplication, so numbers stay small. Examples compute 3¹⁵, 3¹⁵ mod 10 = 7 and 2⁶⁴⁴ mod 645 = 1.

Key Points:

• Repeated multiplication needs n − 1 multiplications; successive squaring reaches a^(2ᵏ) in k
• Binary method: find the binary digits of n, square repeatedly, multiply the powers at the 1-bits
• At most 2⌊log₂ n⌋ multiplications (about 3⌊log₂ n⌋ operations counting divisions)
• For modular powers, reduce modulo m after every multiplication
• 3¹⁵ needs 6 multiplications by this method instead of 14
• 2⁶⁴⁴ mod 645 = 1, using 644 = 512 + 128 + 4

Memory Tip: List the squares in a row (2, 4, 16, 256, …) and tick those that match a 1-bit of the exponent; then multiply only the ticked ones.

Common Mistake: Computing aⁿ in full and reducing at the end. The numbers explode; reduce after each multiplication.

Important Questions:

• Compute 3¹⁵ mod 10. 3² ≡ 9, 3⁴ ≡ 1, 3⁸ ≡ 1, and 15 = 8 + 4 + 2 + 1, so 3¹⁵ ≡ 1·1·9·3 = 27 ≡ 7.
• How many operations does the binary method need for n = 2,000,000? ⌊log₂ 2,000,000⌋ = 20, so at most 2 × 20 = 40 multiplications, or 3 × 20 = 60 operations counting divisions.

Chapter 1.27: The RSA Scheme

Difficulty: Hard · Key topics: public-key cryptography, RSA, encryption and decryption exponents, why RSA works, security

The chapter explains how Bob can publish a modulus m and exponent e so that anyone can send him secrets, while only he can read them. Bob chooses distinct primes p and q, sets m = pq, and finds d with ed ≡ 1 (mod φ(m)). Alice sends M = xᵉ mod m, and Bob recovers x = Mᵈ mod m. Lemma 1.27.1 proves it works using φ(m) = (p − 1)(q − 1), Fermat’s Little Theorem modulo p and q, and CRT-style combination. The worked example uses m = 57, e = 25, d = 13, turning 23 into 44 and back. The chapter discusses why m must be hard to factor and how poor parameters weaken the scheme.

Key Points:

• Public key: modulus m = pq and exponent e; private key: d with ed ≡ 1 (mod φ(m))
• Encrypt M = xᵉ mod m; decrypt x = Mᵈ mod m
• It works because x^(ed) ≡ x modulo both p and q, hence modulo pq
• φ(pq) = (p − 1)(q − 1), so anyone who can factor m can find d
• Example: m = 57 = 3 × 19, φ = 36, e = 25, d = 13 (since 25 × 13 = 325 ≡ 1 mod 36); 23 encrypts to 44 and decrypts back to 23
• The text suggests primes of about 100 digits each, and warns about shared moduli and a small d

Memory Tip: Check three things before using RSA numbers: m = pq with distinct primes, gcd(e, φ(m)) = 1, and d is the inverse of e modulo φ(m), not modulo m.

Common Mistake: Taking the inverse of e modulo m instead of modulo φ(m).

Important Questions:

• For m = 57 and e = 25, what is d? φ(57) = 2 × 18 = 36. Since 25 × 13 = 325 = 9 × 36 + 1, d = 13.
• Why can an eavesdropper not decrypt from m and e alone? She would need φ(m) = (p − 1)(q − 1), which needs p and q, i.e. she would have to factor m, which is infeasible for a modulus of about 200 digits.

Chapter 1.28: Sum of Squares

Difficulty: Hard · Key topics: sums of two, three and four squares, Gaussian integer factoring, Legendre, Lagrange, Waring’s problem, polygonal numbers

This chapter answers the questions of Chapter 1.1. From tables up to 100 it observes that no number congruent to 3 mod 4 is a sum of two squares, and states the two-squares theorem: n is a sum of two squares exactly when no prime congruent to 3 mod 4 divides it to an odd power (partly proved). The product of two sums of two squares is again one, via Gaussian integer factoring. For three squares, Legendre’s theorem says n is a sum of three squares exactly when it is not of the form 4ᵃ(8b + 7), with the impossible direction proved. Lagrange’s four-square theorem follows, and the chapter touches on Waring’s problem and polygonal numbers.

Key Points:

• Two squares: n is a sum of two squares iff every prime ≡ 3 (mod 4) divides n to an even power
• If a and b are sums of two squares, so is ab: (w² + x²)(y² + z²) = (wy − xz)² + (wz + xy)²
• Three squares (Legendre, 1797–98): n is a sum of three squares iff n is not of the form 4ᵃ(8b + 7)
• Four squares (Lagrange, 1770): every positive integer is a sum of four squares
• Squares are 0 or 1 mod 4, so a number ≡ 3 (mod 4) is never a sum of two squares; a number ≡ 7 (mod 8) is never a sum of three
• Waring’s problem asks for a fixed number of k-th powers that suffices for all integers; Hilbert proved it in 1909. Gauss: every positive integer is a sum of at most three triangular numbers

Memory Tip: For two squares, reduce modulo 4 first. For three squares, divide out factors of 4, then reduce modulo 8.

Common Mistake: Forgetting to remove factors of 4. 28 = 4 × 7 is not a sum of three squares even though 28 ≡ 4 (mod 8).

Important Questions:

• Which of 315 and 569 is a sum of two squares? 315 = 3² × 5 × 7 contains 7 (≡ 3 mod 4) to an odd power, so no. 569 is a prime ≡ 1 (mod 4), and 569 = 20² + 13².
• Why is no integer congruent to 7 mod 8 a sum of three squares? Squares are 0, 1 or 4 modulo 8, and no three of these values add up to 7 modulo 8.

Chapter 1.29: Epilogue

Difficulty: Easy · Key topics: further reading, research directions

The epilogue closes the loop with Chapter 1.1: the sums-of-squares results of Chapter 1.28 answer the last of the opening questions. It describes the book as a set of highlights from ancient and recent number theory, not the final word. For further study it points to university library shelves (many number theory books carry the call number QA 241), to the websites of Chris Caldwell and Eric Weisstein listed in the Bibliography, and to the Journal of Number Theory for current research. It notes that recent work has settled long-standing conjectures and raised new ones, and ends by asking readers what they will explore next.

Key Points:

• The epilogue links back to the questions raised in Chapter 1.1
• Number theory books are often shelved under Library of Congress call number QA 241
• It recommends websites by Chris Caldwell and Eric Weisstein, both listed in the Bibliography
• Current research appears in the Journal of Number Theory and other journals

Important Questions:

• Which opening question does Chapter 1.28 settle? The question of which integers are sums of two, three or four squares, posed in Chapter 1.1.
• Where does the epilogue send readers next? To library shelves (call number QA 241), the Caldwell and Weisstein websites, and the Journal of Number Theory.

Appendices: Prime Tables, Rings and Groups, Bibliography

Appendix · Difficulty: Easy · Key topics: prime tables, rings, groups, abelian groups, bibliography

Four appendices support the main text. Appendices 2.1 and 2.2 are tables of primes, those below 200 and those up to 400, useful for the factoring and trial-division exercises. Appendix 2.3 is optional reading that states the definitions of a ring (two operations with associativity, commutativity of addition, identities, inverses and distributivity) and a group (an associative operation with an identity and inverses), and an abelian group. Its examples include ℤ, ℚ, ℝ, ℤₙ, matrices and the group of units Uₙ. Appendix 2.4 is the Bibliography, containing the references that the Epilogue recommends.

Key Points:

• Appendix 2.1 lists the primes below 200 and Appendix 2.2 the primes up to 400
• A ring has two operations; addition is associative and commutative with an identity and inverses, multiplication is associative, and multiplication distributes over addition
• A group is a set with one associative operation, an identity element and inverses; it is abelian if the operation commutes
• Examples of rings: ℝ, ℚ, ℤ, ℤₙ and the n × n real matrices
• Examples of groups: (ℤ, +), (ℚ∖{0}, ·), (ℤₙ, +) and (Uₙ, ·)

Memory Tip: Remember that Uₙ is a group under multiplication only; the whole of ℤₙ is a ring, but its non-units have no multiplicative inverse.

Important Questions:

• What separates a ring from a group in the appendix’s definitions? A ring has two operations (addition and multiplication) linked by distributivity; a group has just one operation, with an identity and inverses.
• Which of the book’s examples is a group under multiplication and what is its size? Uₘ, the units of ℤₘ, whose order is φ(m).

Download Elementary Number Theory PDF (Free)

Elementary Number Theory is free from its official source, Mathematics LibreTexts. Click the button below to open the book page, where you can read every chapter online or use the “Download Full Book (PDF)” option.

How to Study This Book

Numbering note: LibreTexts numbers the 29 chapters 1.1 to 1.29, and theorems carry the same prefix (for example Theorem 1.16.2 lives in Chapter 1.16). This page uses those same numbers so you can match every block above to the book.

Read Chapters 1.1 to 1.4 first and slowly. Chapter 1.1 is a motivating tour with no exercises. Chapter 1.2 lists the axioms (Well-Ordering, Archimedean Property, induction) that every later proof leans on, Chapter 1.3 teaches the eight-part layout of an induction proof, and Chapter 1.4 gives the ten divisibility properties you will quote constantly. Learn the definitions word for word; the book itself insists on this.

Chapters 1.5 to 1.10 are the engine of the course: the Division Algorithm, base b representation, gcd and lcm, the Euclidean Algorithm, Bezout’s Lemma and the two methods for finding Bezout coefficients. Work Chapter 1.10 with pen and paper until both the back-substitution method and Blankinship’s array feel mechanical. Chapter 1.6 matters again in Chapter 1.26, where the binary expansion of an exponent drives fast modular powers.

Chapters 1.11 and 1.12 (primes and unique factorisation) depend on Bezout’s Lemma through Euclid’s Lemma. Chapter 1.13 (Gaussian integers) is the hardest chapter and can be left for a second pass if your syllabus skips it, but Chapter 1.28 uses it to prove that products of sums of two squares are sums of two squares, and several of its exercises need it.

Chapters 1.14 to 1.16 (Fermat and Mersenne primes, number theoretic functions, perfect numbers) form a connected thread: read 1.15 before 1.16, because the perfect-number proofs use the multiplicativity of σ. The proof of the Lucas–Lehmer test in Chapter 1.14 is cited from another source rather than proved, and the proof that φ is multiplicative waits until Chapter 1.23.

Chapters 1.17 to 1.24 are the core of modular arithmetic. Chapters 1.18 and 1.19 (divisibility tests) are applications and can be read quickly. Chapters 1.20 to 1.22 (inverses, residue classes, the groups U_m) must be understood before Chapter 1.23 (Chinese Remainder Theorem) and Chapter 1.24 (Wilson, Fermat, Euler), because those proofs work inside U_m.

Chapters 1.25 to 1.27 are the computational payoff: primality tests, fast modular exponentiation, and RSA, which uses φ (Chapter 1.15), inverses (1.20), Fermat’s Little Theorem (1.24) and fast powers (1.26). Chapter 1.28 and the short Epilogue (1.29) close the loop with the questions asked in Chapter 1.1. Keep the prime tables in the appendices open while doing factoring exercises, and read the optional Appendix 2.3 on rings and groups if you have not yet met those words.

What the book does not cover: the table of contents has no chapters on primitive roots, quadratic reciprocity or continued fractions, and quadratic residues are only mentioned in passing. If your course includes them, plan to pair this text with a second number theory book.

Used In These Programs

This book is used for the Number Theory course in: BS Mathematics. Browse all Number Theory books or all Mathematics books.

Who Should Read This

This book is written for undergraduates taking a first course in number theory, typically in a BS Mathematics program, and it is explicitly designed for a one-semester course and for self-study. It assumes familiarity with basic set theory and high-school algebra, plus a certain amount of mathematical maturity: the book proves nearly everything, so you will be reading and writing proofs from the first chapters. BS Computer Science students will find the modular arithmetic, fast exponentiation and RSA chapters a solid foundation for cryptography, and a course in discrete structures is a natural companion; see Discrete Mathematics: An Open Introduction for the proof techniques, induction and counting that this book assumes you can pick up quickly. It is not a graduate text: analytic and algebraic number theory are outside its scope.

Applicable Universities

This book is useful for students at Pakistani universities offering BS Mathematics and related programs, including Punjab University, Virtual University, COMSATS, UET, NUST, and other HEC-recognized institutions, wherever an Elementary Number Theory course is part of the curriculum.

FAQs

Related Books

• Discrete Mathematics: An Open Introduction – Oscar Levin (4th Edition)
• Discrete Structures US-3 Notes for BSCS (Computer Science)
• Number System & Boolean Algebra SN-2 Notes
• Calculus Volume 1 – Strang & Herman (OpenStax)

Elementary Number Theory gives BS Mathematics students a complete, proof-based route from divisibility to RSA in one free text. Browse more Mathematics books to build the rest of your semester reading list.

Elementary Number Theory (Barrus and Clark), by Mike Barrus (University of Rhode Island) and W. Edwin Clark (University of South Florida, Emeritus), adapted from Clark’s 2002 text. Published by Mathematics LibreTexts under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International licence (CC BY-NC-SA 4.0). Access for free at https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Number_Theory_(Barrus_and_Clark)