Foundations
Number Theory Fundamentals
Difficulty: Intermediate
Why are hash table sizes almost always prime? Why does the Euclidean algorithm for gcd run in O(log(min(a, b))) time despite using only subtraction or remainders? Number Theory Fundamentals is the branch of math that answers these...
Number Theory Fundamentals
Why are hash table sizes almost always prime? Why does the Euclidean algorithm for gcd run in O(log(min(a, b))) time despite using only subtraction or remainders? Number Theory Fundamentals is the branch of math that answers these questions and quietly powers a surprising amount of practical software, from hashing and cryptography to scheduling and competitive programming shortcuts.
This lesson introduces the core building blocks. You will study prime numbers and how to test primality efficiently, the divisibility relation and quick rules for spotting divisors, GCD (greatest common divisor) and LCM (least common multiple) with the identity lcm(a, b) = a * b / gcd(a, b), and the Euclidean algorithm for computing gcd in logarithmic time. You will also do prime factorization by trial division (O(sqrt(n))) and see how factorizations make divisor counting, simplification, and periodicity arguments straightforward.
This lesson builds on Discrete Mathematics Basics, where you learned how to reason precisely about sets, relations, and logical claims. Number theory uses that same proof-style reasoning, but applied to the integers and their multiplicative structure.
With primes, gcd, and factorization in your toolkit, you will be ready to take the premium step into Modular Arithmetic, where you will reuse all of these ideas to work with mod, modular inverses, and Fermat's Little Theorem.
Prerequisites:
Discrete Mathematics BasicsTopics:
What You'll Learn
By the end of this lesson, you will be able to:
Define prime and composite numbers and test whether a small number is prime.
Apply divisibility rules and count the divisors of a given number.
Compute the GCD of two numbers using the Euclidean algorithm and explain why it works.
Compute the LCM of two numbers using the GCD relationship LCM(a, b) = a * b / GCD(a, b).
Perform prime factorization by trial division and explain its O(sqrt(n)) complexity.
Identify number-theoretic patterns in algorithm and interview problems.
Why This Matters
01
Prime numbers are the backbone of hash functions and cryptographic algorithms -- understanding them helps you reason about collision rates and security.
02
The Euclidean algorithm for GCD is one of the oldest and most efficient algorithms in existence, running in O(log(min(a, b))) time, and appears in problems ranging from fraction simplification to scheduling.
03
Prime factorization lets you decompose problems into simpler parts: computing LCM, counting divisors, and analyzing periodicity all rely on factorization.
04
Number theory problems are a staple of coding interviews and competitive programming -- recognizing when a problem has a number-theoretic shortcut can turn an O(n) brute force into an O(sqrt(n)) or O(log n) solution.
Key Terms
8 terms you'll encounter in this lesson
Prime Number
A natural number greater than 1 that has exactly two factors: 1 and itself. Examples: 2, 3, 5, 7, 11. The number 2 is the only even prime.
Composite Number
A natural number greater than 1 that has more than two factors. For example, 12 = 2 x 2 x 3 has factors 1, 2, 3, 4, 6, and 12.
Divisor (Factor)
An integer d is a divisor of n if n mod d = 0. For example, the divisors of 12 are 1, 2, 3, 4, 6, and 12.
GCD (Greatest Common Divisor)
The largest positive integer that divides both a and b. Also called the HCF (highest common factor). For example, GCD(12, 18) = 6.
LCM (Least Common Multiple)
The smallest positive integer that is a multiple of both a and b. Related to GCD by: LCM(a, b) = a * b / GCD(a, b). For example, LCM(4, 6) = 12.
Euclidean Algorithm
An efficient algorithm to compute GCD(a, b) by repeatedly replacing the larger number with the remainder: GCD(a, b) = GCD(b, a mod b), until the remainder is 0. Runs in O(log(min(a, b))) time.
Prime Factorization
Expressing a number as a product of prime factors. For example, 60 = 2^2 x 3 x 5. By the Fundamental Theorem of Arithmetic, every integer > 1 has a unique prime factorization.
Sieve of Eratosthenes
An algorithm that finds all primes up to n by iteratively marking multiples of each prime as composite. Runs in O(n log log n) time and O(n) space.
Related Problems
Coding problems that put this lesson's concepts into practice
Heads Up
Common misconceptions to watch out for
"1 is a prime number"
By definition, a prime must have exactly two distinct factors (1 and itself). The number 1 has only one factor (itself), so it is neither prime nor composite. Excluding 1 from primes preserves the uniqueness of prime factorization.
"To check if n is prime, I must test all numbers from 2 to n-1"
You only need to test divisors up to sqrt(n). If n has a factor larger than sqrt(n), it must also have a corresponding factor smaller than sqrt(n). This reduces primality testing from O(n) to O(sqrt(n)).
"GCD(a, 0) is 0"
GCD(a, 0) = a, not 0. Every integer divides 0 (since 0 = k x 0 for any k), so the greatest common divisor of a and 0 is a itself. This is also the base case of the Euclidean algorithm.
"LCM(a, b) = a * b always"
LCM(a, b) = a * b only when GCD(a, b) = 1 (i.e., a and b are coprime). In general, LCM(a, b) = a * b / GCD(a, b). For example, LCM(4, 6) = 24 / 2 = 12, not 24.