

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

Let's observe following number :

$ 4517\cdot 2^{332192811}+1$

I have noticed :

If $k\cdot 2^{2n+1}+1$ is prime number then $\gcd(k-1,3)=1$ , where $k,n \in Z^{+}$ , so

$\gcd(k-1,3)=1$ should be a necessary condition.

Since $\gcd(4516,3)=1$ this condition is fulfilled.

Proth weight of coefficient $4517$ is $w \approx 0.98199 $ which may be considered to be high value.

I would like to know are there some other necessary conditions that this number has to satisfy , so that might be considered like candidate for prime number ?

share|cite|improve this question


1: PrimeQ[$4517\cdot2^{332192811} + 1$]

2: False

I guess they use the Miller-Rabin primality test.

share|cite|improve this answer
Thanks..I know that it is easy to test number using a computer...but I would like to know are there some theoretical conditions similar to the conditions that I mentioned in the text of the question.. – pedja Nov 25 '11 at 12:56
Did you look up the wikipedia page I linked? The Miller-Rabin test actually relies on such conditions which are true for primes. – Listing Nov 25 '11 at 13:04
Put another way: Miller-Rabin is in fact a compositeness test. If PrimeQ[] returns False, the number is definitely composite. – J. M. Nov 25 '11 at 13:08
I think that there must be more similar conditions.. – pedja Nov 25 '11 at 13:08

Your Answer


