Section 5.2: Prime Numbers

5.2 Outline

  1. Divisibility
    1. definition
      1. divisor
      2. factor
      3. divides
      4. multiple
    2. number of divisors
      1. divisibility rule for 2
      2. divisibility rule for 3
      3. rules of divisibility for 1-12
    3. finding primes
      1. definitions
        1. prime number
        2. composite number
      2. sieve of Eratosthenes
    4. prime factorization
      1. factoring
      2. prime factorization
      3. fundamental theorem of arithmetic
      4. canonical form
      5. greatest common factor
        1. definition
        2. procedure for finding
        3. flowchart
      6. relatively prime
      7. least common multiple
        1. definition
        2. procedure for finding
        3. flowchart
    5. in pursuit of primes
      1. Mersenne prime
      2. largest known prime
      3. GIMPS
    6. infinitude of primes
      1. There is no largest prime.

5.2 Essential Ideas

This essential idea of this section is important to many concepts in mathematics, and that is the idea of a prime number: A prime number is a counting number that has exactly two divisors. A counting number that has more than two divisors is called a composite number.

This section begins with the notion of divisibility. Table 5.1 lists rules of divisibility for numbers from 1 to 12. In practice, however, we are looking for a prime factorization, so we are looking for prime divisors.
2 if the last digit is divisible by 2.
3 if the sum of the digits is divisible by 3.
5 if the last digit is 0 or 5.

We use prime numbers to find the prime factorization of numbers, and then use this idea to find the greatest common factor and the least common multiple. The greatest common factor is used to reduce fractions and the least common multiple is used to find the common denominator when adding or subtracting fractions. Some large primes are found and some possible formulas for primes considered, and then the section concludes by proving that there are infinitely many primes.