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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.