## Primality Testing

Expand Messages
• Lately I have been interested in primality testing: to determine whether a number, N, is prime or composite. From what I have thus far read, various tests have
Message 1 of 3 , Sep 6, 2004
Lately I have been interested in primality testing: to determine
whether a number, N, is prime or composite.
From what I have thus far read, various tests have strengths and
weaknesses.
Some tests are 100% correct, but it may take a long time to test,
comprising hundreds of hours for a computer to test a 4,000 digit
number.
Other tests can give a quick response, but at the sacrifice of
accuracy: sometimes a false answer is given.
I was wondering if there a method yet to determine with 100% accuracy
whether a number is prime or composite, in a quick amount of time.

My thinking on the subject, for what its worth, is this:
1. We can immediately say that numbers whose digits end in
0,2,4,5,6,8 are composite.
2. That leaves numbers ending with the digits 1, 3, 7, 9. Some of
these numbers are prime, some are not. To sort these out is the hard
part.
3. Of the numbers that end in the digit 9, one thing we can do is
this: if we 'cast out' that 9, and if the remaing digits are a
multiple of 3, then, the original number, N, is a composite. For
example, the following numbers are composite: 1239, 3339, 50109.
4. One thing which I thought was a correct rule but not anymore: If
you cast out the last digit 9, and then if you add 2 to the remaining
digits: if you then have a a number whose first half of its digits
are the same as its seocnd half, then that number is composite. To
illustrate: take 209. cast out the 9; add 2 to the remaining digits,
which will make 22. 209 is composite. Or take 319. Cast out the 9;
add 2 to the digits, which will make 33. 319 is composite.
This rule seems to work many times, but I have found at least one
counterexample. So I give this caveat to save somebody else trouble.

Best Regards,

Ron Dwyer
• At 06:50 PM 9/6/2004, Ronald Dwyer wrote: 3. Of the numbers that end in the digit 9, one thing we can do is ... That is of very little help because it tells
Message 2 of 3 , Sep 6, 2004
At 06:50 PM 9/6/2004, Ronald Dwyer wrote:
3. Of the numbers that end in the digit 9, one thing we can do is
>this: if we 'cast out' that 9, and if the remaing digits are a
>multiple of 3, then, the original number, N, is a composite. For
>example, the following numbers are composite: 1239, 3339, 50109.

That is of very little help because it tells if the number is divisible by
3, so that rules out very few of the cases.
Your message has been successfully submitted and would be delivered to recipients shortly.