Complementary  prime-sieve (C.P.S.)

 

 

T a m á s D é n e s mathematician 

free-lance expert

 

e-mail: tdenest@freemail.hu

 

 

ABSTRACT

 

The above mentioned  "complementary prime-sieve" (for short: C.P.S.) can be characterized as follows:

a necessary sufficient condition is given for  natural numbers of forms 6k+1 and 6k-1 (k=1,2,3,...) when they will be composite numbers.

Theorems  1. and 2. imply a short elemetary proof of the infinity of the prime numbers.  C.P.S. does not need the use of Dirichlet's theorem.

With the aid of  C.P.S. we are able to generate the prime numbers without factorization and we give an estimate for  the cardinality of primes less then  X  (notation: ), where  X is an arbitrary natural number.    

 

 

Theorem  1.

Every prime number    has the forms  6k+1 or  6k-1  where k = 1,2,3,...

 

Proof:

Let us suppose that  p  is not of the forms  6k+1 or  6k-1, this implies:

 

(1.1)                  p= 6k+2    or   p= 6k-2          p is an even number, therefore it is a composite number.

 

(1.2)                  p= 6k+3    or   p= 6k-3          p is divisible  3, therefore it is a composite number.

 

(1.3)                  p= 6k+4    vagy   p= 6k-4      p is an even number, therefore it is a composite number.

 

(1.4)                  p= 6k+5    vagy   p= 6k-5         p= 6k+5 = 6(k+1)-1  or   p= 6k-5 = 6(k-1)+1 

 

these are the forms of the theorem.

                                                                                                                  Q.E.D.

 

 

Remark:

Dirichlet's theorem states that "If (a,b)=1, then the arithmetic progression  ak+b  (k=1,2,3,...)  contains infinitely many primes."  But our  theorem  states that  every primes are of the forms  6k+1 or  6k-1.

 

According to the  Theorem 1. the natural numbers can be ordered  in  six columns (see Figure 1.), where the first and the fifth column contain all prime numbers (the first column contains of the forms  6k+1 and the fifth column contains  6k-1).

 

 

Figure 1.

 

6k+1 
      
6k-1
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
. . .          

 

Theorem 1.  implies a direct upper bound of the cardinality of prime numbers not exceeding  N   ():

 

(1.5)                                             

 

As a result of  Theorem 1.  the determination of  prime numbers  p makes it possible to enumerate the numbers of the form    .

Below  (see  Theorem 2.)  we give necessary and sufficient conditions when the numbers of the forms    are composite numbers.  These conditions give the procedure which can be called  C.P.S.

 

Theorem 2.   (Complementary Prime-Sieve: C.P.S.)

 

Let us suppose that  N, k, u, v  are natural numbers, where  u,v 1.

N= 6k+1  is a composite number iff     k =  6uv + u + v     or    k= 6uv - u - v   

N= 6k -1  is a composite number iff    k =  6uv -  u + v     or    k= 6uv +u - v    holds.

 

Proof of necessity:

Let us suppose  that  N= 6k+1  is a composite number, then  6k+1 = dr   k=   holds. There are two options:

 

(2.1)     d= 6u+1  and        r= 6v+1 

 

              k= ==  6uv + u + v

 

(2.2)     d= 6u-1  and      r= 6v-1

 

              k= = = 6uv -u -v

 

 

If  N= 6k-1 is a composite number, then  6k-1= dr   k=    holds.

There are two options:

 

(2.3)             d= 6u+1   and       r= 6v-1  

            k=  =  =  6uv -u + v

 

This formula  (2.3) is symmetric for  u, v, so there is another solution: 

 

(2.4)          k= 6uv + u - v

 

We proved the proof of necessity.

 

 

Proof of sufficiency:

Let us suppose  that  k= 6uv+u+v  and  N= 6k+1, as well as   v=u+r ,  where    , then

 

(2.5)          N=6(6u(u+r)+u+u+r)+1 = 6(6+6ur+2u+r)+1 = =

                  ==  (6u+1)(6v+1)    it is trivially not a prime.

 

