CSET Mathematics Exam (211, 212, 213)

This chapter covers Subtest I requirement 0002, Number Theory (SMR 1.2). It treats divisibility and divisibility proofs, mathematical induction, the division and Euclidean algorithms with linear combinations, the Fundamental Theorem of Arithmetic and its consequences (GCF, LCM, lowest terms, irrational square roots), counting divisors, and modular arithmetic. Expect proof-flavored questions: which step justifies a conclusion, why an algorithm works, or how many divisors a number has.

For integers a and b with a ≠ 0, a divides b, written a | b, if b = ak for some integer k. Then a is a divisor (factor) of b and b is a multiple of a. A prime is an integer p > 1 whose only positive divisors are 1 and p; an integer greater than 1 that is not prime is composite. The number 1 is neither prime nor composite.

Basic divisibility facts follow directly from the definition:

If a | b and b | c, then a | c (transitivity).

If a | b and a | c, then a | (bx + cy) for all integers x and y.

If a | b and b ≠ 0, then |a| ≤ |b|.

Among any two consecutive integers one is even, so 2 divides the product.

Among any three consecutive integers one is a multiple of 3, so 3 divides the product.

Since 2 and 3 are relatively prime and both divide n^3 - n, their product 6 divides n^3 - n.

Result: 6 | (n^3 - n) for all integers n.

The Principle of Mathematical Induction: Let P(n) be a statement about the integer n. If (1) P(n0) is true (the base case), and (2) for every k ≥ n0, P(k) true implies P(k + 1) true (the inductive step), then P(n) is true for every integer n ≥ n0.

By the Principle of Mathematical Induction, P(n) holds for all n ≥ 1. This completes the proof.

Induction also proves divisibility statements.

Since 4m + 1 is an integer, 3 divides 4^(k+1) - 1.

The Division Algorithm: For integers a and b with b > 0, there are unique integers q (quotient) and r (remainder) with a = bq + r and 0 ≤ r < b.

The greatest common divisor gcd(a, b) is the largest positive integer dividing both a and b (not both zero). Integers with gcd 1 are relatively prime. The Euclidean algorithm finds the gcd by repeated division and rests on one lemma.

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

Proof: It is enough to show that a and b have exactly the same common divisors as b and r. If d | a and d | b, then d divides a - bq = r, so d is a common divisor of b and r. Conversely, if d | b and d | r, then d divides bq + r = a, so d is a common divisor of a and b. The two pairs have the same set of common divisors, so they have the same greatest common divisor. This completes the proof.

Applying the lemma repeatedly shrinks the numbers until the remainder is 0; the last nonzero remainder is the gcd.

From step 1, 147 = 1071 - 2 · 462. Substitute: 21 = 462 - 3(1071 - 2 · 462) = 7 · 462 - 3 · 1071.

Consequences of Bezout's identity:

The linear Diophantine equation ax + by = c has integer solutions exactly when gcd(a, b) divides c. If (x0, y0) is one solution and d = gcd(a, b), all solutions are x = x0 + (b/d)t, y = y0 - (a/d)t for integers t.

Euclid's Lemma: if p is prime and p | ab, then p | a or p | b.

If gcd(a, b) = 1 and a | bc, then a | c.

Worked Example: Does 6x + 15y = 20 have integer solutions? Does 6x + 15y = 21? gcd(6, 15) = 3.

3 divides 21. Divide by 3: 2x + 5y = 7, which has the solution x = 1, y = 1.

Result: 6x + 15y = 20 has no integer solutions; 6x + 15y = 21 has solutions such as (1, 1), and in general (1 + 5t, 1 - 2t).

The Fundamental Theorem of Arithmetic: Every integer n > 1 can be written as a product of primes, and this factorization is unique apart from the order of the factors.

Prime factorizations give the gcd and lcm at once. If a and b are written with the same primes (using exponent 0 where needed), gcd(a, b) uses the minimum exponent of each prime and lcm(a, b) uses the maximum. Because min + max of two exponents is their sum, gcd(a, b) · lcm(a, b) = ab for positive a and b.

