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:

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

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
Math Forum Home || Math Library || Quick Reference || Math Forum Search