Test for Divisibility by any Prime
This test will work for any prime that is relatively prime to 10 (basically any prime other than 2 and 5).
To find out if a number is divisible by a prime, p:
1.) Break off the last digit of the number to create two numbers. Take the broken off last digit and multiply it by a positive integer n such that n=(kp+1) / 10 where k is the smallest positive integer where (kp+1) is multiple of 10. Then add it to the rest of the number. If the resulting number is divisible by p then the original number is divisible by p. (like the rule for 3, this rule can be applied repeatedly to the result)
OR
2.) Break off the last digit of the number to create two numbers. Take the broken off last digit and multiply it by (p-n) where n is a positive integer such that n=(kp+1) / 10 where k is the smallest positive integer where (kp+1) is multiple of 10. Then subtract it to the rest of the number. If the resulting number is divisible by p then the original number is divisible by p. (again, like the rule for 3, this rule can be applied repeatedly to the result)
Whether we use method 1 or 2 just depends on which method will give us a smaller multiplier.
Since that explanation was probably very difficult to understand, we will work through the steps in greater detail using 7, 11, and 13 as examples.
How to Get n and (p-n)
For any prime number, p, check for the smallest possible value of a positive integer k so that (kp + 1) is a multiple of 10.
For p = 7, (7)7 + 1 = 50, a multiple of 10. So k = 7 and n = (kp + 1) ⁄ 10 = 50 ⁄10 = 5.
For p= 11, (9)11 + 1 =100, a multiple of 10. So k = 9 and n = (kp + 1) ⁄10 = 100 ⁄10 = 10.
For p= 13, (3)13 + 1 = 40, a multiple of 10. So k = 3 and n = (kp + 1) ⁄10 = 40 ⁄10 = 4.
So,
For 7, n = 5 and (p - n) = 7 - 5 = 2
For 11, n = 10 and (p - n) = 11 - 10 = 1
For 13, n = 4 and (p - n) = 13 - 4 = 9
How to Add/ Subtract the Last Digit
Decide whether n or (p-n) will be more convenient (usually the smaller number.) If you choose n, add. If you choose (p-n), subtract. Below are examples for the primes 7, 11, and 13.
Seven
We will test the number 37499 using (p-n)=2 so we will subtract:
1.) Break the number into3749 and 9.
2.) Multiply the broken off last digit by (p-n) and subtract from the rest of the number: 3749-(2)9=3731.
3.) Now repeat: 373-(2)1=371, 37-(2)1=35, which is clearly divisible by 7, so 37499 is divisible by 7.
Eleven
We will test the number 351, 718 using (p-n)=1, so we will just subtract the broken off last digit. Now this time we will use a shorthand form of writing the process and probably the best way to write out the steps when doing it by hand.
351,718 (35171-8)
35,163 (3516-3)
3513 (351-3)
348 (34-8)
26...not divisible.
Therefore 351,718 is not divisible by 11.
Thirteen
We will test the number 595,153 using n=4, so we will add.
595153 (59515+4×3)
59527 (5952+4×7)
5980(598+4×0)
598(59+4×8)
91(9+4×1)
13...divisible
Therefore 595,153 is divisible by 13.
As evident by the title, this test can be used for any prime. However, after a certain point the arithmetic can be very unwieldy, making this method impractical. For numbers like 7,11, and 13, though, the calculations are almost immediate, making it quite useful. Below is a link for the proof of this test specifically for the numbers 7, 11, and 13, but the proof can be expanded for any prime.