Let us suppose that  k= 6uv-u-v  and  N= 6k+1, as well as  v=u+r,  where   , then

 

(2.6)         N=6(6u(u+r)-u-(u+r))+1 = 6(6+6ur-2u-r)+1 = =

                 ==  (6u-1)(6v-1)   it is trivially not a prime.

 

 

 

Let us suppose that  k=6uv-u+v   and  N= 6k-1, as well as  v=u+r,  where    , then

 

(2.7)           N=6(6u(u+r)-u+u+r)-1 = 6(6+6ur+r)-1 = =

                   =(6u+1)(6u-1)+6r(6u+1) = (6u+1)(6u-1+6r) =  (6u+1)(6v-1)   it is trivially not a prime.

 

 

Let us suppose that  k=6uv+u-v   and   N=6k-1, as well as  v=u+r,  where    , then

 

(2.8)          N=6(6u(u+r)+u-(u+r))-1 = 6(6+6ur-r)-1 = =

                  =(6u+1)(6u-1)+6r(6u-1) = (6u-1)(6u+1+6r) =  (6u-1)(6v+1)     it is trivially not a prime.

         

                                                                                                                                                                 Q.E.D.

 

Corollary  3.

As a result of Formulaes  (2.5) - (2.8)  the natural number  N=   is represented as a product of  .

If   6u-1, 6u+1, 6v-1, 6v+1  are prime numbers (by Theorem 1.), then we obtaine prime factorization of  N.

 

If we induce the notations   a=6u+1   and   b=6u-1, then all    can be represented as one of the

following forms (2.9):

 

(2.9)                                     

 

Example:      u=23,  r=29   a=139,  b=137     = 139x313= 43507   = 137x311= 42607 

                                                                                        = 139x311= 43229   = 137x313= 42881                             

 

Corollary  4.

According to that   always holds and using the notations introduced in corollary 3    except when   r=0  .

Checking the magnitudes of    we can obtain the matrix exhibited below  (see  Figure  2.).

 

>0 consequently
consequently
consequently
consequently
consequently
consequently

 

  Figure 2.

 
-
>
>
>
<
-
<
<
<
>
-
<
>
-

 

In such a way the relation         always holds.

Theorem  1. and 2. imply a short elementary proof  of  the infinity of  the prime numbers:

 

Corollary  5.

The cardinality of prime numbers are infinite.

 

Proof  (indirect):

Let us suppose that the cardinality of prime numbers are finite.

Theorem 1. is sufficient to investigate natural numbers of the forms   .

Let us denote maximal element of prime numbers with  P=6K+1. Consequently all    natural numbers are composite.

By Theorem 2. (see  formulaes  (2.5), (2.6), (2.7), (2.8) )   p  factorized into at least two prime factors as follows:      where     all      and    are primes.

The indirect statement implies that all      consequently      

Thus the cardinality of  the natural numbers of form    are finite, but it is not true. Consequently K doesn’t exist, thus the indirect statement is false. 

The use of form  6k+1 is enough to complete the proof, but we could follow the same way with the use of   6k-1.

 

                                                                                                                                                                Q.E.D.

Corollary  6.

By formulaes   (2.5) - (2.8)  we are investigating the cardinality of  composite numbers of forms  6k+1 and  6k-1 up to  N. It means that we are investigating the inequality  (i= 1,2,3,4).

 

(2.10)      (6u+1)(6u+1+6r)    

 

(2.11)   

 

 

(2.12)      (6u-1)(6u-1+6r)     

 

(2.13)    

 

 

(2.14)       (6u+1)(6u-1+6r)      

 

(2.15)    

 

 

(2.16)        (6u-1)(6u+1+6r)      

 

(2.17)    

 

 

By formulae     (i=1,2,3,4) , the pair  u,v  is symmetrical. Clearly in case of     for   the values of     determine all composite numbers of form  6k+1 and   6k-1.  That implies the formulae below :

 

(2.18)       consequently  

 

 

