Study guide

1.2 Number Theory, Divisibility, Primes & Modular Arithmetic

NBPTS Adolescence & Young Adulthood / Mathematics Exam

Track your progress as you read

Finished sections get a check mark.

1 Chapter 1: Number Systems & Number Theory

1.1 Real and Complex Number Systems & Field Axioms 1.2 Number Theory, Divisibility, Primes & Modular Arithmetic 1.3 Sequences, Series & Summation Notation

2 Chapter 2: Polynomials & Algebraic Structures

2.1 Polynomial Operations, Factoring & Factor/Remainder Theorems 2.2 The Fundamental Theorem of Algebra & Polynomial Roots 2.3 Rational Expressions, Radical Equations & Inequalities 2.4 Matrices, Systems of Equations & Linear Algebra

3 Chapter 3: Functions & Functional Analysis

3.1 Foundations of Functions: Domain, Range & Notation 3.2 Function Transformations, Operations, Composition & Inverses 3.3 Exponential and Logarithmic Functions & Applications 3.4 Rational Functions, Asymptotes & Discontinuities

4 Chapter 4: Trigonometry & Periodic Phenomena

4.1 Angle Measure, Radians & The Unit Circle 4.2 Trigonometric Graphs, Amplitude, Period & Phase Shifts 4.3 Trigonometric Identities & Solving Trigonometric Equations 4.4 Laws of Sines and Cosines, Vectors & Polar Coordinates

5 Chapter 5: Geometry & Measurement

5.1 Axiomatic Geometry, Congruence, Similarity & Proof 5.2 Circle Theorems: Tangents, Chords, Secants & Angles 5.3 2D & 3D Measurement: Area, Surface Area & Volume 5.4 Coordinate Geometry & Geometric Transformations

6 Chapter 6: Single-Variable Calculus

6.1 Limits, Continuity & Average vs. Instantaneous Rate of Change 6.2 Differentiation Rules, Chain Rule & Implicit Differentiation 6.3 Applications of Derivatives: Curve Sketching, Extrema & Optimization 6.4 Definite & Indefinite Integrals, Riemann Sums & FTC 6.5 Volumes of Solids of Revolution: Disk, Washer & Shell Methods

7 Chapter 7: Statistics & Data Analysis

7.1 Descriptive Statistics, Data Distributions & Visual Displays 7.2 Bivariate Data, Scatterplots, Correlation & Linear Regression 7.3 Study Design, Sampling Methods & Sources of Bias 7.4 Inferential Statistics: Confidence Intervals & Hypothesis Testing

8 Chapter 8: Probability & Discrete Mathematics

8.1 Principles of Probability, Conditional Probability & Independence 8.2 Probability Distributions: Binomial & Normal Models 8.3 Combinatorics: Permutations, Combinations & Binomial Theorem 8.4 Graph Theory, Networks, Trees & Algorithms

9 Chapter 9: Mathematical Reasoning, Proof & Modeling

9.1 Propositional Logic, Truth Tables & Quantifiers 9.2 Proof Techniques & Mathematical Induction 9.3 The Mathematical Modeling Cycle & Secondary Applications 9.4 Historical Development of Mathematical Ideas & Cultural Contributions 9.5 Precise Communication of Mathematical Ideas, Definitions & Justification

10 Chapter 10: Secondary Mathematics Pedagogy & NBPTS Standards

10.1 The NBPTS Five Core Propositions & EAYA Mathematics Standards 10.2 Standards for Mathematical Practice & Productive Classroom Discourse 10.3 Formative Assessment, Student Error Analysis & Misconceptions 10.4 Component 1 Assessment Structure & Constructed-Response Strategy

1.2 Number Theory, Divisibility, Primes & Modular Arithmetic

Key Takeaways Explain This Topic AI

The Division Algorithm guarantees that for any integers a and b with b > 0, there exist unique integers q and r such that a = qb + r with 0 ≤ r < b; negative dividends require r ≥ 0, which forces the quotient to round down toward negative infinity.

The Fundamental Theorem of Arithmetic establishes unique prime factorization for every integer n > 1, providing prime-exponent representations for gcd(a, b) and lcm(a, b) such that gcd(a, b) · lcm(a, b) = |ab|.