Worked Example: Find gcd(360, 84) and lcm(360, 84).

Factor: 360 = 2^3 · 3^2 · 5 and 84 = 2^2 · 3 · 7.

Theorem: sqrt(2) is irrational.

Proof: Suppose, for contradiction, that sqrt(2) = a/b with a and b positive integers and the fraction in lowest terms, so gcd(a, b) = 1.

Squaring gives 2 = a^2/b^2, so a^2 = 2b^2.

Then a^2 is even. If a were odd, a^2 would be odd, so a is even; write a = 2k.

Substitute: 4k^2 = 2b^2, so b^2 = 2k^2, and b^2 is even. By the same reasoning, b is even.

Now 2 divides both a and b, contradicting gcd(a, b) = 1.

Therefore no such fraction exists, and sqrt(2) is irrational. This completes the proof.

The Fundamental Theorem of Arithmetic generalizes this: if n is a positive integer that is not a perfect square, then sqrt(n) is irrational. If sqrt(n) = a/b, then a^2 = nb^2. In the factorization of a^2 and b^2, every prime appears to an even power. Because n is not a perfect square, some prime p appears in n to an odd power, so p appears to an odd power on the right side and an even power on the left, contradicting unique factorization.

Common Trap: The same argument does not show sqrt(4) is irrational, because 4 = 2^2 has all even exponents. The key hypothesis is "n is not a perfect square."

If n = p1^a1 · p2^a2 · ... · pk^ak is the prime factorization, then every positive divisor of n has the form p1^b1 · ... · pk^bk with 0 ≤ bi ≤ ai. Each exponent bi has ai + 1 choices, so the number of positive divisors is d(n) = (a1 + 1)(a2 + 1) ... (ak + 1).

For a positive integer m, a is congruent to b modulo m, written a ≡ b (mod m), if m | (a - b); equivalently, a and b leave the same remainder when divided by m. Congruence mod m is an equivalence relation, and it respects addition, subtraction, and multiplication: if a ≡ b and c ≡ d (mod m), then a + c ≡ b + d, a - c ≡ b - d, ac ≡ bd, and a^n ≡ b^n (mod m).

Result: 7^100 leaves remainder 1 when divided by 5.

Worked Example: Find the units digit of 3^87.

The units digit is the remainder mod 10.

Powers of 3 mod 10 cycle: 3, 9, 7, 1, then repeat with period 4.

Result: The units digit of 3^87 is 7.

Worked Example: Solve 7x ≡ 3 (mod 10).

gcd(7, 10) = 1, so 7 has an inverse mod 10.

Congruences explain the divisibility tests. Because 10 ≡ 1 (mod 9), a number is congruent to its digit sum mod 9 (and mod 3). Because 10 ≡ -1 (mod 11), a number is congruent mod 11 to the alternating sum of its digits starting from the units digit.

Divisibility Tests and Their Reasons

Fermat's Little Theorem: If p is prime and p does not divide a, then a^(p-1) ≡ 1 (mod p). In the first example, 2^4 ≡ 1 (mod 5) is this theorem with p = 5.

Exam Tip: The integers mod m, written Z_m = {0, 1, ..., m - 1}, reappear in Chapter 2.1 as examples of rings and fields. Z_m is a field exactly when m is prime, because only then does every nonzero element have an inverse.

a | b means b = ak; if a divides b and c, it divides every combination bx + cy. Combine divisors only when they are relatively prime.

An induction proof needs a base case, a stated hypothesis, and an inductive step that visibly uses the hypothesis.

gcd(a, b) = gcd(b, r) because both pairs have the same common divisors; back-substitution in the Euclidean algorithm gives Bezout's identity ax + by = gcd(a, b).

Unique prime factorization gives gcd (minimum exponents), lcm (maximum exponents), gcd · lcm = ab, unique lowest terms, and the irrationality of sqrt(n) for non-squares n.

The number of divisors is the product of (exponent + 1); in modular arithmetic you may add, subtract, multiply, and raise to powers, but divide only by numbers relatively prime to the modulus.