(2.19)       consequently  

 

 

(2.20)       consequently  

Let us introduce the notation  , that will denote the number of  composite numbers for which      holds.

 

(2.21)                      

 

(2.22)                    

 

(2.23)                     

 

(2.24)                     

 

 

(2.25)                

 

 

The proof mentioned above ensured the necessity only i.e.  producing all different pairs  (u,v).

That makes the occurrence of the composite number possible more than once. Let us denote the number of composite numbers up to  N with .  m(N)  denotes the composite numbers’ occurrence more than once.

 

(2.26)                

 

Let us denote with KP(N)  the number of prime numbers obtained with the aid of  C.P.S.:

 

(2.27)                  KP(N) =  

 

If we know the exact value of   m(N)  that implies the  formulae  (2.28):   

(2.28)                      =  KP(N)

 

 

Corollary  7.

Formulae   (2.21) - (2.25)  imply an approximation of K(N).  Easy to see that  formula (2.29)   holds.

 

(2.29)                            as well as              

Without  losing the generality of the formulae   (2.21) - (2.24)  we can use the value  to sum:

 

(2.30)    K(N)=

(2.31)    If  a= 6u+1  and   b= 6u-1

 

              =

 

              =   

 

 

Easy to see that     , in such a way for  K(N)  the result is the following:

 

(2.32)    

 

 

The approximation of   inequalities might be used  (2.33)  (see [5] at  p 6.):

 

(2.33)                   

 

We obtained as below  (2.34):

 

(2.34)       

 

Let us suppose that mean of (2.34)  left and right side is the approximation of  K(N)  (denote: KK(N) ).

 

(2.35)                                = 

 

 

 

 

 

Corollary  8.

Similarly to formulae   (2.10) - (2.17)  we shall investigate the inequalities    (i= 1,2,3,4)   where   is a natural number.

 

(2.36)                

 

(2.37)               

 

(2.38)              

 

(2.39)              

 

 

Obviously the above mentioned formulae is defined in the interval  (M,N). Let us introduce the notation      (i=1,2,3,4) that will denote the number of pairs  (u,v)  composite numbers included in the interval  (M,N):

 

(2.40)                      

 

(2.41)                    

 

(2.42)                     

 

(2.43)                     

 

 

(2.44)                

 

Below we  give the equivalent formulae for  (2.26), (2.27), (2.32), (2.35)  in arbitrary interval  (M,N):

 

 

(2.45)                

 

 

(2.46)                  KP(M,N) =  

 

 (2.47)     K(M,N)=

                             =

 

 

   , thus we give for  K(M,N):

 

 

(2.48)    

 

 

For the approximation of     we can apply the mean value of formulae (2.33):

 

 (2.49)                                KK(M,N) = 

 

 

If   N=6k+1 or  N=6k-1  is a composite number, then  two factorable representations of   N  by   (2.49)  maximum steps are needed:

 

(2.50)                              

 

 

C.P.S.  gives a direct representation of composite numbers in an interval  (M,N). Consequently one can obtain the prime numbers of interval  (M,N). 

By that approach one can obtain efficient methods to solve three basic tasks about the prime numbers:

1. Given an interval  (M,N).  Enumerate all prime numbers from that interval.

2. Let us represent the prime numbers up to  N. (Then  M=1)

3. Decide whether a natural number   p  is a prime itself.

 

In RSA  (Rivest, Shamir, Adleman) cryptosystem the tasks 1-3  might be used with practical values.  In a forthcoming paper we shall hopefully return to that applications.       

 

Open problems and conjectures:

What is an exact value of m(N) ?  or  What is a good approximate of  m(N) ?

These questions are equivalent the following problem:

Let us the following equalities  k1=v(6u+1)+u, k2=v(6u-1)-u, k3=v(6u-1)+u, k4=v(6u+1)-u . If

(C an arbitrary natural number) and  then how many time are there  ?

 

Conjecture 1. :  KP(N)  approximates  .

 

