Thread: Prime numbers

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

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.

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).

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).

Originally Posted by shmoe

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.

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.

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.

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)

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.

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?

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).

Originally Posted by shmoe

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).

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.