Prime Factorization Examples.Problem A: Find the prime decomposition of 158 A long solution follows. It includes all the details. A more compact version would be in order when a student follow the pattern. Long Solution: Squaring the first six primes 2, 3, 5, 7 or 11 and 13 squared give the sequence 4, 9, 25, 49, 121 and 169 of whole numbers. Here p = 2, 3, 5, 7 and 11 have the property that p2 < 156 Step 1: List the possible primes factors with p2 < N = 158
Find the smallest prime, if any, in the list which is a divisor of N? Here the smallest prime is 2, as N = 158 = 2 x 78 = 2 x N' Step 2: List the possible primes factors with p2 < 78 = N'
Find the smallest prime, if any, in the list which is a divisor of N'? Here the smallest prime is 2, as N' = 78 = 2 x 39 = 2 x N'' Step 3: List the possible primes factors with p2 < 39 = N''
Find the smallest prime, if any, in the list which is a divisor of N'? Here the smallest prime is 3 as N'' = 39 = 3 x 13 = 3 x N''' List the possible primes factors with p2 < 13 = N''
No prime in the list divides 13. So 13 is prime. Step 4: We conclude N = 2 x N' = 2 x 2 x N'' = 2x2x3xN''' = 2x2x3 x 13 So the prime decomposition of 158 = 2231(13)1 Note to avoid ambiguity, for the square of a whole number like 345 write (345)2 instead of 3452. Problem B: Find the prime decomposition of 4581 Solution: Before listing all primes p with p2 < 4581, let us get smaller numbers. Observe modulo 9, 4581 = 4+ 5 + 8 + 1 = 0. So 4581 = 9 x 509. So we need to find the prime decomposition (a.k.a factorization) of 509 < 625 = 252. The list of primes < 25 is as follows. 2, 3, 5, 7, 9, 11, 13, 17, 19, 23. Immediately, divisibility rules say 509 is not a multiple of 2, 3, 5, 9 and 11 as the last digit is odd, the sum of digits is nonzero modulo 3 and 9, the last digit is not a 5 and as
The foregoing gives a reduce set of primes
that could be divisors of 509. With a calculator, we see
so 13 is not a divisor.
Next we try 17, 509 = 29. 94 is not an integer, so 17 is not a divisor.
Next we try 19, 509 = 26.78 is not an integer, so 19 is not a divisor.
Lastly we try 23, 509 = 22.13 is not an integer, so 23 is not a divisor.
Therefore 506 is prime as all primes with square < 509 do not divide into it a whole number of times. Solution: the prime decomposition of 4581 is given by 9 x 509 and 9 x 509 = 4581 for reasons shown above. Problem C: Find the prime decomposition of 11830 Solution: Before listing all primes p with p2 < 4581, let us get smaller numbers. Observe 11830 = 1183 x 10 The 10 gives two prime factors 2 and 5. Now the square root of 1183 is 34.39 < 35. The list of primes < 35 is
Divisibility rules allow us to eliminate 2 and 5 immediately - they are not divisors of 1183.
Now modulo 3, 1183 = 1 + 1 + 8 + 0 = 10 = 1. So the remainder on division by 3 is 1 and 3 is not a divisor. Eliminate 3.
Now
according to my calculator. To avoid be misled by a possible rounding to 169, I clear the display and enter 169 into the calculator and multiply by 7. The result is 7 x 169 = 1183 exactly. So 7 is a factor. We now try to factor 169.
Here 7 might be a factor again. But
Eliminate 7 from the list of possible prime divisors of 169.
Note 1183 = 7 x 169. So the primes 2, 3 and 5 remain cross-out or eliminated as we know 2, 3 and 5 are not divisors of 1183 and hence cannot be divisors of 169 as if they were, they would be divisors of 1183 as well. So now we try 13. From a calculator or memory of the square of 13 169 = 13 a prime Therefore 169 = 13 x 13 So 1183 = 7 x 169 = 7 x 132 and hence
The latter product provides the prime decomposition of 11830
|
Number TheoryA. Start of Number Theory B. Number Theory Related Site Folders
|
|