Factoring And Prime Numbers - A Brief Introduction Part 1
Number Theory has it's roots in the quest for prime numbers. working out if a number is prime (and if not it's prime factors) is a matter of some considerable interest but it is not easy. We will look at some techniques to solve these difficulties in these articles.
Large numbers or small, there are of course some elementary observations which can be made at once. Even numbers and multiples of 5 are recognisable at sight, multiples of 3 respond to a simple and rapid mental check and thanks to a lucky combination of factors those of 7, 11 13 and 37 are found with little effort.
Many other of the smaller primes can be eliminated without having to use the laborious process of testing by actual division. These methods obviously dispose of vast quantities of the natural numbers-even numbers and multiples of 3 alone take care of two-thirds of them, for instance-but there remains an infinity of integers which are either prime or have larger prime factors than these methods are equipped to deal with. These fall into one of two camps; in the one case numbers of a particular structure such as, say, those expressed generally by the formula xn +- 1 for which the 'form' of possible factors can usually be determined fairly easily. On the other hand there are amorphous numbers, whose factor forms can only be found by congruence techniques which for numbers of six or seven digits are inferior to other methods of factorisation and are quite impracticable for larger numbers. It must also be noted that in testing a given number N for possible prime factors, it is not necessary to try a divisor greater than root N since if there is a factor larger than this there must also be a smaller one which has already been revealed.
Since testing by direct division by the primes in sequence is apparently only really applicable to numbers already covered in published tables, it would seem there is little point in pursuing this method further. One of the top factoring methods requires the determination of the upper limit of prime numbers not to be factors of the candidate number. Apart from this it will be obvious that if we have eliminated all the primes less than the cube root of a given number N then there can be at most two factors of N and one of these must be between the cube root of N and the square root of N.
Euclid's Algorithm is the most efficient method for testing small prime divisors. This is dependent on the fact that if two numbers share a common factor, the after dividing one by the other, the remainder will also contain the factor. Continuing in this manner the position is finally arrived at where either the remainder rn equals 1, in which case both numbers are relatively prime, or rn-1 is a multiple of rn. The integer rn is the GCF in the latter case.
As an example taking the numbers 21 and 56 we divide thus: 56/21 = 2, + 14; 21/14 = 1, + 7; 14/7 = 2 exactly and therefore the last divisor -7- is the HCF of the two numbers 21 and 56.
We will discuss this algorithm in greater detail in Part 2.
