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$
7
  • 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, 2013 at 3:17
  • 1
    $\begingroup$ $n!+r$ is divisible by $r$ for $2\le r\le n$ $\endgroup$
    – lab bhattacharjee
    Dec 19, 2013 at 3:18
  • 1
    $\begingroup$ the question explicitly says inclusive $\endgroup$
    – cats
    Dec 19, 2013 at 3:19
  • 6
    $\begingroup$ Your question about $1000!+1$ may be difficult. $\endgroup$
    – André Nicolas
    Dec 19, 2013 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, 2013 at 3:22

5 Answers 5

Reset to default
11
$\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$
3
  • $\begingroup$ $k\ge0$ and $\ne1$ right? $\endgroup$
    – lab bhattacharjee
    Dec 19, 2013 at 3:18
  • 4
    $\begingroup$ It's still true for $k=1$, however it doesn't exclude primality. $\endgroup$
    – vadim123
    Dec 19, 2013 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, 2013 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$
2
  • 1
    $\begingroup$ Please explain how to do this simple check. $\endgroup$
    – vadim123
    Dec 19, 2013 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, 2013 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .