5
$\begingroup$

Is $31!+1$ a prime number?

Prime numbers can be written as $6n+1$ or $6n-1$ form.

$31!+1$ can also be written as $6n+1$,but not every number of the form $6n+1$ is prime.

How do I proceed efficiently?

$\endgroup$
  • 4
    $\begingroup$ That one happens to be divisible by $257$. If your number has a small prime factor then trial and error can find it. Otherwise...well Primality Testing is a very complicated topic. $\endgroup$ – lulu Aug 16 '16 at 16:22
  • 4
    $\begingroup$ Note: the remark about $6n\pm 1$ isn't terribly relevant. All that means is that your number is not divisible by $2$ or $3$. Worth checking, of course, but there are lots of other primes to test. $\endgroup$ – lulu Aug 16 '16 at 16:26
  • 2
    $\begingroup$ For candidates as small as $31!+1, especially when it has a nice simple expression, you look them up in FactorDB. $\endgroup$ – Henning Makholm Aug 16 '16 at 16:37
  • $\begingroup$ @lulu you've linked to a page about critical points. Intentional? $\endgroup$ – Rishav Aug 16 '16 at 16:39
  • 1
    $\begingroup$ Well, if you're okay with using Wolfram|Alpha: wolframalpha.com/input/?i=factors+of+31!+%2B+1 $\endgroup$ – heather Aug 16 '16 at 16:44
2
$\begingroup$

The simplest test is to start with trial division by small primes. Your statement that it is $6n+1$ represents trial division by $2$ and $3$. You can keep going until you get tired. Then try Fermat's little theorem, which says that for $p$ prime and $a$ coprime to $p$, $a^{p-1} \equiv 1 \pmod p$, so see if $2^{8222838654177922817725562880000000} \equiv 1 \pmod {8222838654177922817725562880000001}$ You can do this rather quickly by computer if you have the right package. If this equivalence fails, you have a composite. If it passes, check a few other small primes. If it passes them all, you almost certainly have a prime.

$\endgroup$
1
$\begingroup$

You can use AKS primality test, which runs in polynomial time.

It has you check if the number is a power, and other quite simple steps.

Here you can find implementations of this algorithm in various programming languages, just in case you are looking to use it in a program of yours.

$\endgroup$
  • $\begingroup$ As written in neon pink on that page, the task is not the AKS test. It is really too bad the task has that name. Note that even when considering the real AKS test, there are far faster methods known. $\endgroup$ – DanaJ Aug 18 '16 at 23:57
1
$\begingroup$

Well, first, you can narrow it down a tad.

$31! + 1 = 8222838654177922817725562880000001$

Then, you only need to check numbers up to the square root of the number, because if you have one factor larger than the square root, the other will be smaller.

$\sqrt{8222838654177922817725562880000001} = 90679869067935485.290072114674109180313966488379724733$

which if you round is $90679869067935485$.

Which is also a really large number. Then of course, you only need to check prime factors of number (aka, you can check 5, but you don't need to check 100). And then, after that?

Plug and chug is one way you can go, or you can plug it in to Wolfram|Alpha if you're okay with that. There are also primality tests (I'll be updating this answer with more information).

Finally, below is given some python code that checks if a number is prime (don't plug in $31! + 1$, but the solution to that):

# Python program to check if the input number is prime or not

# take input from the user
num = int(input("Enter a number: "))

# prime numbers are greater than 1
if num > 1:
   # check for factors
   for i in range(2,num):
       if (num % i) == 0:
           print(num,"is not a prime number")
           print(i,"times",num//i,"is",num)
           break
   else:
       print(num,"is a prime number")

# if input number is less than
# or equal to 1, it is not prime
else:
   print(num,"is not a prime number")

Of course, 31! + 1 is not prime; it is divisible by 257, among other numbers.

Hope this helps!

$\endgroup$
  • $\begingroup$ "Plug and chug is really the only way you can go" - not really. Primality testing can be done in polynomial time, rather than the exponential algorithm you've just described. There are also fast probabilistic tests. $\endgroup$ – Patrick Stevens Aug 16 '16 at 17:32
  • 1
    $\begingroup$ @PatrickStevens, my apologies; I'll update my answer. Thank you! $\endgroup$ – heather Aug 16 '16 at 17:36

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.