5.1 Divisibility and Prime Numbers

Divisibility and Number Types

Number theory is the mathematical foundation behind modern cryptography. Divisibility and prime numbers describe how integers relate to each other through division, and these relationships are what make encryption algorithms possible. This section covers divisibility, prime factorization, GCD, LCM, and methods for generating primes.

Fundamental Concepts of Divisibility and Prime Numbers

Divisibility occurs when one integer divides another with no remainder. You write this as $a \mid b$, which means "$a$ divides $b$." Formally, $a \mid b$ if there exists an integer $k$ such that $b = ak$.

For example, $3 \mid 12$ because $12 = 3 \times 4$. But $5 \nmid 12$ because there's no integer $k$ where $12 = 5k$.

Prime numbers have exactly two positive divisors: 1 and themselves. The first several primes are 2, 3, 5, 7, 11, 13, 17, 19. Notice that 2 is the only even prime, since every other even number is divisible by 2 and therefore has at least three divisors.

Composite numbers have more than two positive divisors, meaning they can be written as a product of two smaller positive integers. Numbers like 4, 6, 8, 9, 10, and 12 are composite. Note that 1 is neither prime nor composite; it has exactly one positive divisor.

The Fundamental Theorem of Arithmetic states that every integer greater than 1 can be represented as a product of primes in exactly one way (up to the order of the factors). This uniqueness is what makes prime factorization so useful. For instance, 84 can only be expressed as $2^2 \times 3 \times 7$. No other combination of primes will produce 84.

Prime Factorization and Its Applications

Prime factorization is the process of breaking a number down into the primes that multiply together to form it. Here's how to do it:

1. Divide the number by the smallest prime that divides it evenly.
2. Take the quotient and repeat step 1.
3. Continue until the quotient is 1.

Worked example with 60:

• $60 \div 2 = 30$
• $30 \div 2 = 15$
• $15 \div 3 = 5$
• $5 \div 5 = 1$

So $60 = 2^2 \times 3 \times 5$.

Prime factorization is the basis for computing GCDs and LCMs, simplifying fractions, and solving certain Diophantine equations (equations where you need integer solutions).

Greatest Common Divisor and Least Common Multiple

Understanding and Calculating GCD

The Greatest Common Divisor (GCD) of two integers is the largest positive integer that divides both of them. It's also called the Greatest Common Factor (GCF) or Highest Common Factor (HCF). For integers $a$ and $b$, you write it as $\gcd(a, b)$.

There are three standard methods to find the GCD:

Method 1: Listing factors. Write out all factors of each number and pick the largest one they share. This works fine for small numbers but gets tedious fast.

Method 2: Prime factorization. Factor both numbers, then multiply together only the prime factors they have in common, using the lowest power of each shared prime.

For example, to find $\gcd(48, 180)$:

• $48 = 2^4 \times 3$
• $180 = 2^2 \times 3^2 \times 5$
• Common primes: $2$ (minimum power $2$) and $3$ (minimum power $1$)
• $\gcd(48, 180) = 2^2 \times 3 = 12$

Method 3: Euclidean Algorithm. This is the most efficient approach, especially for large numbers. It works by repeated division:

1. Divide the larger number by the smaller and note the remainder.
2. Replace the larger number with the smaller number, and the smaller number with the remainder.
3. Repeat until the remainder is 0.
4. The last non-zero remainder is the GCD.

Worked example: Find $\gcd(252, 105)$.

• $252 = 105 \times 2 + 42$
• $105 = 42 \times 2 + 21$
• $42 = 21 \times 2 + 0$

The last non-zero remainder is 21, so $\gcd(252, 105) = 21$.

Key GCD properties to know:

• $\gcd(a, b) = \gcd(b, a)$
• $\gcd(a, 0) = |a|$ for any non-zero $a$
• $\gcd(a, 1) = 1$ for any integer $a$
• If $\gcd(a, b) = 1$, then $a$ and $b$ are called coprime (or relatively prime)

Least Common Multiple and Its Calculation

The Least Common Multiple (LCM) of two integers is the smallest positive integer divisible by both. For integers $a$ and $b$, you write it as $\text{lcm}(a, b)$.

Three methods to find the LCM:

Method 1: Listing multiples. Write out multiples of each number until you find the first one they share. Again, only practical for small numbers.

Method 2: Prime factorization. Factor both numbers, then multiply all prime factors using the highest power in which each appears.

For example, $\text{lcm}(48, 180)$:

• $48 = 2^4 \times 3$
• $180 = 2^2 \times 3^2 \times 5$
• Take the highest power of each prime: $2^4, 3^2, 5^1$
• $\text{lcm}(48, 180) = 2^4 \times 3^2 \times 5 = 720$

Method 3: Using the GCD. This is often the fastest route:

$\text{lcm}(a, b) = \frac{|a \times b|}{\gcd(a, b)}$

This formula captures the key relationship between LCM and GCD: the product of the LCM and GCD of two numbers equals the absolute value of their product.

$\text{lcm}(a, b) \times \gcd(a, b) = |a \times b|$

You can verify with the example above: $720 \times 12 = 8640 = |48 \times 180|$.

Common applications of LCM include finding common denominators for fractions, solving scheduling problems (e.g., "two buses leave every 12 and 18 minutes; when do they depart together again?"), and determining when periodic events coincide.

Prime Number Generation

Sieve of Eratosthenes and Prime Number Properties

The Sieve of Eratosthenes is an ancient algorithm for finding all primes up to a given limit $n$. It's named after the Greek mathematician Eratosthenes of Cyrene.

Steps of the sieve:

1. Write out all integers from 2 to $n$.
2. Starting with 2 (the smallest prime), mark all multiples of 2 greater than 2 as composite.
3. Move to the next unmarked number (which is 3). Mark all its multiples greater than 3 as composite.
4. Repeat for each successive unmarked number.
5. You can stop once you've processed all primes up to $\sqrt{n}$, because any composite number $\leq n$ must have a prime factor $\leq \sqrt{n}$.

All numbers that remain unmarked at the end are prime.

Why stop at $\sqrt{n}$? If a number $m \leq n$ is composite, then $m = a \times b$ where at least one of $a$ or $b$ is $\leq \sqrt{n}$. So by the time you've crossed off multiples of all primes up to $\sqrt{n}$, every composite number has already been marked.

The sieve runs in $O(n \log \log n)$ time with $O(n)$ space, making it very efficient for generating all primes in a range.

Important properties of prime numbers:

• There are infinitely many primes. Euclid proved this around 300 BCE. The proof works by contradiction: assume there are finitely many primes, multiply them all together and add 1, and the result isn't divisible by any prime on your list.
• Primes become less frequent as numbers grow. Among the first 100 integers, 25 are prime. Among integers near 1,000,000, roughly 1 in 14 are prime.
• The Prime Number Theorem makes this precise: the number of primes less than or equal to $n$ is approximately $\frac{n}{\ln n}$.
• In cryptography, large primes (hundreds of digits) are essential. The RSA algorithm relies on the fact that multiplying two large primes is easy, but factoring their product back into those primes is computationally infeasible.