CHAPTER 5
Decisive solution to the problem of recognizing prime numbers by a formula concerning recognizing of numbers ""
5.1. Determination of the formula for the characteristic function of numbers
At first we form a matrix of "0" and "1" for odd natural number and according to their divisibility on every odd number:
|
1 |
3 |
5 |
7 |
9 |
11 |
13 |
15 |
17 |
19 |
21 |
23 |
25 |
27 |
29 |
31 |
33 |
35 |
37 |
39 |
41 |
|
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
... |
3 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
... |
5 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
... |
7 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
... |
9 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
... |
11 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
... |
13 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
... |
15 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
... |
17 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
... |
19 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
... |
21 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
... |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
If numbers in columns are divisible on the numbers in rows, their intersection, in the table has a value as "1" and if they arent divisible their intersection has a value as "0".
First column has only "1" because all of numbers are multiplier of "1".
Second column indicates multipliers of 3.
Third column indicates multipliers of 5.
And as it is seen, every column is multipliers of a number.
According to table rows, when in front of every column number written just two number "1", in fact that column number is a prime number because "every prime number is divided just on "1" and itself". And knowing that "for identifying the primality of specific number "N", it is enough that we divide "N" on prime numbers which are not more than ". For identifying column number it is enough to attend row of that number. If in one row there are more than two numbers "1", that number isnt prime column number. For example the row concerned to number "15", has four number "1" , because it is divisible on 1,3,5 and 15 therefore "15" is composite. But rows of (3, 5, 7, , 17, 19, ...) have just two numbers "1". So this numbers are Prime. For identifying the numbers, it is enough that we find some functions that produce every one of table column. In the other hand it produce all of "0" and "1" in every column with same column arrange (from up to end).
General formula of these functions is:
|
|
|
|
|
|
|
1 |
1 |
0 |
0 |
0 |
0 |
0 |
3 |
1 |
1 |
0 |
0 |
0 |
0 |
5 |
1 |
0 |
1 |
0 |
0 |
0 |
7 |
1 |
0 |
0 |
1 |
0 |
0 |
9 |
1 |
1 |
0 |
0 |
1 |
0 |
11 |
1 |
0 |
0 |
0 |
0 |
1 |
13 |
1 |
0 |
0 |
0 |
0 |
0 |
15 |
1 |
1 |
1 |
0 |
0 |
0 |
17 |
1 |
0 |
0 |
0 |
0 |
0 |
19 |
1 |
0 |
0 |
0 |
0 |
0 |
|
|
|
|
|
|
|
According to the table and this point that for identifying numbers "N", it is enough to divide it on prime numbers which are not more than, therefore, we divide "N" on odd numbers which are not more than it, So for calculating odd number which is not more than, sum of functions of the numbers in column "x" is enough. Therefore, if "N" be prime, we have just one number "1" in row of number "N":
("N" is prime number)
If "N" is composite:
("N" is not prime number)
We know that "1" is neither prime nor composite and also, therefore, if "N" be an odd number and greater than then:
(3)
That *S value is:
"" is prime or composite and these two cases will be determined by identification function and always just two cases (3) namely "0" and "1" will be accrued. Therefore, if we write a function by using it is a surjective function (in the set of odd numbers that are greater than "3").
According to primary conditions, we form the below table:
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
50 |
|
|
3 |
5 |
7 |
9 |
11 |
13 |
15 |
17 |
19 |
|
101 |
|
|
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
|
1 |
|
Now, we content oneself with present example two, for showing application of this function.
At first we calculate *S for identifying the number to be prime or composite:
Then we form function:
Since "" so, number "2003" is a prime number.
For determining number"" if we calculate like example (5.1.3), it results:
Since "" so number "" is a composite number.
According to above examples, It is observed that for determining a number like "N", It is enough to calculate () by a simple software program[1]. It is obvious that in this method, for determining number "N", only answer of dividing "N" on all of odd numbers smaller than are used. Therefore, for determining number "N", we do the least possible calculation by this method software program of this identification function.
If we want the identification function to accept , we can use one of two below identification functions instead of it ():
The number "*S" is same for ,, and is calculated by below relation:
Therefore, for every odd number greater than "1" ():
[1] . Refer to the appendixes II (22.2)