13
$\begingroup$

I know $1000!$ is not a prime number as any number $1000$ or less is a divisor, but how would I know if $1000!+1$ is prime? Any hints?

Also, use the above question to prove that you can find $n$ consecutive composite numbers.

$\endgroup$
  • 2
    $\begingroup$ You have only commented on determining whether or not $1000!+1$ is prime. What about the others in the range, do you have any thoughts on them? $\endgroup$ – Michael Albanese Dec 19 '13 at 3:17
  • 1
    $\begingroup$ $n!+r$ is divisible by $r$ for $2\le r\le n$ $\endgroup$ – lab bhattacharjee Dec 19 '13 at 3:18
  • 1
    $\begingroup$ the question explicitly says inclusive $\endgroup$ – cats Dec 19 '13 at 3:19
  • 6
    $\begingroup$ Your question about $1000!+1$ may be difficult. $\endgroup$ – André Nicolas Dec 19 '13 at 3:19
  • $\begingroup$ $n!+1$ is this sequence; I concur with @AndréNicolas that knowing if it's prime is not easy. $\endgroup$ – vadim123 Dec 19 '13 at 3:22
10
$\begingroup$

The only non-trivial case is $n=1000!+1$.

However, you can easily check with a computer that $2^{n-1} \not \equiv 1 \pmod n$, thus it's not a prime number (it's just an instance of Fermat primality test). If you want to try this yourself, use an efficient modular exponentiation method.

You may also have a look at FactorDB, which will give you a partial factorization: $$1000! + 1 = 6563 \cdot 1190737 \cdot 115205557790605547 \cdot C_{2541}$$ where $C_{2541}$ is a composite number with 2541 decimal digits.

$\endgroup$
6
$\begingroup$

Hint: $k$ divides $1000!+k$, for every natural $k\le 1000$.

$\endgroup$
  • $\begingroup$ $k\ge0$ and $\ne1$ right? $\endgroup$ – lab bhattacharjee Dec 19 '13 at 3:18
  • 4
    $\begingroup$ It's still true for $k=1$, however it doesn't exclude primality. $\endgroup$ – vadim123 Dec 19 '13 at 3:20
  • 2
    $\begingroup$ That's a good hint when $k\ge 2$. At $k=1$ it's a big number, not clear whether prime or not. $\endgroup$ – coffeemath Dec 19 '13 at 3:20
4
$\begingroup$

All the integers from $1000!+2$ up to $1000!+1000$ are clearly not prime, and a simple check verifies that $6563$ is a factor of $1000!+1$, so there are no primes in the list.

$\endgroup$
  • 1
    $\begingroup$ Please explain how to do this simple check. $\endgroup$ – vadim123 Dec 19 '13 at 14:33
  • $\begingroup$ It was a check using software. I used this command in pari/gp: N=1000!+1;forprime (p=1003,1000000,if (N%p==0,print(p))). Just to see if there were any small prime factors, and I was lucky. $\endgroup$ – Old John Dec 19 '13 at 14:37
1
$\begingroup$

I cannot give a proof, but the OEIS entry on factorial primes claims that $1000!+1$ is not prime, as 1000 isn't listed. This is likely a proof-by-computer, though.

As for the rest of the numbers in that range, everyone else has already mentioned that $k\mid n!+k$ for $1\leq k\leq n$.

$\endgroup$
0
$\begingroup$

You can use wolfram alpha to check. Not really elegant but effective :-)

http://www.wolframalpha.com/input/?i=Is+1000%21%2B1+prime%3F

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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