Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hi,

I know that the answer is no, yet I dont know how to prove it wrong. Finding a counterexample is not a good solution because it is a past written exam question with no calculators allowed. The first counterexample is about 30000... Is there a, simple preferred, solution to this problem? (This is asked in a CS discrete math exam)

The original problem is from Rosen Discrete Math, and as follows:

Prove or disprove that $p_1p_2 ... p_n+1$ is prime for every integer n, where $p_i$ is the ith smallest prime number.

Thanks in advance.

share|improve this question

closed as off-topic by Andy Putman, Andrey Rekalo, Stefan Kohl, Daniel Moskovich, Chris Godsil Dec 21 '13 at 15:16

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – Andy Putman, Andrey Rekalo, Stefan Kohl, Daniel Moskovich, Chris Godsil
If this question can be reworded to fit the rules in the help center, please edit the question.

3  
You need only check up to $n=6$... –  Mariano Suárez-Alvarez Jan 11 '10 at 3:40
3  
Though the prime factors for n=6 are not entirely obvious without a calculator... –  Jason DeVito Jan 11 '10 at 4:01
4  
This is funny; the comments are answers and the answers are comments. (Partly understandable because Wlog can't comment and the commenters probably feel it's too straightforward to answer.) If the past class had seen a solution, they would be able to reproduce it; some teachers give exam question like that, so just because they didn't have a calculator doesn't mean it wasn't doable. I don't agree with Qiaochu 100%; what you seem to be asking for is a qualitative, non-computational way to show that such a counterexample must exist without necessarily producing one. Can someone do it? –  Jonas Meyer Jan 11 '10 at 4:41
17  
I am reminded of Hendrik Lenstra's proof that there are infinitely many composite numbers: Suppose that there are only finitely many composite numbers. Multiply them together. DON'T add 1! –  Bjorn Poonen Jan 11 '10 at 6:13
6  
But what if there is only one composite number!? –  Matt Noonan Jan 11 '10 at 6:27
show 4 more comments

2 Answers 2

up vote 5 down vote accepted

Here's a possible intended solution to show that $30031 = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1$ is composite without factoring it. Recall the Fermat primality test: if $a^{n-1} \not \equiv 1 \bmod n$, then $n$ cannot be prime. It turns out that $2^{30030} \equiv 21335 \bmod 30031$, so $30031$ must indeed be composite. There is a well-known algorithm called binary exponentiation that is reasonably fast to implement by hand and that could conceivably be done on an exam. (I am not totally convinced that this would be faster than trial division until $p = 59$, though. And if you followed Leonid's suggestion in the comments your life would be even easier.)

Edit: Here is the solution by trial division. It suffices to check the primes from $17$ up. Note that the fact that we know the prime factorization of $30030$ helps a lot. All of the arithmetic necessary beyond what I wrote down was mental.

For $17$ write $30031 = 30 \cdot 77 \cdot 13 + 1 \equiv -4 \cdot 9 \cdot -4 + 1 \equiv -8 \bmod 17$.

For $19$ write $30031 \equiv -8 \cdot 1 \cdot -6 + 1 \equiv 11 \bmod 19$.

For $23$ write $30031 \equiv 7 \cdot 8 \cdot -10 + 1 \equiv -99 \bmod 23$.

For $29$ write $30031 \equiv 1 \cdot -10 \cdot 13 + 1 \equiv -100 \bmod 29$.

For $31$ write $30031 \equiv 30000 \bmod 31$.

For $37$ write $30031 \equiv -7 \cdot 3 \cdot 13 + 1 \equiv -13 \bmod 37$.

For $41$ write $30031 \equiv -11 \cdot 5 \cdot 13 + 1 \equiv -14 \cdot 13 + 1 \equiv -140 \bmod 41$.

For $43$ write $30031 \equiv -13 \cdot -9 \cdot 13 + 1 \equiv -26 \bmod 43$.

For $47$ write $30031 = 210 \cdot 143 + 1 \equiv 25 \cdot 2 + 1 \equiv 4 \bmod 47$.

For $53$ write $30031 \equiv -2 \cdot -16 + 1 \equiv 33 \bmod 53$.

Finally, for $59$ write $30031 \equiv 33 \cdot 25 + 1 \equiv 11 \cdot 16 + 1 \equiv 0 \bmod 59$.

share|improve this answer
    
Thanks for the answer, I believe this and what Leonid wrote above is the intended solution. –  kolistivra Jan 11 '10 at 15:30
add comment

I don't know a non-computational solution to this question, or even a computational solution that wouldn't make one annoyed not to be allowed to use a calculator or computer. I don't know of any theoretical reason why the statement is false, and there are similar questions involving Euclid sequences that remain open: see e.g. Problem 6 of

http://math.uga.edu/~pete/NT2009HW1.pdf

A "U" in front of a part of the problem means that it is unsolved.

I am a professional mathematician specializing in number theory who has thought at least a little bit about similar problems in the context of teaching advanced undergraduate number theory. (I am not the world's greatest problem solver, but some of the people who have already commented on this question and not given a solution meeting the criteria above are about as quick and clever as they come.) So I submit that if I cannot solve the question in a nice way, then it is not reasonable to be able to expect an undergraduate to do so on an in-class exam.

share|improve this answer
1  
I believe John Nash put unsolved problems in his exams, because he thought that if the students did not realize how hard they were, they might actually be able to solve them! –  Emil Jan 11 '10 at 10:25
    
There's a story about a famous result in computer science being solved in exactly that way, although I don't remember which one it is at the moment. –  Qiaochu Yuan Jan 11 '10 at 12:45
    
@Qiaochu - Perhaps you're thinking of George Dantzig? He arrived late to a class and confused two open problems that the prof had written on the board for homework. A few days later he turned in their solutions! –  Ben Linowitz Jan 11 '10 at 12:49
    
Thanks, now I'm more convinced that I should stop(at least until I get a little more advanced in math=)) searching for a qualitative, non-computational answer. –  kolistivra Jan 11 '10 at 15:33
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.