Primes and GCD

Prime Numbers

Definition

A prime number (or simply prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Formal: An integer p > 1 is prime if its only positive divisors are 1 and p.

Examples

Prime Numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47…

Not Prime:

  • 1 (by definition, not considered prime)
  • 4 = 2 × 2 (divisible by 2)
  • 6 = 2 × 3 (divisible by 2 and 3)
  • 9 = 3 × 3 (divisible by 3)
  • 10 = 2 × 5 (divisible by 2 and 5)

Important Facts About Primes

  1. 2 is the only even prime (all other evens are divisible by 2)
  2. 2 is the smallest prime
  3. All primes except 2 are odd
  4. There are infinitely many primes (proven by Euclid)
  5. Every integer > 1 can be expressed as a product of primes (Fundamental Theorem of Arithmetic)

Composite Numbers

Definition: A composite number is a positive integer greater than 1 that is not prime (has divisors other than 1 and itself).

Examples: 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20…

Testing for Primality

Method: To check if n is prime, test if any integer from 2 to √n divides n.

Why √n? If n = a × b and a ≤ b, then a ≤ √n.

Example 1: Is 37 prime?

  • √37 ≈ 6.08
  • Test divisors: 2, 3, 4, 5, 6
  • 37 ÷ 2 = 18.5 (not divisible)
  • 37 ÷ 3 = 12.33… (not divisible)
  • 37 ÷ 5 = 7.4 (not divisible)
  • No divisors found → 37 is prime ✓

Example 2: Is 91 prime?

  • √91 ≈ 9.54
  • Test divisors: 2, 3, 4, 5, 6, 7, 8, 9
  • 91 ÷ 7 = 13 (divisible!) ✓
  • 91 = 7 × 13 → 91 is composite ✗

The Fundamental Theorem of Arithmetic

Theorem: Every integer n > 1 can be expressed uniquely (up to order) as a product of prime numbers.

This is called the prime factorization or canonical form.

Examples:

Example 1: 12

  • 12 = 2 × 6 = 2 × 2 × 3 = 2² × 3

Example 2: 60

  • 60 = 2 × 30 = 2 × 2 × 15 = 2 × 2 × 3 × 5 = 2² × 3 × 5

Example 3: 100

  • 100 = 10 × 10 = (2 × 5) × (2 × 5) = 2² × 5²

Example 4: 360

  • 360 = 2³ × 3² × 5

Finding Prime Factorization

Method: Factor Tree or Repeated Division

Example: Find the prime factorization of 84.

84
├─ 2 × 42
    ├─ 2 × 21
        ├─ 3 × 7

Answer: 84 = 2² × 3 × 7

Verification: 4 × 3 × 7 = 12 × 7 = 84 ✓

The Sieve of Eratosthenes

An ancient algorithm to find all primes up to a given number n.

Algorithm:

  1. List all numbers from 2 to n
  2. Start with 2 (first prime)
  3. Cross out all multiples of 2 (except 2 itself)
  4. Move to next uncrossed number (3), cross out its multiples
  5. Repeat until you reach √n
  6. All uncrossed numbers are prime

Example: Find all primes up to 30.

2  3  4  5  6  7  8  9  10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30

Cross out multiples of 2: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30 Cross out multiples of 3: 9, 15, 21, 27 (others already crossed) Cross out multiples of 5: 25 (others already crossed)

Primes up to 30: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

Greatest Common Divisor (GCD)

Definition

The greatest common divisor (GCD) of two integers a and b (not both zero) is the largest positive integer that divides both a and b.

Notation: gcd(a, b) or sometimes (a, b)

Examples

Example 1: gcd(12, 18)

  • Divisors of 12: 1, 2, 3, 4, 6, 12
  • Divisors of 18: 1, 2, 3, 6, 9, 18
  • Common divisors: 1, 2, 3, 6
  • Greatest common divisor: 6

Example 2: gcd(15, 25)

  • Divisors of 15: 1, 3, 5, 15
  • Divisors of 25: 1, 5, 25
  • Common divisors: 1, 5
  • Greatest common divisor: 5

Example 3: gcd(7, 13)

  • Divisors of 7: 1, 7
  • Divisors of 13: 1, 13
  • Common divisors: 1
  • Greatest common divisor: 1 (they are relatively prime or coprime)

Relatively Prime (Coprime)

Definition: Two integers a and b are relatively prime (or coprime) if gcd(a, b) = 1.

Examples:

  • gcd(8, 15) = 1 → relatively prime ✓
  • gcd(9, 16) = 1 → relatively prime ✓
  • gcd(6, 9) = 3 → NOT relatively prime ✗

Properties of GCD

  1. gcd(a, b) = gcd(b, a) (commutative)
  2. gcd(a, 0) = |a| for a ≠ 0
  3. gcd(a, 1) = 1 for any a
  4. gcd(a, a) = |a|
  5. If d = gcd(a, b), then gcd(a/d, b/d) = 1
  6. gcd(a, b) × lcm(a, b) = |a × b|

Finding GCD Using Prime Factorization

Method: Express both numbers as products of primes, then take the product of common primes with the smallest exponents.

Example 1: gcd(60, 84)

Step 1: Prime factorization

  • 60 = 2² × 3 × 5
  • 84 = 2² × 3 × 7

Step 2: Common primes with minimum exponents

  • Common primes: 2, 3
  • 2: min(2, 2) = 2
  • 3: min(1, 1) = 1
  • 5 and 7 are not common

Step 3: gcd(60, 84) = 2² × 3 = 4 × 3 = 12

Example 2: gcd(48, 180)

  • 48 = 2⁴ × 3
  • 180 = 2² × 3² × 5
  • Common primes: 2, 3
  • 2: min(4, 2) = 2
  • 3: min(1, 2) = 1
  • gcd(48, 180) = 2² × 3 = 12

Euclidean Algorithm

A much more efficient method for finding GCD, especially for large numbers.

Algorithm: Based on the fact that gcd(a, b) = gcd(b, a mod b)

Steps:

  1. If b = 0, return a
  2. Otherwise, compute r = a mod b
  3. Set a = b, b = r
  4. Repeat from step 1

Example 1: gcd(48, 18)

gcd(48, 18)
= gcd(18, 48 mod 18)
= gcd(18, 12)         [48 = 18×2 + 12]
= gcd(12, 18 mod 12)
= gcd(12, 6)          [18 = 12×1 + 6]
= gcd(6, 12 mod 6)
= gcd(6, 0)           [12 = 6×2 + 0]
= 6

Answer: gcd(48, 18) = 6

Example 2: gcd(252, 105)

gcd(252, 105)
= gcd(105, 252 mod 105)
= gcd(105, 42)        [252 = 105×2 + 42]
= gcd(42, 105 mod 42)
= gcd(42, 21)         [105 = 42×2 + 21]
= gcd(21, 42 mod 21)
= gcd(21, 0)          [42 = 21×2 + 0]
= 21

Answer: gcd(252, 105) = 21

Example 3: gcd(1071, 462)

gcd(1071, 462)
= gcd(462, 147)       [1071 = 462×2 + 147]
= gcd(147, 21)        [462 = 147×3 + 21]
= gcd(21, 0)          [147 = 21×7 + 0]
= 21

Extended Euclidean Algorithm

Not only finds gcd(a, b) but also finds integers x and y such that:

ax + by = gcd(a, b)

This is called Bézout’s Identity.

Example: Find gcd(30, 12) and express it as 30x + 12y.

Using Euclidean Algorithm:

30 = 12 × 2 + 6
12 = 6 × 2 + 0

gcd(30, 12) = 6

Working backwards:

6 = 30 - 12 × 2
6 = 30(1) + 12(-2)

Answer: gcd(30, 12) = 6 = 30(1) + 12(-2)

Verification: 30(1) + 12(-2) = 30 - 24 = 6 ✓

GCD of More Than Two Numbers

Property: gcd(a, b, c) = gcd(gcd(a, b), c)

Example: gcd(12, 18, 24)

Step 1: gcd(12, 18) = 6 Step 2: gcd(6, 24) = 6

Answer: gcd(12, 18, 24) = 6

Applications of Primes and GCD

Application 1: Simplifying Fractions

To simplify a/b, divide both by gcd(a, b).

Example: Simplify 48/60

  • gcd(48, 60) = 12
  • 48/60 = (48÷12)/(60÷12) = 4/5

Application 2: Cryptography

RSA encryption uses the fact that large primes are hard to factorize.

Application 3: Hash Tables

For best performance, table size should be prime.

Application 4: Scheduling Problems

If two events occur every a and b units, they coincide every lcm(a, b) units.

Theorems About Primes

Theorem 1: Infinitude of Primes

Theorem: There are infinitely many prime numbers.

Proof (by Euclid): Suppose there are finitely many primes: p₁, p₂, …, pₙ. Consider N = p₁ × p₂ × … × pₙ + 1. N is not divisible by any of p₁, …, pₙ (remainder 1). So either N is prime, or has a prime factor not in our list. Contradiction! Therefore, there are infinitely many primes. ✓

Theorem 2: Prime Number Theorem

The number of primes less than n is approximately n/ln(n).

Theorem 3: Fundamental Theorem of Arithmetic

Every integer > 1 has a unique prime factorization (up to order).

Key Points for Exams

  1. 2 is the only even prime
  2. To test primality, check divisors up to √n
  3. Euclidean algorithm is more efficient than prime factorization for GCD
  4. gcd(a, b) × lcm(a, b) = a × b
  5. Relatively prime means gcd = 1
  6. Every integer has unique prime factorization
  7. Use factor trees for prime factorization
  8. Sieve of Eratosthenes finds all primes up to n
  9. Bézout’s Identity: ax + by = gcd(a, b) has integer solutions
  10. Practice Euclidean algorithm - it’s fast and commonly tested

Practice Problems

  1. Is 89 prime? (check divisors up to √89)

  2. Find the prime factorization of 360.

  3. Find gcd(126, 84) using: a) Prime factorization method b) Euclidean algorithm

  4. Are 35 and 48 relatively prime?

  5. Express gcd(45, 30) in the form 45x + 30y.

  6. Find all primes between 50 and 70.

  7. Find gcd(12, 18, 24, 30).

  8. Simplify 144/180 using GCD.

  9. Prove that if p is prime and p | ab, then p | a or p | b.

  10. Find the smallest number divisible by 2, 3, 5, and 7.