Elementary Number Theory

• We say an integer p divides an integer q if q = p x r, for some integer r

• Numbers that divide q (p) are called divisors (or factors) of q

• Prime number = 1 and p are the ONLY divisors of p

  • ex; 2, 3, 5, 7, 11, 13, 19, 23…

Greatest Common Factor (GCF)

• ex: (20,42)

  • 20 = 1, 2, 4, 5, 10, 20

  • 42 = 1, 2, 3, 6, 7, 14, 21, 42

  • GCF = 2

• ex: (9,72)

  • 9 = 1, 3, 9

  • 72 = 1, 2, 3, 4, 8, 9 …

  • GCF = 9

Prime Factorization

• Every integer greater than 1 is either prime itself or is the product of prime numbers

  • ex; 8 = 2 × 4 = 2 × 2 × 2 = 2³

  • 17 = 17; just prime

  • 100 = 2 × 50 = 2 × 2 × 25 = 2 × 2 × 5 × 5 = 2² x 5²