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 
questions about any of this.

- Doctor Greenie, The Math Forum
  http://mathforum.org/dr.math/