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$ Dec 19, 2013 at 3:17
  • 1
    $\begingroup$ $n!+r$ is divisible by $r$ for $2\le r\le n$ $\endgroup$ 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$ 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

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

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.