# Prove a large number is prime

• Jan 20th 2011, 04:43 AM
juanma101285
Prove a large number is prime
Hi, I have been told about the following in class:

A positive integer p>1 is said to be prime if
d | p and d is a natural number implies d=p or d=1.

However, I cannot apply that to very large numbers (in the thousands). Does anyone know how to check if a large number is prime? Thanks a lot.
• Jan 20th 2011, 04:46 AM
DrSteve
It depends how large. Determining if a number is prime can actually be quite difficult. If the number is not "too" large, then you can do the following:

Check if the number is divisible by each prime up to the square root of the number. If not, then the number is prime.
• Jan 20th 2011, 05:22 AM
chisigma
Quote:

Originally Posted by DrSteve
It depends how large. Determining if a number is prime can actually be quite difficult. If the number is not "too" large, then you can do the following:

Check if the number is divisible by each prime up to the square root of the number. If not, then the number is prime.

For some 'large numbers' there are specific tests to extablish if a numer is prime without a systematic search of factors. An example are the so called 'Marsenne primes' that are of the form $M_{n}= 2^{n}-1$ , where n is a prime number. For the 'Marsenne primes' a specific procedure known as 'Lucas-Lehmer test' can be used...

Lucas-Lehmer Test -- from Wolfram MathWorld

Kind regards

$\chi$ $\sigma$
• Jan 20th 2011, 05:47 AM
Ackbeet
There are also probabilistic methods which can determine the primality of a number to within any desired probability.
• Jan 20th 2011, 06:14 AM
CaptainBlack
Quote:

Originally Posted by juanma101285
Hi, I have been told about the following in class:

A positive integer p>1 is said to be prime if
d | p and d is a natural number implies d=p or d=1.

However, I cannot apply that to very large numbers (in the thousands). Does anyone know how to check if a large number is prime? Thanks a lot.

You can check if a number of moderate size is prime by checking it for divisibility by all primes less than or equal to its' square root.

So a four digit number will at worst have to be checked against the 25 primes less than or equal 97.

Here we are using the result that if a number is composite (non-prime) then it has a prime divisor at most equal to its' square root.

CB
• Jan 20th 2011, 10:12 AM
Petek
If you don't need a formal proof that a number is prime, you can use Wolfram Alpha. Just input factor xxxxxx, where xxxxxx is the number in question. It handles 20-digit numbers almost instantly. You also can input expressions such as factor 2^107 - 1. If the number isn't prime, it will display its factorization into primes.
• Jan 20th 2011, 10:30 AM
juanma101285
Thanks a lot for your answers! I will be getting more proofs of the same type next week so all this is going to help me quite a lot.
• Jan 20th 2011, 12:44 PM
chisigma
Quote:

Originally Posted by Petek
If you don't need a formal proof that a number is prime, you can use Wolfram Alpha. Just input factor xxxxxx, where xxxxxx is the number in question. It handles 20-digit numbers almost instantly. You also can input expressions such as factor 2^107 - 1. If the number isn't prime, it will display its factorization into primes.

According to...

A000043 - OEIS

... $2^{107}-1$ is prime...

Kind regards

$\chi$ $\sigma$
• Jan 21st 2011, 03:41 PM
undefined
Quote:

Originally Posted by Ackbeet
There are also probabilistic methods which can determine the primality of a number to within any desired probability.

To add, you might also be interested in these deterministic tests: Miller's test (which relies on an unproven conjecture); Miller-Rabin restricted to smaller integers for which we only need to test a handful of potential witnesses; and AKS.

Wikipedia - Miller-Rabin primality test, subheading Deterministic variants of the test

MathWorld - AKS Primality Test
• Feb 1st 2011, 11:17 PM
Bacterius
You can also type "Primality your number" or "PrimeQ[your number]" in Wolfram Alpha, it'll simply return the primality of the number (I'm not sure about the inner workings of the algorithm but I'm pretty sure it's based on Miller-Rabin & a precomputed prime table, it's probably documented in Mathematica under the PrimeQ function anyway). It wouldn't make much of a difference for typical numbers under 80 digits, but on bigger numbers it will be much, much faster (try factoring a random 500-digit integer, it'll likely time out, but on the other hand primality testing of the same number is instantaneous). It'll in addition give you the factors if the number is small enough and if there's any trivial factor.