Mathematics Foundations/3.2 Divisibility and Prime Numbers

Divisibility and Prime Numbers Introduction Divisibility and prime numbers are fundamental concepts in number theory. This section explores the properties of divisibility, the characteristics of prime numbers, and their significance in mathematics. Divisibility Basic Definition An integer is said to be divisible by a non-zero integer , denoted by , if there exists an integer such that . Equivalently, divides if the remainder when is divided by is zero. If does not divide , we write . Properties of Divisibility For integers , , , and : 1. for any 2. for any 3. for any 4. If and , then (transitivity) 5. If and , then for any integers and 6. If and , then 7. If and , then 8. If and , then Proof of Property 5: If and , then and for some integers and . Therefore: Since is an integer, . ∎ Divisibility Tests Several tests can determine if a number is divisible by specific values: + Common Divisibility Tests Divisor Test 2 The last digit is even (0, 2, 4, 6, or 8) 3 The sum of the digits is divisible by 3 4 The number formed by the last two digits is divisible by 4 5 The last digit is 0 or 5 6 The number is divisible by both 2 and 3 8 The number formed by the last three digits is divisible by 8 9 The sum of the digits is divisible by 9 10 The last digit is 0 11 The alternating sum of digits is divisible by 11 Example: To check if 2057 is divisible by 11, compute the alternating sum: Since the result is divisible by 11, the original number 2057 is divisible by 11. Prime Numbers Definition A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not prime is called composite. The first few prime numbers are: Note that 1 is neither prime nor composite by definition. The Fundamental Theorem of Arithmetic Theorem: Every integer greater than 1 can be expressed as a product of primes in a unique way, apart from the order of the factors. Proof Sketch: 1. Existence: We use induction on . If is prime, we're done. If is composite, then where . By the induction hypothesis, and can be expressed as products of primes, so can as well. 2. Uniqueness: Suppose where the and are primes. Then . By Euclid's lemma (see below), must divide one of the . Since is prime, we must have . After cancellation and induction, we conclude and the prime factorizations are identical up to ordering. ∎ Euclid's Lemma Lemma: If is a prime number and , then or . Proof: If , we're done. Assume . Then since is prime. By Bézout's identity, there exist integers and such that . Multiplying by : Since , we have for some integer . Substituting: Therefore, . ∎ This lemma generalizes to: if is prime and , then for at least one . Infinitude of Primes Theorem (Euclid): There are infinitely many prime numbers. Proof: Suppose, for contradiction, that there are only finitely many primes: . Consider the number: Either is prime or it's not. If is prime, then we have found a prime different from , contradicting our assumption. If is not prime, then it has a prime divisor . This must be one of the primes . But if , then , which is impossible. Therefore, our assumption is false, and there must be infinitely many primes. ∎ Distribution of Prime Numbers Prime Number Theorem The prime number theorem describes the asymptotic distribution of prime numbers. Let be the prime-counting function (the number of primes less than or equal to ). Then: This means that the probability that a randomly chosen number near is prime is approximately . Bertrand's Postulate Theorem: For every , there is at least one prime such that . This was conjectured by Joseph Bertrand in 1845 and first proved by Chebyshev in 1850. A simpler proof was later given by Ramanujan. Prime Factorization Algorithms for Finding Prime Factorization Trial Division The simplest method for finding the prime factorization of a number is trial division: 1. Try dividing by the smallest prime, 2. 2. If the division is exact, record 2 as a prime factor and replace with . 3. Repeat step 2 until is no longer divisible by 2. 4. Move to the next prime (3) and repeat the process. 5. Continue with successive primes (5, 7, 11, ...) until or until the prime being tested exceeds . Example: Find the prime factorization of 84. 84 ÷ 2 = 42, so 2 is a factor 42 ÷ 2 = 21, so 2 is a factor again 21 ÷ 3 = 7, so 3 is a factor 7 is prime Therefore, 84 = 2² × 3 × 7 Sieve of Eratosthenes The Sieve of Eratosthenes is an efficient algorithm for finding all primes up to a specified limit: 1. Create a list of consecutive integers from 2 to . 2. Let start at 2, the first prime. 3. Mark all multiples of from to as composite. 4. Find the next unmarked number after ; this is the next prime. 5. Repeat steps 3-4 until . 6. All unmarked numbers are prime. Special Types of Primes Mersenne Primes A Mersenne prime is a prime number of the form where is also prime. For to be prime, must be prime, but not all such values yield primes. The first few Mersenne primes correspond to , giving: Mersenne primes are important in the search for perfect numbers and hold the record for the largest known explicit primes. Fermat Primes A Fermat number is of the form . A Fermat prime is a Fermat number that is prime. The first few Fermat numbers are: Only through are known to be prime. Fermat numbers have connections to constructible regular polygons. Twin Primes Twin primes are pairs of primes that differ by 2, such as (3,5), (5,7), (11,13), (17,19), etc. The Twin Prime Conjecture states that there are infinitely many twin primes, but this remains an unsolved problem in number theory. Applications of Prime Numbers Prime numbers have numerous applications in various fields: Cryptography The security of many cryptographic systems, including RSA, relies on the difficulty of factoring large numbers into their prime components. A public key can be created from two large prime numbers, while factoring the product to find these primes is computationally infeasible with current technology. Hash Functions Prime numbers are used in designing hash functions for efficient data storage and retrieval. Pseudorandom Number Generation Some pseudorandom number generators use properties of prime numbers to produce sequences with good statistical properties. Cicadas Prime-numbered life cycles (13 and 17 years) help periodical cicadas minimize encounters with predators having regular life cycles. Exercises 1. Prove that if and , then . 2. Show that there are infinitely many primes of the form . 3. Prove that is irrational using the Fundamental Theorem of Arithmetic. 4. Find the prime factorization of: a) 1001 b) 2310 c) 3969 5. Prove that if and are twin primes greater than 3, then is divisible by 6. 6. Show that if is prime, then . 7. Prove that there are no prime triplets other than . 8. Use the Sieve of Eratosthenes to find all primes less than 100.