How to check if a large number is prime?

Question

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?

Answer 1

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.

Answer 2

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!

Answer 3

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.