MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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 – user9072 Aug 16 '13 at 9:31
It should say above that compositenes is never very easy to establish (as one will never find a very small factor). – user9072 Aug 16 '13 at 11:28
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.) – Noam D. Elkies Aug 16 '13 at 13:09
@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.) – user9072 Aug 16 '13 at 19:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.