|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
course syllabus assignments materials request a test proctor form |
Prime FactorsGiven a natural number value, how can you determine its prime factors or if it is prime? Recall that a prime number is an Integer, n, greater than 1 which is evenly divisible only by 1 and itself. By evenly divisible we mean that the remainder after the division is zero. If a number has only itself as a factor, then it is prime. If it has more than one prime factor, then it is composite. The Fundamental Theorem of Arithmetic states that any Natural Number may be factored into one or more prime factors. The prime factors are unique except for order and, being primes, cannot be further factored. As an example: 126 can be factored into 2•3•3•7 or 2•32•7. On the other hand, the value 127 cannot be factored; thus, it is prime. The prime factors are not simply a list of all possible factors. As an example, our value of 126 can be factored by 6. Indeed all the possible factors of 126 are: 1, 2, 3, 6, 7, 9, 14, 18, 21, 42, 63, and 126. Some of these are prime, others are products of the prime factors. A difference between the list of possible factors and the prime factors, is that when all the prime factors are multiplied together, we get the original number. Given a value n how can we obtain the prime factors? The answer is simple—try dividing the number by all possible primes smaller than the number! This simple answer can be a lot of work and would not necessarily catch all the prime factors if one happens to be repeated (as with the 3 in the example above for 126). We can make the process more efficient and effective. A good procedure involves three improvements. The first is that we will start with the smallest possible prime factor first, then progressively try larger values. The second is whenever we find a factor we will try it again; however, the most important improvement is that we continue from that point onward with the quotient rather than the original number. This makes the checking easier (the number gets smaller as we proceed and we can catch a prime that is a multiple factor). The third is that we stop the process when the trial factor is greater than the square root of the number. The reason is that if there is indeed a factor greater than the square root, then there must be one smaller which we would have already found (and in the process find the larger one as well). Rather than comparing the trial factor with the square root, we will square the trial factor and compare it directly to the number. This way we can avoid having to compute a square root. Let us try this process on 126.
We notice that if a trial factor divides the number evenly, then we try it again using the quotient in the next step. It is only when a trial factor does not divide evenly that we move to the next possible prime trial factor. If we try this process on 127, we get:
This process is straightforward if we have a list of primes. However, we can make it easier to work, but less efficient, by using the list: 2, 3, 5, 7, 9, 11, 13, .... Except for the initial 2 (the only even prime) all the others are simply consecutive odd numbers. The use of an odd value that is not a prime will cause an additional step, but will not create an incorrect result since we would previously removed its factors. As an example, if we have a number such as 1989 (32•13•17), then applying our process would give:
Even though the original number had 9 as a factor, by the time we got around to trying 9, we had already removed the two factors of 3. Thus we had an extra step that essentially did nothing. As we saw with the examples for 126 and 127, the process is reasonable efficient for small to moderate size numbers since we only need in the worst case to try about half of the numbers up to the square root of the number:
While almost 16,000 trial factors seem undoable when performing this process by hand, it is a very fast job for a simple computer program to find the prime factors of a number near one billion! The process above tries about half the values since we eliminate the even numbers. We could also easily eliminate the numbers that are multiples of 3. All prime numbers above three are either one more or one less than a multiple of 6. Therefore, starting with 5 we successively add 2 to get the next trial factor (7), then 4 (11), then 2 (13), then 4 (17), etc. This will reduce even further the number of possible trial factors. However, it still will not eliminate all non-primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 51, .... Even for this short list, we have the non-prime numbers: 25, 35 and 49. And it is harder to keep everything straight if we do this by hand. For a computer program that is not a problem, and it means we need test only about 1/3 rather than 1/2 of the numbers up to the square root of the original number. However, for numbers that are tens of digits in length, this process is much to slow even for the fastest computer. To find the prime factors of a number of 100 digits would take millions of years! Fortunately, there are other procedures that can determine if such a number is prime or not, even if we cannot determine the prime factors. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
© 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008 by Lawrence Turner |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||