The Euclidean Algorithm computes gcd(a, b) via successive remainders in logarithmic time O(log(min(a, b))), while the Extended Euclidean Algorithm computes Bézout coefficients x, y ∈ ℤ such that ax + by = gcd(a, b).

A linear Diophantine equation ax + by = c has integer solutions if and only if gcd(a, b) divides c, generating an infinite family of integer solutions parameterized by t ∈ ℤ once a particular solution (x₀, y₀) is known.

Modular congruence a ≡ b (mod m) preserves addition, subtraction, and multiplication, but division requires multiplying by the modular inverse a⁻¹, which exists if and only if gcd(a, m) = 1.

Last updated: September 2026

1.2 Number Theory, Divisibility, Primes & Modular Arithmetic

Number theory provides secondary mathematics educators with a deep repertoire of algebraic structures, discrete algorithms, and problem-solving contexts. From divisibility rules and prime factorization in middle school to cryptographic ciphers (such as RSA) and modular congruences in advanced coursework, the principles of number theory anchor algebraic fluency in discrete mathematical reasoning.

1. The Division Algorithm & Divisibility Foundations

Let a , b ∈ Z a, b \in \mathbb{Z} a , b ∈ Z with b ≠ 0 b \ne 0 b  = 0 . We say that b b b divides a a a (written b ∣ a b \mid a b ∣ a ) if there exists an integer k ∈ Z k \in \mathbb{Z} k ∈ Z such that a = b k a = bk a = bk . When b b b does not divide a a a , the fundamental division structure of the integers is governed by the Division Algorithm :

Theorem (The Division Algorithm): Given integers a a a (dividend) and b b b (divisor) with b > 0 b > 0 b > 0 , there exist unique integers q q q (quotient) and r r r (remainder) such that: a = q b + r , where 0 ≤ r < b a = qb + r, \quad \text{where } 0 \le r < b a = q b + r , where 0 ≤ r < b

The Negative Dividend Pedagogical Trap

A widespread point of confusion in secondary mathematics arises when dividing a negative integer by a positive integer. Consider dividing − 38 -38 − 38 by 7 7 7 :

Common Student Error: Many students perform truncation division (as seen in standard handheld calculators): − 38 ÷ 7 = − 5.428 ⋯ ⟹ q = − 5 -38 \div 7 = -5.428\dots \implies q = -5 − 38 ÷ 7 = − 5.428 ⋯ ⟹ q = − 5 . They write − 38 = ( − 5 ) ( 7 ) − 3 -38 = (-5)(7) - 3 − 38 = ( − 5 ) ( 7 ) − 3 , reporting a remainder of − 3 -3 − 3 . This violates the definition, which strictly requires 0 ≤ r < b 0 \le r < b 0 ≤ r < b .

Correct Mathematical Procedure: The quotient must round down toward − ∞ -\infty − ∞ , giving q = − 6 q = -6 q = − 6 . Then: − 38 = ( − 6 ) ( 7 ) + 4 -38 = (-6)(7) + 4 − 38 = ( − 6 ) ( 7 ) + 4

Here q = − 6 q = -6 q = − 6 and r = 4 r = 4 r = 4 , satisfying 0 ≤ 4 < 7 0 \le 4 < 7 0 ≤ 4 < 7 . In modular arithmetic, this yields − 38 ≡ 4 ( m o d 7 ) -38 \equiv 4 \pmod 7 − 38 ≡ 4 ( mod 7 ) .

Teaching Strategy: Have students visualize integer division on a number line. To represent − 38 -38 − 38 using jumps of size 7 7 7 from the origin, taking 5 5 5 steps left reaches − 35 -35 − 35 , which is not far enough to the left to add a positive remainder. Taking 6 6 6 steps left reaches − 42 -42 − 42 ; from − 42 -42 − 42 , one must step + 4 +4 + 4 to the right to land on − 38 -38 − 38 .

2. Prime Factorization, GCD, and LCM

A prime number is an integer p > 1 p > 1 p > 1 whose only positive divisors are 1 1 1 and p p p . Integers n > 1 n > 1 n > 1 that are not prime are composite .

The Fundamental Theorem of Arithmetic (Unique Factorization)

Every integer n > 1 n > 1 n > 1 can be expressed uniquely as a product of prime powers: n = p 1 e 1 p 2 e 2 ⋯ p k e k n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} n = p 1 e 1 ​ ​ p 2 e 2 ​ ​ ⋯ p k e k ​ ​

