Associated Topics || Dr. Math Home || Search Dr. Math

### Divisibility Tests to Find the Smallest Prime Factor of a Number

```Date: 02/02/2006 at 15:27:39
From: ed
Subject: tricks to find smallest positive prime divisor of a number

How can I find the smallest positive prime divisor of 1633?  I need
to do it quickly without dividing in the standard way of finding prime
numbers, such as 1633/2 and so on.

```

```
Date: 02/02/2006 at 22:28:57
From: Doctor Greenie
Subject: Re:  tricks to find smallest positive prime devisor of a number

Hi, Ed -

Let's first discuss the problem in general of finding the smallest
prime divisor of a number.  Of course if the number is even, the
problem is trivial--the smallest prime divisor is 2.  Otherwise, we
need to check for divisibility by odd primes.

One of the first considerations is how far we have to look before
deciding (if we haven't found any divisors) that the number is prime.
The answer is that we don't need to go higher than the square root of
a number.  The square root of a number "n" is the number which
multiplied by itself gives n.  If there are two unequal integers whose
product is "n", then one of them must be larger than and the other
smaller than the square root of n.  So if we haven't found any integer
divisors by the time we reach square root of n, then we aren't going
to find any.

Next we can try divisibility rules for odd primes.  There are only
three which I find of much use.  Of course the divisibility rule for
5 is trivial.  Then, the number is divisible by 3 if the sum of the
digits is divisible by 3; and the number is divisible by 11 if the
difference between the sum of the odd-numbered digits and the sum of
the even-numbered digits is divisible by 11.  If you aren't familiar
with that divisibility rule, here is an example:

57607 is divisible by 11, because

5+6+7 = 18 (sum of odd-numbered digits - 1st, 3rd, and 5th)
7+0 = 7 (sum of even-numbered digits - 2nd and 4th)
18-7 = 11 is divisible by 11

In your specific example, a quick check using these divisibility rules
shows that 1633 is not divisible by either 3 or 11.

There are divisibility rules for other odd primes; in fact, you can
develop divisibility rules for ANY prime number.  But these are in
my opinion merely curiosities, because using them usually takes far
longer than performing the long division.  In case you are curious
about the process for developing these divisibility rules, here is a
link to a page in the Dr. Math archives where the process is
discussed and demonstrated:

Finding Divisibility Rules for Large Numbers
http://mathforum.org/library/drmath/view/55962.html

The fastest method I know for checking for divisibility by odd
primes involves adding or subtracting multiples of the prime divisor
being tested to get trailing zeros and then dropping those zeros.

Here is how I could find that, using the example above, 57607 is
divisible by 11 using this method:

57607+33 = 57640
5764-44 = 5720
572-22 = 55

55 is divisible by 11, so the original number is also.  The
reasoning is as follows:

(1) 57607 is divisible by 11 if and only if 57607+3(11) = 57640 is
(2) 57640 is divisible by 11 if and only if 5764 is
(3) 5764 is divisible by 11 if and only if 5764-4(11) = 5720 is
(4) 5720 is divisible by 11 if and only if 572 is
(5) 572 is divisible by 11 if and only if 572-2(11) = 550 is
(6) 550 is divisible by 11 if and only if 55 is
(7) 55 IS divisible by 11; therefore 57607 is divisible by 11

At this point in your specific problem, we simply need to apply this
method for finding the smallest prime factor of 1633.  The prime
divisors we might need to check are the following:  7, 13, 17, 19, 23,
29, 31, 37.  (As discussed earlier, we don't need to go higher than 37
since the square root of 1633 is just over 40.)

We use the method described above; I will display the process rather
cryptically to save time and space...!!

7:  1633; 1640; 164; 150; 15  no...
13:  1633; 1620; 162; 110; 11  no...
17:  1633; 1650; 165; 80; 8    no...
19:  1633; 1690; 169; 150; 15  no...
23:  1633; 1610; 161; 230; 23  YES!!

If we are to find the full prime factorization, we then simply divide
1633 by 23 to find the result.  We can perform long division for this,
or we can use logic.  Using estimation, we see that 1633/23 is about
70; and since the final digit of both numbers is "3", it should be
(and is!) 1633/23 = 71.

I hope some of this helps.  Please write back if you have any further

- Doctor Greenie, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Number Theory
Middle School Factoring Numbers

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search