2.2 Prime numbers and factorization

Prime numbers are the building blocks of arithmetic. They're special numbers that can only be divided evenly by 1 and themselves. Understanding prime numbers is crucial for grasping the fundamentals of additive number theory.

The Fundamental Theorem of Arithmetic states that every number can be uniquely broken down into prime factors. This concept is key to many aspects of number theory, including finding common divisors and multiples, which are essential in additive combinatorics.

Prime Numbers and Their Properties

Definition and Characteristics

Top images from around the web for Definition and Characteristics

• 

  Prime number - Wikipedia View original

  Is this image relevant?

• 

  Prime numbers - Wikiversity View original

  Is this image relevant?

• 

  The Pattern of Prime Numbers View original

  Is this image relevant?

• 

  Prime number - Wikipedia View original

  Is this image relevant?

• 

  Prime numbers - Wikiversity View original

  Is this image relevant?

1 of 3

Top images from around the web for Definition and Characteristics

• 

  Prime number - Wikipedia View original

  Is this image relevant?

• 

  Prime numbers - Wikiversity View original

  Is this image relevant?

• 

  The Pattern of Prime Numbers View original

  Is this image relevant?

• 

  Prime number - Wikipedia View original

  Is this image relevant?

• 

  Prime numbers - Wikiversity View original

  Is this image relevant?

1 of 3

• Define prime numbers as positive integers greater than 1 that have exactly two positive divisors: 1 and itself
• Exclude the number 1 from being considered a prime number because it only has one positive divisor
• Identify 2 as the smallest prime number and the only even prime number
• Recognize that two distinct prime numbers are always coprime, meaning their greatest common divisor is 1
• Understand that the product of any number of primes is always a composite number, with the exception of the empty product which equals 1

Fundamental Theorem of Arithmetic

• State the Fundamental Theorem of Arithmetic, which asserts that every positive integer greater than 1 can be represented uniquely as a product of prime numbers, up to the order of the factors
• Use the Fundamental Theorem of Arithmetic to express the prime factorization of a number using exponents, where each prime factor is raised to the power of the number of times it appears in the factorization
• Apply the Fundamental Theorem of Arithmetic to find the greatest common divisor (GCD) of two numbers by comparing their prime factorizations and taking the product of the common prime factors with the minimum exponent for each prime (12 and 18)
• Utilize the Fundamental Theorem of Arithmetic to determine the least common multiple (LCM) of two numbers by comparing their prime factorizations and taking the product of all prime factors with the maximum exponent for each prime (24 and 36)

Primality Testing Methods

Basic and Classical Methods

• Describe trial division as the most basic method for testing primality, where a number is divided by all primes up to its square root to check for divisibility
• Explain the Sieve of Eratosthenes as an ancient algorithm for finding all prime numbers up to a given limit by iteratively marking the multiples of each prime, starting with 2
• Introduce Fermat's little theorem, which states that if p is prime and a is not divisible by p, then a^(p-1) ≡ 1 (mod p), and its application in the Fermat primality test

Advanced and Modern Methods

• Discuss the Miller-Rabin primality test as a probabilistic algorithm that determines whether a given number is likely to be prime based on the properties of strong pseudoprimes, offering improved accuracy compared to the Fermat primality test
• Present the AKS primality test, named after its inventors Agrawal, Kayal, and Saxena, as a deterministic algorithm that determines whether a number is prime in polynomial time using the concept of cyclotomic polynomials
• Compare the efficiency and reliability of various primality testing methods, considering factors such as computational complexity, accuracy, and the size of the numbers being tested (small primes, large primes)

Fundamental Theorem of Arithmetic

Prime Factorization

• Restate the Fundamental Theorem of Arithmetic, which guarantees that every positive integer greater than 1 can be uniquely represented as a product of prime numbers, up to the order of the factors
• Describe the process of finding the prime factorization of a number by dividing it by the smallest prime that divides it evenly and repeating this process with the quotient until the quotient becomes 1
• Represent the prime factorization of a number using exponents, where each prime factor is raised to the power of the number of times it appears in the factorization (360 = 2^3 × 3^2 × 5)

Applications of Prime Factorization

• Use prime factorizations to find the greatest common divisor (GCD) of two numbers by comparing their factorizations and taking the product of the common prime factors with the minimum exponent for each prime (GCD of 24 and 36 is 2^2 × 3 = 12)
• Determine the least common multiple (LCM) of two numbers using their prime factorizations by taking the product of all prime factors with the maximum exponent for each prime (LCM of 24 and 36 is 2^3 × 3^2 = 72)
• Solve problems involving divisibility, factorization, and number theory using the Fundamental Theorem of Arithmetic (finding the number of factors of a given integer, determining the sum of the factors of a number)

Prime Number Distribution

Prime Number Theorem

• State the Prime Number Theorem, which asserts that the number of primes less than or equal to a given number n, denoted as π(n), is asymptotically equal to n/ln(n) as n approaches infinity
• Interpret the Prime Number Theorem as providing an estimate for the density of prime numbers, showing that the probability of a randomly chosen number near n being prime is approximately 1/ln(n)
• Discuss the significance of the Prime Number Theorem in understanding the distribution of prime numbers and its implications for various areas of mathematics (cryptography, number theory)

Related Conjectures and Functions

• Introduce the Riemann hypothesis, a famous unsolved problem in mathematics, which states that the non-trivial zeros of the Riemann zeta function all have a real part equal to 1/2, and its potential impact on providing a more precise estimate for the distribution of prime numbers
• Define the Chebyshev function ϑ(x) as the sum of the natural logarithms of all prime numbers less than or equal to x and explain its use in studying the distribution of prime numbers and its relation to the Prime Number Theorem
• Present the Erdős–Kac theorem, which describes the distribution of the number of distinct prime factors of a randomly chosen integer as asymptotically normal with a mean and variance of log log n, where n is the chosen integer (distribution of prime factors for integers near 1,000,000)