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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/