nt.number theory - Is the product of first $n$ prime numbers $+1$ another prime number?

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$.

• Next gr.group theory - Two finite groups with the same identical relations?
• Previous nt.number theory - Reference for Deligne's construction of Galois representations attached to modular forms