Results 1 to 10 of 10

Math Help - Prove a large number is prime

  1. #1
    Junior Member
    Joined
    Sep 2010
    Posts
    64

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    Quote Originally Posted by DrSteve View Post
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    There are also probabilistic methods which can determine the primality of a number to within any desired probability.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by juanma101285 View Post
    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Nov 2010
    Posts
    56
    Thanks
    16
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Sep 2010
    Posts
    64
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    Quote Originally Posted by Petek View Post
    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
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Ackbeet View Post
    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
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: September 24th 2011, 11:23 AM
  2. Prime factoring a large number.
    Posted in the Algebra Forum
    Replies: 5
    Last Post: September 10th 2011, 04:10 AM
  3. Prove composite number has a prime divisor
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: January 25th 2011, 04:44 PM
  4. Comparing large prime powers.
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: November 9th 2010, 07:08 AM
  5. Generating Large Prime Numbers
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: July 26th 2009, 02:08 PM

Search Tags


/mathhelpforum @mathhelpforum