Extended Wilson's Theorem

I found another interesting result when I was studying some of the properties of prime numbers. It is like this...

   

Where P is any Prime number and  1 <= n <= P (Simply for any ‘n’ that makes sense).

Btw when n=1, the above becomes Wilson’s Theorem. So this is kind of an Extended Wilson’s Theorem…   

;-)

Reply me when you get a chance…

This C++ program is to check whether a given number is prime or not using the above method... Try this out, you will how fast it is...

#include <iostream>

#include <time.h>

using namespace std;

int main (){

long long k, a;

again:

cin >> k;

if (k == 1){ 

cout << "Composite" << endl;

goto again;

}

if (k == 2 || k == 3){

cout << "Prime" << endl;

goto again;

}

//time

clock_t tStart = clock();

if ((k-1)%6==0){

a=(k-1)/6;

for (long long i=1; i<a/2; i++){

if ( (a-i)%(6*i+1)==0 || (a+i)%(6*i-1)==0 ){

goto out;

}

}

}else if ((k+1)%6==0){

a=(k+1)/6;

for (long long i=1; i<a/2; i++){

if ( (a-i)%(6*i-1)==0  ){

goto out;

}

}

}else{

goto out;

}

cout << "Prime" << endl;

goto skip;

out:

cout << "Composite" << endl;

skip:

//time

printf("Time taken: %.4fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);

goto again;

system ("pause");

return 0;

}

Prime Number Pattern

I have been working on prime number cases for few days and found a quite nice simple result. My finding was a primality test which could generate whether a given number is prime or composite very easily. This could be used even by the school children since it is simple and need no special mathematical knowledge to handle it.

For the time being, I wont be publishing any proofs of my theory, but I will publish them very soon.

----------------------------------------

As you know, every prime number can be expressed in one of the form 6*m - 1 or 6*m + 1.  Except 2 and 3.

Let's take the number that is to be checked whether a prime or not as 'n'.

First you have to find the form of 'n'. That is whether it is in the form of 6*m - 1 or 6*m + 1. This is very easy because you only have to check whether n+1 or n-1 is divisible by 6. It is clearly observed that if neither n+1 nor n-1 is not divisible by 6, n is composite. 

If,

(n-1) MOD 6 = 0, then n is in the form of 6*m + 1

(n+1) MOD6 = 0, then n is in the form of 6*m - 1.

Save the value of 'm' for future uses...

 ( a MOD b = the remainder you get by dividing 'a' from 'b')

Let's consider two real positive integers K, L.

If' 'n' is in the form of 6*m + 1

Define,

         K = (m + a) / (6*a - 1)                               L = (m - a) / (6*a + 1)

                                                                                                                           ( 'a' is a positive integer )

If for all 'a', K and L is not an integer, then 'n' is a prime.

If not composite.

If 'n' is in the form of 6*m - 1 

Define,

           

     K = (m - a) / (6*m - 1)                              

                                                        ('a' is a positive integer)

If for all 'a', K and L is not an integer, then 'n' is a prime.

If not composite.

Well that's it. I would like to demonstrate an example then you could understand much easily.

Example 1:

Take our 'n' as 143.

142 MOD 6 = 4

144 MOD 6 = 0

So 143 is in the form of 6*m - 1.

So m = 24

Then,

                K = (m - a) / (6*a - 1)          

a=1;  K =  (24 - 1) / (6-1) not integer

a=2;  K =  (24 - 2) / (12 - 1)  = 22/11 = 2------> integer

So you don't have to continue this test further, because K has became an integer for a=2. 

Then 143 is Composite.

Example 2:

Take our 'n' as 257.

256 MOD 6 = 4

258 MOD 6 = 0

So m = 43 and the form is 6*m - 1.

Then,

                K = (m - a) / (6*a - 1)     

a=1;  K = (43-1)/(6-1) not integer

a=2;  K = (43-2)/(12-1) n.i.

a=3;  K = (43-3)/(18-1) n.i.

a=4;  K = (43-4)/(24-1) = 39/23 ---> it is clear that for further 'a', K cannot be an integer

So K did not become an integer for any 'a'. So 257 is prime.

Hope you understand.

Please be kind enough to leave a reply too.

NOTE:

You might have noticed that even for bigger 'n', the number of calculations is not much, compared to other primality tests like Fermat Primality Test. So this is a very effective way of checking primality of bigger numbers. 

Hello World!