where p 1 < p 2 < ⋯ < p k p_1 < p_2 < \dots < p_k p 1 ​ < p 2 ​ < ⋯ < p k ​ are distinct primes and e i ≥ 1 e_i \ge 1 e i ​ ≥ 1 , up to the order of factors.

The uniqueness proof hinges on Euclid's Lemma : if a prime p p p divides a product a b ab ab , then p ∣ a p \mid a p ∣ a or p ∣ b p \mid b p ∣ b . This lemma distinguishes prime elements from arbitrary composite numbers.

Prime Testing Strategy

To test whether an integer n > 1 n > 1 n > 1 is prime, one only needs to test prime divisors p ≤ ⌊ n ⌋ p \le \lfloor\sqrt{n}\rfloor p ≤ ⌊ n ​ ⌋ .

Proof: Suppose n n n is composite. Then n = a b n = ab n = ab with 1 < a ≤ b 1 < a \le b 1 < a ≤ b . If both a > n a > \sqrt{n} a > n ​ and b > n b > \sqrt{n} b > n ​ , then a b > n n = n ab > \sqrt{n}\sqrt{n} = n ab > n ​ n ​ = n , a contradiction. Therefore, the smaller factor satisfies a ≤ n a \le \sqrt{n} a ≤ n ​ . By the Fundamental Theorem of Arithmetic, a a a has at least one prime divisor p ≤ a ≤ n p \le a \le \sqrt{n} p ≤ a ≤ n ​ .

GCD, LCM, and Their Universal Identity

For integers a = ∏ p i e i a = \prod p_i^{e_i} a = ∏ p i e i ​ ​ and b = ∏ p i f i b = \prod p_i^{f_i} b = ∏ p i f i ​ ​ , the greatest common divisor gcd ⁡ ( a , b ) \gcd(a, b) g cd ( a , b ) and least common multiple lcm ⁡ ( a , b ) \operatorname{lcm}(a, b) lcm ( a , b ) are: gcd ⁡ ( a , b ) = ∏ p i min ⁡ ( e i , f i ) , lcm ⁡ ( a , b ) = ∏ p i max ⁡ ( e i , f i ) \gcd(a, b) = \prod p_i^{\min(e_i, f_i)}, \quad \operatorname{lcm}(a, b) = \prod p_i^{\max(e_i, f_i)} g cd ( a , b ) = ∏ p i m i n ( e i ​ , f i ​ ) ​ , lcm ( a , b ) = ∏ p i m a x ( e i ​ , f i ​ ) ​

Because min ⁡ ( e i , f i ) + max ⁡ ( e i , f i ) = e i + f i \min(e_i, f_i) + \max(e_i, f_i) = e_i + f_i min ( e i ​ , f i ​ ) + max ( e i ​ , f i ​ ) = e i ​ + f i ​ for all real exponents, we obtain the universal identity: gcd ⁡ ( a , b ) ⋅ lcm ⁡ ( a , b ) = ∣ a ⋅ b ∣ \gcd(a, b) \cdot \operatorname{lcm}(a, b) = |a \cdot b| g cd ( a , b ) ⋅ lcm ( a , b ) = ∣ a ⋅ b ∣

3. The Euclidean & Extended Euclidean Algorithms