Conjecture 2.:

 The relative error of  KP(N) and   are better than  .

Figure 3.  demonstrate the paper's results on the cardinality of prime numbers.

 

Figure 3. 

N
K(N)
KK(N)
m(N)
KP(N)

KP(N)

rel.err. (%)

rel.err. (%)
1.000
205
195
34
162
168
144
3.5
14.3
2.000
484
461
112
294
303
263
3.0
13.2
3.000
794
755
214
420
430
375
2.3
12.8
4.000
1.118
1.067
325
540
552
482
2.2
12.7
5.000
1.452
1.394
442
656
669
587
2.0
12.3
6.000
1.807
1.731
577
770
783
690
1.7
11.8
7.000
2.160
2.077
713
886
900
791
1.5
12.1
8.000
2.532
2.431
857
991
1.007
890
1.5
11.6
9.000
2.905
2.792
1.006
1.101
1.117
988
1.4
11.5
10.000
3.281
3.159
1.160
1.212
1.229
1.086
1.4
11.6
.11.000
3.666
3.531
1.316
1.316
1.335
1.182
1.4
11.5
12.000
4.055
3.909
1.474
1.419
1.438
1.278
1.3
11.1
13.000
4.454
4.291
1.648
1.527
1.547
1.372
1.3
11.3
14.000
4.850
4.677
1.815
1.631
1.652
1.466
1.2
11.3
30.000
11.641
11.266
4.891
3.250
3.245
2.910
0.2
10.3
50.000
20.796
20.175
9.263
5.133
5.133
4.621
0.0
10.0
70.000
30.409
29.537
14.013
6.937
6.935
6.275
0.0
9.5
90.000
40.335
39.220
19.053
8.718
8.713
7.890
0.0
9.4
190.000
92.971
90.619
46.813
17.175
17.170
15.632
0.0
8.9
350.000
183.080
178.739
96.357
29.943
29.977
27.417
0.1
8.5
900.000
517.786
506.647
289.266
71.480
71.274
65.645
0.1
7.9
1.000.000
581.158
568.777
326.493
78.668
78.498
72.382
0.2
7.8
1.500.000
905.437
886.863
520.366
114.929
114.155
105.478
0.6
7.6
2.000.000
1.239.132
1.214.375
721.684
149.218
148.933
137.849
0.2
7.4
3.000.000
1.926.146
1.889.011
1.143.113
216.967
216.818
201.152
0.6
7.2
4.000.000
2.632.033
2.582.508
1.581.846
283.146
283.148
263.127
0.0
7.0
5.000.000
3.351.917
3.290.031
2.033.930
348.679
348.515
324.150
0.4
7.0
6.000.000
4.083.022
4.008.733
2.495.735
412.713
412.851
384.436
0.3
6.9
7.000.000
4.823.413
4.736.732
2.966.794
476.714
476.650
444.122
0.1
6.8
8.000.000
5.571.739
5.472.690
3.445.726
540.653
539.779
503.304
0.1
6.7
10.000.000
7.088.528
6.964.708
4.416.529
661.334
664.579
620.421
0.4
6.6

 

References

[1]  T.Dénes:  New results in RSA key decryption

                       (in Hungarian)  Híradástechnika, 2002/1. 47-55

 

[2]  T.Dénes:  Complementary Prime Sive and a remark on S.W.Golomb’s factorization method

                       (manuscript)

 

[3]  S.W.Golomb: FAX massage to  J.Dénes   (dated  21.07.2000.)

                                Problem E969: American Math. Monthly, (vol 58. no.5. p 338.) 1951.

 

[4]  S.W. Golomb, On factoring Jevons’ number

                                CRYPTOLOGIA, vol XX. No3 1996

 

[5]  P. Erdős, J. Surányi:  Selected chapters from the theory of numbers

                                               (in Hungarian)    Polygon, Szeged, 1996.

 

[6]  Maria Suzuki:  Alternative Formulations of the Twin Prime Problem

 The Amer. Math. Monthly, Vol. 107.  january 2000.