Primes and factorization, divisibility rules, GCD and LCM, modular arithmetic, the Euclidean algorithm, and Diophantine equations — the complete foundation.
A prime number is a natural number greater than 1 whose only divisors are 1 and itself. Every other integer greater than 1 is composite — it factors into smaller primes.
Fundamental Theorem of Arithmetic
Every integer n > 1 has a unique prime factorization: n = p₁^a₁ × p₂^a₂ × ⋯ × pₖ^aₖ, where p₁ < p₂ < ⋯ < pₖ are primes and each aᵢ ≥ 1.
2, 3, 5, 7, 11, 13, 17, 19, 23, 29. The only even prime is 2 — all other even numbers are divisible by 2 and therefore composite.
To test if n is prime, check divisibility by all primes up to √n. If none divide n evenly, n is prime. For n = 101: √101 ≈ 10.05, test 2, 3, 5, 7 — none work, so 101 is prime.
Use a factor tree or repeated division. Example: 360 = 2 × 180 = 2 × 2 × 90 = 4 × 9 × 10 = 2³ × 3² × 5. Always write in standard form with primes in ascending order.
An ancient algorithm for finding all primes up to N: write out integers 2 through N, mark 2 as prime and cross out all multiples of 2, then mark the next unmarked number as prime and cross out its multiples, and repeat until done.
Blue = prime, gray = composite (primes up to 31 shown)
Divisibility rules let you quickly determine whether an integer divides another without performing long division. These are essential for rapid factoring.
| Divisor | Rule | Example |
|---|---|---|
| 2 | Last digit is even (0, 2, 4, 6, 8) | 1,348 → last digit 8 → divisible by 2 |
| 3 | Sum of digits divisible by 3 | 471 → 4+7+1=12 → 12÷3=4 ✓ |
| 4 | Last two digits divisible by 4 | 1,932 → 32÷4=8 ✓ |
| 5 | Last digit is 0 or 5 | 2,035 → last digit 5 ✓ |
| 6 | Divisible by both 2 and 3 | 714 → even and 7+1+4=12 ✓ |
| 7 | Double last digit, subtract from rest; repeat until clear | 343 → 34−6=28 → 2−16=−14 → divisible by 7 ✓ |
| 8 | Last three digits divisible by 8 | 5,120 → 120÷8=15 ✓ |
| 9 | Sum of digits divisible by 9 | 2,718 → 2+7+1+8=18 ✓ |
| 10 | Last digit is 0 | 3,450 → last digit 0 ✓ |
| 11 | Alternating digit sum divisible by 11 | 2,728 → 2−7+2−8=−11 ✓ |
The largest positive integer that divides both a and b. Also called the Greatest Common Factor (GCF) or Highest Common Factor (HCF).
By prime factorization: write both numbers in prime factored form and take the minimum exponent for each shared prime.
The smallest positive integer that is divisible by both a and b. Essential for adding fractions with different denominators.
By prime factorization: take the maximum exponent for each prime that appears in either factorization.
Key Identity
This identity lets you find LCM instantly once you have GCD: LCM(a, b) = (a × b) / GCD(a, b).
Extend the prime factorization method: for GCD take the minimum exponent across all three; for LCM take the maximum.
The Euclidean Algorithm is the most efficient method for computing GCD, especially for large numbers where prime factorization is impractical. It relies on one key fact:
Core Principle
Repeatedly replace the larger number with the remainder of dividing the two numbers. Stop when the remainder is 0 — the previous remainder is the GCD.
Divide a by b
Write a = q × b + r where 0 ≤ r < b. This is the Division Algorithm.
Replace: set a ← b, b ← r
The GCD of the original pair equals the GCD of this new pair.
Repeat until remainder = 0
When r = 0, the current value of b is GCD(original a, original b).
Modular arithmetic generalizes the idea of remainders. We say a ≡ b (mod n) (read: a is congruent to b modulo n) if n divides a − b — equivalently, a and b leave the same remainder when divided by n.
If a ≡ b (mod n) and c ≡ d (mod n), then a + c ≡ b + d (mod n). Example: 14 + 9 mod 5. 14 ≡ 4, 9 ≡ 4, so sum ≡ 8 ≡ 3 (mod 5). Check: 23 mod 5 = 3 ✓
If a ≡ b (mod n) and c ≡ d (mod n), then ac ≡ bd (mod n). Example: 7 × 11 mod 6. 7 ≡ 1, 11 ≡ 5, so product ≡ 5 (mod 6). Check: 77 mod 6 = 5 ✓
Use repeated squaring. To find 3⁸ mod 7: 3²=9≡2, 3⁴≡4, 3⁸≡16≡2 (mod 7). This is dramatically faster than computing 3⁸=6561 then reducing.
The inverse of a mod n is x such that ax ≡ 1 (mod n). It exists iff GCD(a,n)=1. Example: inverse of 3 mod 7 is 5, since 3×5=15≡1 (mod 7). Found via Extended Euclidean Algorithm.
The integers mod n are partitioned into n residue classes: [0], [1], [2], …, [n−1]. Every integer belongs to exactly one class. Arithmetic mod n works within these classes.
| Class mod 5 | Members (sample) |
|---|---|
| [0] | …, −10, −5, 0, 5, 10, 15, … |
| [1] | …, −9, −4, 1, 6, 11, 16, … |
| [2] | …, −8, −3, 2, 7, 12, 17, … |
| [3] | …, −7, −2, 3, 8, 13, 18, … |
| [4] | …, −6, −1, 4, 9, 14, 19, … |
A Diophantine equation is any equation for which we seek only integer solutions. The simplest and most important type is the linear Diophantine equation ax + by = c.
If GCD(a, b) does not divide c, there are no integer solutions. Example: 6x + 10y = 9 has no solution because GCD(6,10) = 2 does not divide 9.
If (x₀, y₀) is one particular solution to ax + by = c, then the complete family of integer solutions is:
There are infinitely many solutions — each integer k gives a different solution pair.
To find a particular solution, use the Extended Euclidean Algorithm to express GCD(a, b) = sa + tb for integers s and t (called Bezout coefficients). Then scale by c / GCD(a, b).
GCD(35, 15): 35 = 2×15 + 5, then 15 = 3×5 + 0 → GCD = 5
Back-substitute: 5 = 35 − 2×15 → s=1, t=−2
So 35(1) + 15(−2) = 5 (Bezout identity)
RSA encryption uses large primes p and q. The public key is n = pq. Security relies on the difficulty of factoring n. Decryption uses the modular inverse of the encryption exponent, found via the Extended Euclidean Algorithm.
ISBN-13 check digits use mod 10. Credit card validation (Luhn algorithm) uses mod 10. Many hash functions rely on arithmetic modulo a large prime. Modular arithmetic prevents overflow while preserving structure.
The day-of-week for any date uses modular arithmetic mod 7. The Chinese Remainder Theorem solves scheduling problems — e.g., finding when two cyclic events next coincide — by combining congruences with coprime moduli.
Find all prime factors of 1,260.
1,260 ÷ 2 = 630
630 ÷ 2 = 315
315 ÷ 3 = 105
105 ÷ 3 = 35
35 ÷ 5 = 7
7 is prime.
1,260 = 2² × 3² × 5 × 7
Sum of exponents: 2+2+1+1 = 6, so 1,260 has (2+1)(2+1)(1+1)(1+1) = 36 divisors.
Find GCD(299, 221).
299 = 1 × 221 + 78 → GCD(299,221) = GCD(221,78)
221 = 2 × 78 + 65 → GCD(221,78) = GCD(78,65)
78 = 1 × 65 + 13 → GCD(78,65) = GCD(65,13)
65 = 5 × 13 + 0 → GCD(65,13) = 13
GCD(299, 221) = 13
Verify: 299 = 23 × 13 ✓ 221 = 17 × 13 ✓
By Fermat's Little Theorem: 7^(11−1) = 7¹⁰ ≡ 1 (mod 11)
50 = 5 × 10 + 0, so 7⁵⁰ = (7¹⁰)⁵ ≡ 1⁵ = 1 (mod 11)
7⁵⁰ ≡ 1 (mod 11)
Without the theorem, repeated squaring: 7¹≡7, 7²≡5, 7⁴≡3, 7⁸≡9, 7¹⁰≡7⁸×7²≡9×5=45≡1 ✓
Step 1: GCD(15, 21) = 3. Does 3 | 9? Yes (9 = 3×3). Solutions exist.
Step 2: Simplify ÷3: 5x + 7y = 3
Step 3: Find GCD(5, 7) = 1 = 5(3) + 7(−2). Verify: 15−14=1 ✓
Step 4: Multiply by 3: 5(9) + 7(−6) = 3. Particular solution: x₀=9, y₀=−6.
Step 5: General solution (d=1): x = 9 + 7k, y = −6 − 5k
x = 9 + 7k, y = −6 − 5k for any integer k
k=0: (9,−6). Check: 15(9)+21(−6)=135−126=9 ✓ k=−1: (2,−1). Check: 30−21=9 ✓
Find x such that: x ≡ 1 (mod 3), x ≡ 4 (mod 5), x ≡ 6 (mod 7)
N = 3 × 5 × 7 = 105
N₁=35, N₂=21, N₃=15
Find inverses: 35 mod 3 = 2, inv(2) mod 3 = 2 (since 2×2=4≡1)
21 mod 5 = 1, inv(1) mod 5 = 1
15 mod 7 = 1, inv(1) mod 7 = 1
x = 1×35×2 + 4×21×1 + 6×15×1 = 70 + 84 + 90 = 244
244 mod 105 = 34
x ≡ 34 (mod 105)
Verify: 34÷3=11r1 ✓ 34÷5=6r4 ✓ 34÷7=4r6 ✓
Check divisibility by 8:
Last three digits: 392. Is 392 ÷ 8 = 49? Yes. → 7,392 is divisible by 8.
Check divisibility by 9:
Sum of digits: 7+3+9+2 = 21. Is 21 ÷ 9 = 2.33...? No. → 7,392 is NOT divisible by 9.
7,392 is divisible by 8 but not by 9.
7,392 = 8 × 924 = 2⁵ × 3 × 7 × 11. The factor 9 = 3² requires two factors of 3, but there is only one.
A prime number is a natural number greater than 1 that has exactly two divisors: 1 and itself. To test if n is prime, check divisibility by all primes up to √n. If none divide evenly into n, then n is prime. For example, to test 97: √97 ≈ 9.8, so test primes 2, 3, 5, 7. None divide 97 evenly, so 97 is prime. The first ten primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29. Note that 1 is not prime — it has only one divisor.
The Fundamental Theorem of Arithmetic states that every integer greater than 1 can be represented uniquely as a product of prime numbers, up to the order of the factors. This unique representation is called the prime factorization. For example, 360 = 2³ × 3² × 5. No other combination of primes multiplied together gives 360. This theorem is the foundation of number theory — it tells us that primes are the 'building blocks' of all integers.
To find GCD (Greatest Common Divisor) and LCM (Least Common Multiple) using prime factorization: Step 1 — write the prime factorization of each number. Step 2 — for GCD, take the minimum exponent of each shared prime factor. Step 3 — for LCM, take the maximum exponent of each prime factor that appears in either number. Example: GCD(72, 120): 72 = 2³ × 3², 120 = 2³ × 3 × 5. GCD = 2³ × 3¹ = 24. LCM = 2³ × 3² × 5 = 360. Key identity: GCD(a, b) × LCM(a, b) = a × b.
Modular arithmetic is a system where numbers wrap around after reaching a modulus n, like a clock. The notation a ≡ b (mod n) means that a and b have the same remainder when divided by n — equivalently, n divides (a − b). For example, 17 ≡ 2 (mod 5) because 17 = 3 × 5 + 2 and 2 = 0 × 5 + 2, both leaving remainder 2. Modular arithmetic supports addition, subtraction, and multiplication: if a ≡ b and c ≡ d (mod n), then a + c ≡ b + d (mod n) and a × c ≡ b × d (mod n).
The Euclidean Algorithm finds GCD(a, b) by repeatedly applying the division algorithm: GCD(a, b) = GCD(b, a mod b) until the remainder is 0. The last nonzero remainder is the GCD. Example: GCD(252, 105). Step 1: 252 = 2 × 105 + 42, so GCD(252, 105) = GCD(105, 42). Step 2: 105 = 2 × 42 + 21, so GCD(105, 42) = GCD(42, 21). Step 3: 42 = 2 × 21 + 0, so GCD(42, 21) = 21. Therefore GCD(252, 105) = 21. This algorithm is far more efficient than factoring large numbers.
Key divisibility rules: A number is divisible by 2 if its last digit is even. By 3 if the sum of its digits is divisible by 3. By 4 if the last two digits form a number divisible by 4. By 5 if the last digit is 0 or 5. By 6 if it is divisible by both 2 and 3. By 8 if the last three digits form a number divisible by 8. By 9 if the sum of its digits is divisible by 9. By 10 if the last digit is 0. By 11 if the alternating sum of digits (left to right) is divisible by 11. Example: 132 — alternating sum = 1 − 3 + 2 = 0, which is divisible by 11, so 132 ÷ 11 = 12.
A Diophantine equation is a polynomial equation for which only integer solutions are sought. The linear Diophantine equation ax + by = c has integer solutions if and only if GCD(a, b) divides c. To find solutions: Step 1 — verify GCD(a, b) | c. Step 2 — use the Extended Euclidean Algorithm to write GCD(a, b) = sa + tb for integers s and t. Step 3 — multiply through by c / GCD(a, b) to get a particular solution (x₀, y₀). Step 4 — the general solution is x = x₀ + (b/d)k, y = y₀ − (a/d)k for all integers k, where d = GCD(a, b). Example: 3x + 5y = 1 — GCD(3,5)=1 divides 1, and 3(2) + 5(−1) = 1, so one solution is x=2, y=−1.
Euler's totient function φ(n) counts the number of integers from 1 to n that are coprime to n (share no common factor with n other than 1). For a prime p: φ(p) = p − 1, since all integers from 1 to p−1 are coprime to p. For prime powers: φ(pᵏ) = pᵏ − pᵏ⁻¹. The function is multiplicative: φ(mn) = φ(m)φ(n) when GCD(m,n) = 1. Euler's theorem states: if GCD(a,n) = 1, then aᶲ⁽ⁿ⁾ ≡ 1 (mod n). This is the foundation of RSA encryption — the most widely used public-key cryptosystem in the world.
Two integers a and b are coprime (or relatively prime) if their greatest common divisor is 1 — they share no common prime factors. For example, 8 and 15 are coprime: 8 = 2³ and 15 = 3 × 5 share no prime factors, so GCD(8, 15) = 1. Coprimality is essential for many theorems — the Chinese Remainder Theorem guarantees unique solutions when moduli are pairwise coprime, and fractions are in lowest terms when numerator and denominator are coprime. Note: two numbers can be coprime without either being prime. For instance, 4 and 9 are coprime because GCD(4, 9) = 1.
The Chinese Remainder Theorem (CRT) states: if n₁, n₂, …, nₖ are pairwise coprime positive integers, then for any integers a₁, a₂, …, aₖ, the system x ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂), …, x ≡ aₖ (mod nₖ) has a unique solution modulo N = n₁ × n₂ × ⋯ × nₖ. Example: solve x ≡ 2 (mod 3) and x ≡ 3 (mod 5). N = 15. Try x = 8: 8 = 2×3 + 2 ✓ and 8 = 1×5 + 3 ✓. The unique solution mod 15 is x ≡ 8 (mod 15). The CRT is used in cryptography, computer science, and competition mathematics.
Interactive problems with step-by-step solutions and private tutoring — free to try.
Start Practicing Free