Notices
Results 1 to 12 of 12

Thread: Prime numbers

  1. #1 Prime numbers 
    Forum Sophomore Stranger's Avatar
    Join Date
    Sep 2005
    Posts
    148
    Hi,

    Is there an easy way to know whether a number ending with "9" (e.g. 1073792449) is a prime number or not? I'm not familiar with the "mod" thing.

    And in general, are there characteristic conditions for a number ending with "9" to be a prime number?

    Thanks


    Watch what thy eyes can't see... and live it.

    (T.B)
    Reply With Quote  
     

  2.  
     

  3. #2  
    Forum Radioactive Isotope mitchellmckain's Avatar
    Join Date
    Oct 2005
    Location
    Salt Lake City, UTAH, USA
    Posts
    3,112
    Not that I have ever heard. As far as I know you have to eliminate possible prime factors starting with,

    2 - all even numbers
    3 - all numbers whose digits add up to a number divisible by 3
    5 - all numbers ending in 5 (those ending in 0 already eliminated)

    But I dont even know of any tricks for prime factors higher than 5.

    Something ending in a 9 could have a prime factor of 3, 11, 13, 17 to name a few so don't see how there could be any such easy way as you are suggesting.

    3 x 13 = 39
    13 x 23 = 299
    11 x 19 = 209
    17 x 37 = 629

    There are some formulas for likely prime numbers involving powers of 2, but again I have heard of nothing like what you are talking about.


    See my physics of spaceflight simulator at http://www.relspace.astahost.com

    I now have a blog too: http://astahost.blogspot.com/
    Reply With Quote  
     

  4. #3  
    Forum Bachelors Degree
    Join Date
    May 2005
    Location
    London, England
    Posts
    405
    There is no formula for determining whether any number is prime, only for determining if it's not prime. There's nothing special for numbers which end in 9, only for numbers where the digits add up to a multiple of 9. Numbers which add up to a multiple of 9 are divisible by 9 - this is a consequence of 9 being the largest digit (ie one less than the base). (The fact that the same is true for multiples of 3 where the digits add up to a multiple of 3 derives from the fact that 3 is a factor of 9, and therefore divides into base 10 with a remainder of 1).
    Reply With Quote  
     

  5. #4  
    Forum Sophomore
    Join Date
    Jul 2005
    Posts
    121
    Quote Originally Posted by Silas
    There is no formula for determining whether any number is prime, only for determining if it's not prime.
    I'm not sure what you mean by this, but there are plenty of primality tests that can determine if a number is prime. A simple (but innefficient) one: p is prime if and only if p divides (p-1)!+1 (Wilson's theorem).

    Ahh- by 'formula' you're maybe talking only about using quick divisibilty tests to determine if a number is divisible by 2, 3, 5, or whatever and then concluding it's composite? Then absolutely.

    ----

    There's no special test that I've ever seen with respect to 9 or any other last digit, apart from the obvious that the last digit must be 1,3,7,or 9 to be prime (except 2 or 5). This is essentially just 'pre-sieving' by removing all multiples of 2 and 5. Also fun is that the primes are evenly distributed in an asymptotic sense amongst the last digits 1,3,7, and 9 (prime number theorem for arithmetic progressions).
    Reply With Quote  
     

  6. #5  
    Forum Radioactive Isotope mitchellmckain's Avatar
    Join Date
    Oct 2005
    Location
    Salt Lake City, UTAH, USA
    Posts
    3,112
    Quote Originally Posted by shmoe
    Quote Originally Posted by Silas
    There is no formula for determining whether any number is prime, only for determining if it's not prime.
    I'm not sure what you mean by this, but there are plenty of primality tests that can determine if a number is prime. A simple (but innefficient) one: p is prime if and only if p divides (p-1)!+1 (Wilson's theorem).

    Ahh- by 'formula' you're maybe talking only about using quick divisibilty tests to determine if a number is divisible by 2, 3, 5, or whatever and then concluding it's composite? Then absolutely.

    ----

    There's no special test that I've ever seen with respect to 9 or any other last digit, apart from the obvious that the last digit must be 1,3,7,or 9 to be prime (except 2 or 5). This is essentially just 'pre-sieving' by removing all multiples of 2 and 5. Also fun is that the primes are evenly distributed in an asymptotic sense amongst the last digits 1,3,7, and 9 (prime number theorem for arithmetic progressions).
    Way cool formula (Wilson theorem). I had to test it up to 11 just to see it work. I would love to see the proof of that. Though the ineffeciency here practically proves the point. Imagine trying to use this with just a 5 digit candidate for a prime! After all, if Silas was really wrong about what he said then public key encryption would be broken.
    See my physics of spaceflight simulator at http://www.relspace.astahost.com

    I now have a blog too: http://astahost.blogspot.com/
    Reply With Quote  
     

  7. #6  
    Forum Sophomore
    Join Date
    Jul 2005
    Posts
    121
    Quote Originally Posted by mitchellmckain
    Way cool formula (Wilson theorem). I had to test it up to 11 just to see it work. I would love to see the proof of that.
    If p is prime just pair multiplicative inverses mod p and the result follows. If n divides (n-1)!+1 and n=ab with a<n, then a divides (n-1)! and a divides (n-1)!+1 so a divides 1, hence a=1 so n is prime.

    This will be in any elementary number theory text as well.

    Quote Originally Posted by mitchellmckain
    Though the ineffeciency here practically proves the point. Imagine trying to use this with just a 5 digit candidate for a prime! After all, if Silas was really wrong about what he said then public key encryption would be broken.
    I think I figured out what he meant (the "Ahh-.." paragraph).

    Wilsons is crap for applications, but there are other quite zippy primality tests ('zippy' being a subjective term). You wouldn't have rsa public key cryptography without these tests as you need to be able to find two large primes for it to work. Note that proving a number is prime or composite is a much easier problem than factoring a number with the current published algorithms. This is necessary for the security of rsa, we can find two 'large enough' primes p and q pretty fast that make factoring n=pq extremely time consuming for someone who only knows n.
    Reply With Quote  
     

  8. #7  
    Forum Radioactive Isotope mitchellmckain's Avatar
    Join Date
    Oct 2005
    Location
    Salt Lake City, UTAH, USA
    Posts
    3,112
    Quote Originally Posted by shmoe
    If p is prime just pair multiplicative inverses mod p and the result follows. If n divides (n-1)!+1 and n=ab with a<n, then a divides (n-1)! and a divides (n-1)!+1 so a divides 1, hence a=1 so n is prime.
    Ok I get most of that. Just not the first part completely (the if part of the iff = "if and only if"). Since p is prime, we can assume p>2 and so p is odd. So p-1 is even and I guess there is some guarantee that all the numbers below p-1 and greater than 1 pair off as multiplicative inverses mod p so you get (p-1)! mod p = 1 x 1 x 1 x .... x (p-1) = p-1 so that when you add 1 you get p proving that (p-1)!+1 is divisible by p. I mean I could see this happen in an example but did not know that there was something to guarantee that all the numbers below p-1 and greater than 1 pair off as multiplicative inverses mod p. (I am good at math but I'm a physicist not a mathematician)
    See my physics of spaceflight simulator at http://www.relspace.astahost.com

    I now have a blog too: http://astahost.blogspot.com/
    Reply With Quote  
     

  9. #8  
    Forum Sophomore
    Join Date
    Jul 2005
    Posts
    121
    For any a, the congruence ax=1 (mod n) has a solution when a and n are relatively prime (use generalized euclidean algorithm to write 1 as a linear combination of a and n), so mod p we know 2, 3, ..., p-1 all have multiplicative inverses (actually {1,2,..,p-1} form a group under multiplication mod p, and these inverses will be unique).

    The only one of 2, 3, .., p-1 that is it's own inverse is p-1, which can be seen by considering x^2=1 (mod p), which implies p divides x+1 or x-1 so x is 1 or -1 mod p.
    Reply With Quote  
     

  10. #9  
    Forum Radioactive Isotope mitchellmckain's Avatar
    Join Date
    Oct 2005
    Location
    Salt Lake City, UTAH, USA
    Posts
    3,112
    Aahh... Of course, p-1 = -1 mod p! I couldn't think why p-1 was special. Though I have also just realized that (p-1)(p-1) = p^2 - 2p + 1 = 1 mod p.

    In fact, if I remember correctly doesn't ax = b (mod p) always have a solution when p is prime?
    See my physics of spaceflight simulator at http://www.relspace.astahost.com

    I now have a blog too: http://astahost.blogspot.com/
    Reply With Quote  
     

  11. #10  
    Forum Sophomore
    Join Date
    Jul 2005
    Posts
    121
    Quote Originally Posted by mitchellmckain
    In fact, if I remember correctly doesn't ax = b (mod p) always have a solution when p is prime?
    Close, but not if a=0 (mod p) and b is non zero (mod p), hence the a and p relatively prime bit, which is satisfied for all a that are not 0 mod p of course (this may be what you were thinking of).
    Reply With Quote  
     

  12. #11  
    Forum Radioactive Isotope mitchellmckain's Avatar
    Join Date
    Oct 2005
    Location
    Salt Lake City, UTAH, USA
    Posts
    3,112
    Quote Originally Posted by shmoe
    Quote Originally Posted by mitchellmckain
    In fact, if I remember correctly doesn't ax = b (mod p) always have a solution when p is prime?
    Close, but not if a=0 (mod p) and b is non zero (mod p), hence the a and p relatively prime bit, which is satisfied for all a that are not 0 mod p of course (this may be what you were thinking of).
    Well what I was thinking was that for prime p every column of the mod p multiplication table (excepting the 0 column) includes all the members of the group (represented by all the numbers less than p).
    See my physics of spaceflight simulator at http://www.relspace.astahost.com

    I now have a blog too: http://astahost.blogspot.com/
    Reply With Quote  
     

  13. #12  
    Forum Sophomore
    Join Date
    Jul 2005
    Posts
    121
    Quote Originally Posted by mitchellmckain
    Well what I was thinking was that for prime p every column of the mod p multiplication table (excepting the 0 column) includes all the members of the group (represented by all the numbers less than p).
    Absolutely. The only exception to the ax=b mod p having a solution is just the possibilty of a=0 (and b non zero), I was just being picky and pointing this out.
    Reply With Quote  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •