This article will introduce simple methods to factor numbers. As the number become larger a more advanced technique will be introduced.
Basics
For the purpose of this article we will only concern ourselves with factoring positive integers. These numbers are your common counting numbers that you are acquainted; that is: 1, 2, 3, 4, 5, 6, and so on.
The basic principle of factoring is to find at least two numbers (that is integers) that when multiplied together result in the number you wanted factored. A simple example is the number 6. Two numbers multiplied together to generate the result 6 are 2 x 3 = 6. That in a nutshell is factoring.
Now as the number becomes larger the number of unique sets of factors may increase. Take for example 12. We have the following sets of factors:
2 x 2 x 3 = 12, 4 x 3 = 12, 2 x 6 = 12, & 1 x 12 = 12
However, not all numbers can be factored into smaller numbers. For example take these two examples: 3 and 13. Both numbers cannot be reduced any further. When a number cannot be reduced into smaller numbers then that number is called a PRIME number.
In the above example: 12 can be broken down into 2 x 2 x 3 to which these numbers are all primes. In fact, all numbers can be broken down to a unique set of prime factors. The table below lists the prime factorization of the first 21 numbers:
As you can see several numbers cannot be broken down further. These prime numbers are unique and are extremely important to the rest of this discussion. The first set of prime numbers smaller than 102 are as follows:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,101
Note: the number one is no longer officially considered a prime number. It is neither prime nor composite (like 12).
Method #1: Trial Division: (From Ancient Greek Times)
This simple method requires one to divide all prime numbers less than the square root of number is question.
For example: You wanted to find the prime factorization of the number 100. The square root of 100 is 10 and the list of prime numbers less than 10 is 2,3,5,7.
Starting at 100 we divide by 2 and we have 50. Then take 50 and divide by 2 again and we have 25.Dividing by 2 again does not result in an integer and we try the next prime number and that too does not result in an integer. Lastly, we try 5 and 25 is divisible by 5. Thus we have the prime factors of 100 as being 2,2,5,5 or 2 x 2 x 5 x 5 = 100.
As an example try factoring 500: The answer would be 2 x 2 x 5 x 5 x 5
This is a simple method that works quickly with numbers below 1,000 or so. (Assuming you are doing this by hand and a simple calculator)
As the numbers become bigger a more modern method is required.
Method #2: Fermat’s Factorization Method Discovered in the Early 1600’s
Thousands of years later, Pierre de Fermat (1601 (or 1607/1608) to 1665), discovered a much better method to factor large numbers.
The formula represents an odd integer as the difference of two squares. (Note: If the number in question was even you can divide multiples of 2 until the number has been completely factored or you have an odd integer that may or may not be a prime.)
Let us take N to be the number of interest then the formula is:
Let us look at a simple example: Let us factor 5959.
Step #1: Take the square root of 5959 and we get a value equal to approximately 77.19. We take the next largest integer which is 78 and let that be initially equal to “a”
Step #2: We plug our initial value of “a” into the formula and see what we get for the square of “b”.
78x78– 5959 = 6084 – 5959 = 125 = bxb.... But, once we take the square root of b squared we get b = 11.18 which is not an integer. Since the resulting “b” is not an integer, we try again with the next biggest integer or in this case 79. We keep trying until we find one that works or until we find bxb such that b is an integer. Let us try it again with 79:
79x79– 5959 = 6241 – 5959 = 282 = bxb.... but b = 16.79. We try it again:
80x80– 5959 = 6400 – 5959 = 441 = bxb...and b = 21 is an integer. Therefore we have found our answer. Plugging the values back into formula we have
N = (80 +21) x (80-21) = 101 x 59
Therefore the factors are 101 and 59 for the number 5959. Both 101 and 59 are prime numbers and this means that the number cannot be further factorized.
Example #2: Try a nice large number: 192,911. The square root is approximately 439.21
Then our first a = 440: See table below
Therefore N = (444+65) x (444-65) = 509 x 379 (both are primes)
Now, the question is: how is this method better then the first method devised by the Greeks? Good question. In the first problem we examined was 5959. Recall the next largest integer great than the square root of 5959 was 78. That means we would have had to divide by all these prime numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, and 59 for a total of 17 divisions using the Greek method versus just 5 attempts using Fermat’s method. As you can clearly see Fermat’s method is extremely useful for larger numbers!
The real question is: If Fermat’s method is clearly so superior why bother with the Greek method?
The main reason is that the Greek method is much simpler for smaller numbers: Simple repetitive division versus solving a repeating algebraic expression. The next reason is that some numbers are made up of small repetitive integers that are clearly best solved by the Greek method; take for example: 4,747,561,509,943. When you look at this number, your eyes might glaze over at the thought of thousands of division you will need to make before you find any factors. The fact is that this number is the factor of 7’s – fifteen 7’s multiplied by each other!
4,747,561,509,943 = 7 x 7 x 7 x 7 x 7 x 7 x 7 x 7 x 7 x 7 x 7 x 7 x 7 x 7 x 7!
As you see, the old methods of doing things are not just something you can discard for new ideas and methods. They work too and at times they work better!
If you are totally confused over which method to use, try one and see where it takes you. If you are not happy then try the other. Remember mathematics is not a Science it is an Art. Yes, that is correct! When you graduate with a four or six year college degree at most colleges you are awarded a Bachelor’s of Arts or a Master’s of Arts degree not of Science! To put it simply: A mathematician’s canvass is his paper or his chalkboard and his brush is calculator or computer. The resulting painting may be as simplistic as the number Zero or one that never ends. Like a painter painting a lovely landscape with its hills and valleys its trees and flowers, the mathematician generates his equations, with their variables and their constants, some simple and others not so. Both create beauty for the senses to take in and the mind to savor!
Hope you have enjoyed this simple discussion of factoring!
Additional resources:
interesting and some very useful article......thank you for sharing
Gosh, this brings back some memories from the classroom but I don't think it was ever explained to me this clearly! Nice work.
It is very interesting article. Well done.
Very interesting...stumbled.
WEll shared wisdom. Thank you . Voted up
Quite a presentation!