The user-friendly version of this content is available here.

The following content is copyright (c) 2009-2013 by Goods of the Mind, LLC.

This essential trains for: SAT-I, GMAT, AMC-8, Math Kangaroo 5-6, Math Kangaroo 7-8.

The fundamental theorem of arithmetic and related facts:

A natural number is either prime or composite.

A natural number is prime if it divides evenly only into 1 and itself. It has only two factors (divisors).

A natural number is composite if it divides evenly into numbers other than 1 and itself. It has more than two factors (divisors).

Any composite number can be obtained by multiplying several prime numbers together. The primes need not be different from one another (i.e. distinct).

The most useful way of writing the prime factorization of a number N is:

equation

where:

equation

are M prime numbers ordered increasingly, and

equation

are M positive integers.

Notice that the primes are all distinct in the ordered list, which means that the exponents reflect exactly how many times each prime occurs in the factorization.

Examples: (Note that if the exponent is equal to one, then it is not written explicitly.)

equation

equation

Important facts:

1 is neither prime nor composite since it does not satisfy either definition. It is an improper prime - the only number in this category.

2 is the only even prime.

2 is the smallest prime.

There is no largest prime. (this is a theorem that we prove in another lesson)

1 is a divisor of any integer.

equation

0 is a multiple of any integer.

equation

Algorithm for finding prime factors:

Take the first prime (2) and divide by it as many times as the integer division is possible (remainder is zero).

Go to the second prime (3) and repeat step 2.

Continue with increasingly larger primes.

equation

equation

equation

equation

equation

equation

Test for primality:

A simple algorithm for figuring out if a number N is prime:

Using the first prime (2) as a divisor, check if integer division is possible (remainder is zero). Continue to use 2 as a divisor until the remainder becomes non-zero.

Using the second prime (3) as a divisor, check if integer division is possible (remainder is zero). Continue to use 3 as a divisor until the remainder becomes non-zero.

Continue with increasingly larger primes until the prime that is close in value to:

equation

It is quite obvious that, if N would be divisible by a prime larger than √N then the quotient would be a prime smaller than √N. We see that if testing for divisibility with smaller primes has failed, testing for larger primes cannot yield any new instances of divisibility.

Example:

To test the primality of 889 we only need to use primes between 3 and 29. We omit 2 since the number is odd.