Factoring large integers into primes is computationally inefficient. The Euclidean Algorithm computes gcd ⁡ ( a , b ) \gcd(a, b) g cd ( a , b ) in logarithmic time ( O ( log ⁡ ( min ⁡ ( a , b ) ) ) O(\log(\min(a, b))) O ( lo g ( min ( a , b ))) steps by Lamé's Theorem) by applying the recurrence: gcd ⁡ ( a , b ) = gcd ⁡ ( b , a m o d b ) \gcd(a, b) = \gcd(b, a \bmod b) g cd ( a , b ) = g cd ( b , a mod b )

Bézout's Identity and the Extended Euclidean Algorithm

Bézout's Identity asserts that gcd ⁡ ( a , b ) \gcd(a, b) g cd ( a , b ) is the smallest positive integer that can be expressed as an integer linear combination of a a a and b b b : gcd ⁡ ( a , b ) = a x + b y for some x , y ∈ Z \gcd(a, b) = ax + by \quad \text{for some } x, y \in \mathbb{Z} g cd ( a , b ) = a x + b y for some x , y ∈ Z

The integers x x x and y y y are called Bézout coefficients .

Worked Example: Compute gcd ⁡ ( 138 , 42 ) \gcd(138, 42) g cd ( 138 , 42 ) and find its Bézout representation

Forward Euclidean Algorithm:

  • 138 = 3 ( 42 ) + 12 138 = 3(42) + 12 138 = 3 ( 42 ) + 12
  • 42 = 3 ( 12 ) + 6 42 = 3(12) + 6 42 = 3 ( 12 ) + 6

12 = 2 ( 6 ) + 0 12 = 2(6) + 0 12 = 2 ( 6 ) + 0 The last non-zero remainder is 6 , so gcd ⁡ ( 138 , 42 ) = 6 \gcd(138, 42) = 6 g cd ( 138 , 42 ) = 6 .

Reverse Extended Euclidean Algorithm (Back-Substitution):

  • From equation (2): 6 = 42 − 3 ( 12 ) 6 = 42 - 3(12) 6 = 42 − 3 ( 12 )
  • From equation (1): 12 = 138 − 3 ( 42 ) 12 = 138 - 3(42) 12 = 138 − 3 ( 42 )

Substitute 12 12 12 into the expression for 6 6 6 : 6 = 42 − 3 [ 138 − 3 ( 42 ) ] = 42 − 3 ( 138 ) + 9 ( 42 ) = 10 ( 42 ) − 3 ( 138 ) 6 = 42 - 3[138 - 3(42)] = 42 - 3(138) + 9(42) = 10(42) - 3(138) 6 = 42 − 3 [ 138 − 3 ( 42 )] = 42 − 3 ( 138 ) + 9 ( 42 ) = 10 ( 42 ) − 3 ( 138 )

Rewriting: 138 ( − 3 ) + 42 ( 10 ) = 6 138(-3) + 42(10) = 6 138 ( − 3 ) + 42 ( 10 ) = 6 . The Bézout coefficients are x = − 3 x = -3 x = − 3 and y = 10 y = 10 y = 10 .

4. Modular Congruence & Linear Diophantine Equations

Two integers a a a and b b b are congruent modulo m m m ( m ∈ Z + m \in \mathbb{Z}^+ m ∈ Z + ), written a ≡ b ( m o d m ) a \equiv b \pmod m a ≡ b ( mod m ) , if m ∣ ( a − b ) m \mid (a - b) m ∣ ( a − b ) . Modular congruence partitions Z \mathbb{Z} Z into m m m equivalence classes Z m = { [ 0 ] , [ 1 ] , … , [ m − 1 ] } \mathbb{Z}_m = \{[0], [1], \dots, [m-1]\} Z m ​ = {[ 0 ] , [ 1 ] , … , [ m − 1 ]} .

Algebraic Compatibility and the Cancellation Caveat

If a 1 ≡ b 1 ( m o d m ) a_1 \equiv b_1 \pmod m a 1 ​ ≡ b 1 ​ ( mod m ) and a 2 ≡ b 2 ( m o d m ) a_2 \equiv b_2 \pmod m a 2 ​ ≡ b 2 ​ ( mod m ) , then:

a 1 ± a 2 ≡ b 1 ± b 2 ( m o d m ) a_1 \pm a_2 \equiv b_1 \pm b_2 \pmod m a 1 ​ ± a 2 ​ ≡ b 1 ​ ± b 2 ​ ( mod m )

a 1 a 2 ≡ b 1 b 2 ( m o d m ) a_1 a_2 \equiv b_1 b_2 \pmod m a 1 ​ a 2 ​ ≡ b 1 ​ b 2 ​ ( mod m )

Caution

The Modular Cancellation Rule: One cannot divide across congruences arbitrarily. If a c ≡ b c ( m o d m ) ac \equiv bc \pmod m a c ≡ b c ( mod m ) , then: a ≡ b ( m o d m gcd ⁡ ( c , m ) ) a \equiv b \pmod{\frac{m}{\gcd(c, m)}} a ≡ b ( mod g c d ( c , m ) m ​ ) Canceling c c c without changing the modulus is valid if and only if gcd ⁡ ( c , m ) = 1 \gcd(c, m) = 1 g cd ( c , m ) = 1 .

Modular Multiplicative Inverses

The linear congruence a x ≡ 1 ( m o d m ) ax \equiv 1 \pmod m a x ≡ 1 ( mod m ) has a solution x = a − 1 x = a^{-1} x = a − 1 if and only if gcd ⁡ ( a , m ) = 1 \gcd(a, m) = 1 g cd ( a , m ) = 1 . By Bézout's identity, gcd ⁡ ( a , m ) = 1 ⟹ a x + m y = 1 \gcd(a, m) = 1 \implies ax + my = 1 g cd ( a , m ) = 1 ⟹ a x + m y = 1 , which reduces modulo m m m to a x ≡ 1 ( m o d m ) ax \equiv 1 \pmod m a x ≡ 1 ( mod m ) .

If m = p m = p m = p is prime, Fermat's Little Theorem ( a p − 1 ≡ 1 ( m o d p ) a^{p-1} \equiv 1 \pmod p a p − 1 ≡ 1 ( mod p ) for p ∤ a p \nmid a p ∤ a ) gives the inverse explicitly as a − 1 ≡ a p − 2 ( m o d p ) a^{-1} \equiv a^{p-2} \pmod p a − 1 ≡ a p − 2 ( mod p ) .

Linear Diophantine Equations: a x + b y = c ax + by = c a x + b y = c

A linear Diophantine equation seeks integer solutions ( x , y ) ∈ Z 2 (x, y) \in \mathbb{Z}^2 ( x , y ) ∈ Z 2 .

Solvability Criterion: Solutions exist if and only if d = gcd ⁡ ( a , b ) d = \gcd(a, b) d = g cd ( a , b ) divides c c c .

General Solution Formula: If ( x 0 , y 0 ) (x_0, y_0) ( x 0 ​ , y 0 ​ ) is a particular solution found via the Extended Euclidean Algorithm, all integer solutions are given by: x = x 0 + ( b d ) t , y = y 0 − ( a d ) t , t ∈ Z x = x_0 + \left(\frac{b}{d}\right)t, \quad y = y_0 - \left(\frac{a}{d}\right)t, \quad t \in \mathbb{Z} x = x 0 ​ + ( d b ​ ) t , y = y 0 ​ − ( d a ​ ) t , t ∈ Z

  • 5. Pedagogical Scenarios & Diagnosing Misconceptions
  • Classroom Context: Calendar Arithmetic (Modulo 7)

Calendar systems provide a natural anchor for modular arithmetic. Days of the week map to residue classes modulo 7: Sunday = 0, Monday = 1, ..., Saturday = 6.

Scenario: If today is Wednesday (day 3), what day of the week will it be in 500 500 500 days?

Solution: Compute ( 3 + 500 ) ( m o d 7 ) (3 + 500) \pmod 7 ( 3 + 500 ) ( mod 7 ) . Using the Division Algorithm: 503 = 71 ( 7 ) + 6 503 = 71(7) + 6 503 = 71 ( 7 ) + 6 . Since 503 ≡ 6 ( m o d 7 ) 503 \equiv 6 \pmod 7 503 ≡ 6 ( mod 7 ) , the day will be Saturday .

Misconception Analysis: Illegal Cancellation in Congruences

When asked to solve 6 x ≡ 18 ( m o d 8 ) 6x \equiv 18 \pmod 8 6 x ≡ 18 ( mod 8 ) , students frequently divide both sides by 6 and conclude x ≡ 3 ( m o d 8 ) x \equiv 3 \pmod 8 x ≡ 3 ( mod 8 ) .

Teacher Diagnostic: Dividing by c = 6 c = 6 c = 6 requires dividing the modulus by gcd ⁡ ( 6 , 8 ) = 2 \gcd(6, 8) = 2 g cd ( 6 , 8 ) = 2 , yielding x ≡ 3 ( m o d 4 ) x \equiv 3 \pmod 4 x ≡ 3 ( mod 4 ) . In the original modulo 8 system, this produces two distinct residue solutions: x ≡ 3 ( m o d 8 ) x \equiv 3 \pmod 8 x ≡ 3 ( mod 8 ) and x ≡ 7 ( m o d 8 ) x \equiv 7 \pmod 8 x ≡ 7 ( mod 8 ) . Dividing without altering the modulus omits half of the valid solution set.

Loading diagram... The Euclidean and Extended Euclidean Algorithms