## Factoring Three Digit Numbers using Divisibility Tests

Revision to this post. November 20, 2014

I woke up last night and to try to go to back to sleep I started dividing numbers in my head by 23.  Found that I had missed a couple of multiples of 23 in the list below.  My edits are in bold.

To keep myself occupied when I walk through town, I like to factor three digit numbers. Since Oregon license plate identifiers have three numerical digits and three alphabetic characters,  I have a “random” supply of numbers to factor. My current favorite three digit number is $611$.
This is why divisibility tests have interested me. (See these last two posts: Divisibility by 13 and Divisibility by 17.) Generally when I wanted to factor a number I would just try dividing by various primes, but now, based on the understanding I gained exploring divisibility by 13 and 17, I have a systematic procedure. In outline, test a three digit number for divisibility by all primes through 19. (Now 23) If successful, divide out the prime and iterate.  If no success, check to see if the number is one of six particular numbers.

First the six particular numbers. If a three digit number is not divisible by any prime number up through 19, then it could only be the product of primes $23, 29$ and $31$.  These three digit numbers are $23^2=529, 23\cdot29 =667, 23\cdot31=713, 29^2 = 841, 29\cdot31 = 899, and 31^2 = 961$.  Also 23 times 37 equals 851, 23 times 41 equals 943, and 23 times 43 equals 989.  There are now too many numbers here.  So I have added a divisibility test for 23 below.

Use this divisibility test table for primes through $19$.  $n|x$ means $n$ divides $x$ with no remainder.  Modulo  $11$ means remainder after dividing by $11$.

Divisibility Test Table for Three Digit Numbers

For divisibility by 23 use 23|8a+10b+c.

Here is an example.

Example: Factor 611