Prime Number Heuristics?

For mathematicians working with number theory, discovering the next biggest prime involves dividing an unknown number by sucessively larger known primes. (Very tedious)
Some short cuts are available, though.
Excepting 2, all even numbers are not prime.
Excepting 5, all numbers that end with 0 or 5 are not prime.
So, basically, all numbers ending with 0,2,4,5,6,8 are out.
Another short cut is this:
If a number’s digits are added up, and That number is divisible by 3, then the original number is divisible by 3.
92418
9+2+4+1+8=24…divisible by 3

Are there any other short-cuts for numbers besides 2,3,or 5?

You realize, of course, that by judiciously multiplying using only those numbers, you can create ALL numbers except 1 and 2. Simply because of that I would guess that those are the only rules that apply.

However, I could be wrong.

Damn, now I want to know :smiley: .

Yes, there’s a rule for every prime, although the rules get harder as the prime gets larger. Consider 7:

Since the following things are true:

1 leaves a remainder of 1 when divided by 7.
10 leaves a remainder of 3 when divided by 7.
100 leaves a remainder of 2 when divided by 7.
1,000 leaves a remainder of 6 when divided by 7.
10,000 leaves a remainder of 4 when divided by 7.
100,000 leaves a remainder of 5 when divided by 7.
1,000,000 leaves a remainder of 1 when divided by 7.
10,000,000 leaves a remainder of 3 when divided by 7.
100,000,000 leaves a remainder of 2 when divided by 7.
1,000,000,000 leaves a remainder of 6 when divided by 7.

This is repeating already (and you can show that it will continue to repeat the cycle 1,3,2,6,4,5). So what you do to tell if something is divisible by 7 is:

Multiply the one’s digit by 1. Find the remainder when divided by 7.
Multiply the ten’s digit by 3. Find the remainder when divided by 7.
Multiply the hundred’s digit by 2. Find the remainder when divided by 7.
Etc. (Continue to use the multipliers in the cycle 1,3,2,6,4,5.)

Now add up the remainders. Find the remainder of the sum when divided by 7. If the original number is divisible by 7, the remainder of the sum will be 0.

There’s an easier way to check for divisibility by 7, although (unlike Wendell Wagner) I don’t know the actual mathematical justification for it.

  1. Split the number in two by separating the last digit (i.e., if your number is 1234, split it into the number 123 and the number 4). Call the first part (all digits except the last) number A.

  2. Multiply the last digit by 2: (2*4=8) Call this Result B.

  3. Subtract the smaller of A and B from the larger, always getting a positive result: (123-8=115)

  4. If the original number was a multiple of 7, the result of step 3 will be either 0 or a multiple of 7. Since all multiples of 7 follow this rule, you can continue reducing until you get a result that’s easy to test by division or visual inspection.

Examples:
A. 63: 2*3=6 ,6-6=0, and 63 is a multiple of 7.

B. 14: 4*2=8, 8-1=7, and 14 is a multiple of 7

C. 343: 23=6, 34-6=28, 82=16, 16-2=14, and 14 is a multiple of 7.

D. 1234: 42=8, 123-8=115, 25=10, 11-10=1 1234 is not a multiple of 7 (check it yourself).

There’s also a fairly trivial way to check for divisibility by 11, and this one’s easy to explain. Since 11=10+1 (duh), and our numbering system is based on powers of 10, we can use the fact that 10==10[sup]1[/sup] * 1 (again, duh) to check divisibility by 11. Any number divisible by 11 will have a digit pattern of


e                  |       descending
d+e                |         place
c+d                |         vaues
b+c     (100's)    |
a+b      (10's)  \ | /
a        (1's)    \ /

due to the way base 10 numbers are formatted.

if we sum all the “odd” digits, starting at the ones place, we would get a+ (b+c)+ (d+e)=a+b+c+d+e. Likewise, the sum of the “even digits” will be (a+b)+ (c+d)+e, which is identical. Therefore, you can test any number for divisibility by 11 in the manner described, simply by summing every other digit and checking if they are the same.

Don’t know any other tricks like this, sorry :frowning:

Here you go enolancooper, a theorem that “will generate a divisibility test for any natural number
relatively prime to ten”, which of course includes any prime number > 5.