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

Divisibility Test Table for Three Digit Numbers

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

Here is an example.

Example: Factor 611

Example: Factor 611

Advertisements

About jrh794

I am a sixty-five year old math instructor at Southern Oregon University. I taught at the College of the Siskiyous in Weed California for twenty-six years. Prior to that I worked as a computer programmer, carpenter and in various other jobs. I graduated from Rice University in 1967 and have a MS in Operations Research from Stanford. In the past I have hand-built a stone house and taken long solo bicycle tours. Now I ride my mountain bike and play golf for recreation.
This entry was posted in Math and Me, Math Explorations and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s