| Prime Home | Primer on Primes | In Search of Primes | Sieve of Eratosthenes | Files | References | Table of Contents |
A Primer on Primes |
| Introduction : Prime numbers are the basis of many modern enciphering methods. Primes are now the basis of entire fields of applied mathematics. We now have governments trying to define illegal use of prime numbers. This makes prime numbers exciting, if not interesting. The simplicity of prime numbers also appeals to the problem solver. Unfortunately most information sources on prime numbers do not address the basics of prime numbers. |
| History : A long time ago in a land far away... (Greece about 600 BC) Many mathematicians were discovering the fundamentals of number theory, geometry, and trigonometry. Philolaus is credited with formalizing all natural numbers into composite or prime categories. About 400 years later, Eratosthenes became famous for two discoveries. He calculated the perimeter of the earth to within 5% of the actual value. He also developed the Sieve of Eratosthenes, a fast method for screening prime numbers. |
| Primes
Defined : Natural numbers, integers, and
whole numbers are the same. All of these describe numbers
without fractional or decimal parts. Two, three , five,
and 4356 are all natural numbers. The old Greeks did not
recognize zero or one, but they also are natural numbers.
3.1415, 1.234, and 1/3 are not natural numbers, since
they have fractional or decimal parts. For the rest of
this paper, these two types of numbers will be split into
two groups, Integer numbers and Real numbers. Integers
are natural numbers, and real numbers are everything not
Integer. If you remember back to elementary school, you may remember fractions. You may remember factoring of Integers. You probably don't remember it with any fondness. In the table below, we put a series of numbers and list the factors. Table 2 contains factors of numbers to 255.
If we examine the information in this table, some things can be learned. Everyone of these numbers are either a factorable or not factorable (duh). If the number is factorable, all of the factors are non-factorable numbers. The non-factorable numbers are prime numbers. Prime numbers are defined as numbers only factorable by one and themselves. All factorable (non-prime) numbers are called composite numbers. The reason most of us disliked factoring is the lack of a simple method of finding the factors, or primeness. There are a number of 'tricks' used to find simple factors. Some of these are listed below:
There are also methods 7, 11 and 13, but are progressively more complex. There methods are different for each prime factor, and increasingly more difficult. These methods are also not computer appropriate. These methods are appropriate for manual factoring only. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Algebra of
Primes: In the next sections methods of
factoring for small primes will be explained. In order to
understand the methods, a few fundamental rules need to
be defined. Factors of Sums: If we have the following conditions :
where d is a factor of both B and C, and therefore it is also a factor of A. Example : If we add a number factorable by 7, 42 to another number factorable by 7 say 70, the result is 112, which factors to 2·2·2·2·7. As you can see 112 does have 7 as a factor. Factors of Products : If we a product of A and some factor B:
If C has some factor d, and d is not a factor of B, A is then factorable by d. Example : If we multiply 21 by 5 with the result of 105, and 105 is factorable by 7, then 21 is factorable by 7, since 5 is not factorable by 7. |
Factoring 3 :
The finding factors of 3 is sometimes used, but rarely
proven. Finding if a number is factorable by three is
done as follows
Example 1
Example 2
Some of you may be wondering how this works. First we need to step back and look at how we can algabraically work with prime numbers. This is also defined in the section above on Algebra of Primes.
If we represent some number Q as a series of sums where dx are the digit values we have:
and according to the associative rule we can define Q as
If both term1 and term2 are factorable by a given number A, the number Q is factorable by the same number A. By re-arranging the series of sums in the equation above we have:
Examination of the second set of terms reveals that it is factorable by 9 for all possible numbers of Q, and therefore factorable by 3. If the first set of terms are factorable by 3, Q is factorable by 3. This is not a mathematically rigorous proof, but an adequate explanation of the algorithm. |
Factoring by
11: If we represent the number we are
factoring :
where d1 represents the lowest digit and Dn represents all of the digits above d1. This equation can be algebraically rearranged :
In terms of factoring the equations above are equivalent, since the only difference is an additional factor of -1 in the -Q equation. This representation once again results in two terms, the second of which is clearly factorable by 11. The first term can be recursively entered into the same function until it is clearly factorable / non-factorable by 11. The method is best summarized as:
Example 1:
Example 2:
|
| Factoring by
7: This is similar to the factoring by 11
exercise above. If we represent the number we are factoring :
where d1 represents the lowest digit and Dn represents all of the digits above d1. This equation can be algebraically rearranged :
In terms of factoring the equations above are equivalent, since the only difference is an additional factor of -2 in the -Q equation. This representation once again results in two terms, the second of which is clearly factorable by 7. The first term can be recursively entered into the same function until it is clearly factorable / non-factorable by 7. The method is best summarized as:
Example 1:
Example 2:
|
| Factoring by
13: This is similar to the factoring by 11
exercise above. This is third example of this method.
After this you should be able to apply this method to any
factor of reasonable size. If we represent the number we are factoring :
where d1 represents the lowest digit and Dn represents all of the digits above d1. This equation can be algebraically rearranged :
In terms of factoring the equations above are equivalent, since the only difference is an additional factor of 4 in the second Q equation. This representation once again results in two terms, the second of which is clearly factorable by 13. The first term can be recursively entered into the same function until it is clearly factorable / non-factorable by 13. The method is best summarized as:
Example 1:
Example 2:
|
Summary
: We can summarize this topic to the following:
|
|
|
