FINDING A PRIME FACTORS
1:33 AM
Muhammad Yusuf
, Posted in
EXAMPLE 1
Prove the following
numbers are composite by finding a prime factor.
70272753, 2663683,
304603, 32821.
Solution:
1. 7 + 0 + 2 + 7 +
2 + 7 + 5 + 3 = 33 which is divisible by 3, so 3 is a factor of
70272753.
2. 2+6+6+3+6+8+3 =
34 so it is not divisible by 3. But, 2 – 6 + 6 – 3 + 6 – 8 + 3
= 0, so 11 is a factor.
3. We find that 3,
11, and 7 are not factors, but 13 is a factor because
30460
+ 4(3) = 30472
3047 +
4(2) = 3055
305 +
4(5) = 325
32 +
4(5) = 52
5 +
4(2) = 13
4. Using our
methods above, we find that 32821 is not divisible by 2, 3, 5, 7, 11, or 13.
What now? We try the next few primes using long division. We find that 17 and
19 are not factors, but 32821 = 23 x 1427.
EXAMPLE 2
Find the prime factorization of 663993.
Solution:
From our
divisibility for 3 trick, this is clearly divisible by 3. We get by division
663993 = 3 x 221331.
We have
2+2+1+3+3+1 = 12, so it is divisible by 3. We get 221331 = 3 x 73777.
Now 7 + 3 + 7 + 7
+ 7 = 31, so it is not divisible by 3. But, 7-3 + 7 -7 + 7
= 11 so it is divisible by 11. 73777 = 11 x 6707.
We already know
6707 is not divisible by 3 as 73777 wasn't. So, we check 11, 13, 17, and then
find 19 is a factor. We get 6707 = 19 x 353. What about 523? Since 192 = 361,
and we know that it is not divisible by a prime less than 19, it must be prime.
Thus, 663993 = 32 x 11 x 19 x 353.
This method works
very poorly if all of the prime factors of a number are very large.
The worst case
would be for a number like 39203 = 197 x 199 (note that 197 and 199 are both
prime). We would have had to check 45 primes before we found a single factor, and
the number is only 5 digits long! We now look at another factoring algorithm
invented by Fermat, which will actually check for large factors that are close
together.
0 Response to "FINDING A PRIME FACTORS"
Post a Comment