Is there any way (general procedure, i mean) to determine if a Euclid Number (En = pn# + 1) is prime or composite? Any research papers exploring this theme are also welcome. Thanks!
4
-
2$\begingroup$ On the one hand, there are many general procedures to determine for any number if they are prime or not, in this sense, yes. OTOH, it is an open problem if there are infinitely many primes of this form, so there is no characetrization or anything even close to a characterization for which $n$ the number is prime. When testing such a number for prime one knows it won't have small primefactors; one thus can save a step in usual prime testing algorthms, but it also shows that primeness of these numbers is never very easy to establish. For references around this see oeis.org/A006862 $\endgroup$– user9072Aug 16, 2013 at 9:31
-
$\begingroup$ It should say above that compositenes is never very easy to establish (as one will never find a very small factor). $\endgroup$– user9072Aug 16, 2013 at 11:28
-
$\begingroup$ Actually compositeness of $N$ can be much easier to establish than primality: just find a case where the Miller-Rabin test fails (usually the Fermat test is all that's needed). Of course that's assuming that $N$ isn't so large that you can't actually compute with it; if it's the $n$-th "Euclid number" for $n$ on the order of $10^6$ then the only hope is to get lucky and find a prime factor $l$ small enough that $\prod_{m\leq n} p_n \equiv -1 \bmod l$. (If you want to find such an example, start with $l=p_r$ and try all $n < r$, which should succeed about $1-\exp(-1)$ of the time.) $\endgroup$– Noam D. ElkiesAug 16, 2013 at 13:09
-
$\begingroup$ @NoamD.Elkies I am not sure if you refer to my comment, but in case: I meant to say that trial-divsion by (very) small primes will never give anything useful for these numbers. Success of this trial division is what I meant by 'very easy'. (Not some relative statement whether compositenes or primality is relatively easier to establish.) $\endgroup$– user9072Aug 16, 2013 at 19:09
Add a comment
|