What Is Trial Division?

Date: 02/24/98 at 10:01:42
From: Kyle Savage
Subject: Trial Division

What is trial division?

Date: 02/24/98 at 16:00:09
From: Doctor Rob
Subject: Re: Trial Division

It is a technique for factoring a number into the product of its prime 
number divisors:

   1. Start with your number and an empty list.
   2. Let the new divisor be the smallest whole number bigger than 1   
      you haven't yet used.
   3. Divide the number by the divisor.
   4. If it doesn't go in evenly, go back to step 2.
   5. It it does go in evenly, write down the divisor in the list.
   6. Replace your number with the quotient you got in step 3.
   7. If the new number is 1, stop.
   8. Go back to step 3.

When you are done, the list will contain all the prime number divisors 
of your original number.  The product of all the numbers on this list 
will equal your original number.

It is called trial division because you are trying to divide evenly by 
all the prime numbers, one at a time.

There are a few improvements that can be made to the above technique, 
but basically, that's it.

Example:  Factor 90 using trial division.

   1. Number is 90, list is {}.
   2. Divisor is 2.
   3. 90/2 = 45, remainder 0.
   5. List is {2}.
   6. Number is 45.
   7. Don't stop.
   8. Go to step 3.
   3. 45/2 = 22, remainder 1.
   4. Go to step 2.
   2. Divisor is 3.
   3. 45/3 = 15, remainder 0.
   5. List is {2, 3}.
   6. Number is 15.
   7. Don't stop.
   8. Go to step 3.
   3. 15/3 = 5, remainder 0.
   5. List is {2, 3, 3}.
   6. Number is 5.
   7. Don't stop.
   8. Go to step 3.
   3. 5/3 = 1, remainder 2.
   4. Go to step 2.
   2. Divisor is 4.
   3. 5/4 = 1, remainder 1.
   4. Go to step 2
   2. Divisor is 5.
   3. 5/5 = 1, remainder 0.
   5. List is {2, 3, 3, 5}.
   6. Number is 1.
   7. Stop.

The factorization of 90 is 90 = 2*3*3*5 = 2*3^2*5.

-Doctor Rob,  The Math Forum
Check out our web site http://mathforum.org/dr.math/