Divisibility Criteria for Prime Numbers

Math 300

R. S. Wilson

When expressing a number as a product of primes, it is helpful to have criteria for deciding if a particular prime will go into the number. We will present criteria for telling if 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, and 37 go into a number as well as a procdure for generalizing the techniques for all the prime except 2 and 5.

2: If the last digit is 0, 2, 4, 6, or 8, then 2 goes into the number

3: If the sum of the digits is divisible by 3, then the number is divisible by 3. This also works for 9. If the sum of the digits is divisible by 9 then the number is divisible by 9. However, this method will not work for 6. 36 is divisible by 6 even though the sum of the digits, 9, is not, and 15 is not divisible by 6 even though the sum of the digits is 6.

5: If the last digit is 0 or 5, then the number is divisible by 5.

7: Split off the last digit. Double it and subtract that from the number that is left. If the result is divisible by 7 then so is the original number. Since the result will have one fewer digits than the original number, this will be an easier problem. You may need to repeat the process several times to get a number small enough to be able to tell easily if 7 goes into the result. This method also works for 3. If the result is divisible by 3 then so is the original number, but the sum of the digits method is easier for 3.

11: Take the sum of every other digit. Then take the sum of the other every other digits. If the difference is divisible by 11 (and 0 = 0x11 is divisible by 11), then the number is divisible by 11.

13: There are two methods. The first is like the method for 7. Split off the last digit, multiply by 9 and subtract from the rest of the number. If the result is divisible by 13, then so is the original number. This method also works for 7.

The second method is like the one for 9: Split off the last digit, multiply by 4 and add to the rest of the number, The second method is probably easier than the first

17: Split off the last digit, multiply by 5 and subtract the product from the rest of the number. If the result is divisible by 17 then so is the original number.

19: Split off the last digit, multiply it by 2 and add the product to the rest of the number. If the result is divisible by 19, then so is the original number.

23: Split off the last digit, multiply by 7 and add the product to the number that is left. If the result is divisible by 23 then so is the original number.

29: Split off the last digit, multiply by 3 and add the product to the number that is left. If the result is divisible by 29 then so is the original number.

31: Split off the last digit, multiply by 3 and subtract the product from the number that is left. If the result is divisible by 31 then so is the original number.

37: Split off the last digit, multiply by 11, and subtract the product from the number that is left. if the result is divisible by 37 then so is the original number.

While these methods can be generalized to work for any prime number except 2 and 5, at this point, it becomes easier to simply divide the number by the prime in question. Moreover, at some point, it will be necessary to actually divide the nuber by the prime to see if the quotient has gotten to be smaller than the divisor. If no prime works by the time the quotient gets to be smaller than the divisor, the number is prime.