Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/   
    
Associated Topics:
Elementary Division

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/