Finding prime factors

This is an entry for those of you who would like to have a quick mental-calculation method to see whether one number is a factor of another number, or to find out whether your number is prime. [The size of the number that you could investigate will depend on your confidence in your short term memory.]

So, if we take the number a = 493 as an example.
We can see that it is not divisible by 2 (the right-hand most digit is an odd number), 3 (the digits do not add up to a multiple of 3) or 5 (the right-hand most digit is neither 5 nor 0).

Apart from actually doing the sums, is there a way of finding out whether 493 is divisible by other prime numbers like 7, 11, 13 and 17? While in this case it is easy to see that 493 is not divisible by 7, I would still like to use 'Is 7 a factor of 493?' as an example of a method to find prime factors for a given number.

In order to understand this method, let's ask the following question: Why did I say that it is easy to see that 493 is divisible by 7?

The reason is that we know that 490 is divisble by 7 and that 3 is not divisible by 7, therefore 490 + 3 cannot be divisible by 7. In other words, if 493 minus a multiple of seven is not divisible by seven, then 493 is not divisible by 7.

Another multiple of 7 is 21.

21 is interesting in that 21*3 = 63. i.e. 21 multiplied by the last digit of our number (493) gives a number that also ends in 3.

493 - 63 = 430. Now we know that 42 is multiple of 7, therefore 43 is not. It follows then that 430 is not divisible by 7, and from our previous reasoning, this means that 493 is also not divisible by 7. A useful observation is that we can just ask if (49 - 6) [i.e. (49 - 2*3)] is divisible by 7.

The first step in our method is thus to find a multiple of our divisor that ends in 1.

1. Multiply the divisor by a number such that the product will have 1 as its right-hand most digit. In this case 7 * 3 = 21.

2. Subtract 1 from this product and divide by 10 to give y. In this case y = (21-1)/10 = 2. [i.e. Chop off the one!]

3. Multiply the right-hand most digit by y to give r (3y = 6 = r).

4. Chop the right-hand most digit off the original number a to give b (493 -> 49).

5. Substract r from b to give c (c = 49-6 = 43 ).

6. Ask the question: Is c divible by 7? If yes, then a is divisible by 7. If no, then a is not divible by 7. If uncertain, repeat steps 3-6 using c instead of a. If c = 0 then a is divisible by 7. In this case, 43 is not divisible by 7, therefore 493 is not divisible by 7.

What about 11?
We don't need to multiple 11 by anything to get a product ending in 1. We just use '1'.
49-3 = 46. 46 is not divisible by 11, therefore neither is 493.

What about 13?
1. 13*7 = 91
5. 49 - 9*3 = 22.
6. 22 is not divisible by 13, therefore neither is 493.

What about 17?
1. 17*3 = 51
5. 49 - 5*3 = 34
6. 34 is divible by 17, therefore so is 493.

What about 19?
1. 19*9 = 171
5. 49 - 17*3 = 49 - 51 = 2
6. 2 is not divisible by 19, therefore neither is 493.

What about 23?
1. 23*7 = 161
5. 49 - 16*3 = 1
6. 493 is not divisible by 23.

What about 29?
1. 29*9 = 261
5. 49 - 26*3 = -29.
6. 493 is divisible by 29.