Prime Decomposition of Whole Numbers
This lesson focuses on obtaining prime factors and prime
decomposition of whole numbers. Prime decompositions are called prime
factorizations as well.
Recognition of prime factors and the prime decomposition of
whole numbers aid calculations of LCM, GCD and LCD in arithmetic with whole
numbers and fractions. They also lead to cosmetic simplification of square
roots. The recognition of common factors in numerators and denominators of
fractions alone or in products helps with the reduction of fractions and via
cancellation leads to efficient methods for multiplying fractions.
The question of whether or not, a whole number is prime may be related to its
decimal representation.
A whole number is not prime if is a proper multiple of 2, 3, 5, 7 or 11, or
equivalently if it remainder, modulo these small primes is zero. The multiple
one of each of these primes is considered improper. The decimal-based rules for
recognizing multiples of these primes (or calculating remainders) can be used to
recognize prime factors.
The numbers 2, 3, 5, 7 or 11 are the smallest primes. A theorem of Euler
shows there the number of primes is unlimited. Given any finite sequence
of prime numbers, their product plus one is a prime or is a multiple of a prime
not in the sequence.
Squaring the five primes 2, 3, 5, 7 or 11 squared give the sequence 4, 9, 25,
49 and 121 of whole numbers.
Theorem: If N = AB is product of two whole numbers A and B
where A > B > 1 then A2 > N and
N2 > B.
Proof: N = AB < AA = A2 .Therefore A2
> N. Similarly N = AB > BB = B2 .Therefore
B2 < N.
The above theorem implies if N is a product of two whole numbers, both
greater than one, than the smallest squared will be less than or equal to
N and the largest squared will be greater than or equal to N. Now the smallest
factor is a prime or it a multiple of a prime. In either case there is prime
whose square is less than or equal to the smallest factor squared and hence less
than or equal to the original number N.
Theorem: If N = AB is product of two whole numbers A and B where
A > B > 1 then N has a prime factor p with square p2
< N.
Contrapositive Consequence: If N has is not a proper multiple of all
primes p with square p2 < N then N cannot be decomposed in
to a product of two smaller whole numbers, and hence N is prime.
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.
The Contrapositive consequence implies the following.
If N < 169 = 132 is not divisible by any of the primes 2, 3,
5, 7 or 11 then N is a prime number.
Proof: If N < 169 is divisible by a prime less
than itself, then there is a prime p with square p2 < N
< 169 which divides into p. So p has to be one of the first five
primes 2, 3, 5, 7 or 11 as all further primes have square > 169 >
N
So to check if a whole number N < 169 is a prime, is enough to compute the
remainders for N when N is divided by 2, 3, 5, 7 or 11. The latter can be done
with the help of divisibility rules for recognizing multiples of these primes,
with the help of the 10 or 12 times table, or with the aid of a
calculator.
Calculator Rounding Hazard: If some prime
p, N/p = q for a whole number q according to your calculator, due to the
possibility of rounding, you need to compare pq and N. Most calculators can
compute a product of whole numbers exactly. So if the product pq is not
equal to N, you know that some rounding error led you to think p was a divisor
and N was the exact multiple q of p.
Rule of Thumb
In learning and applying algebra exactly, one only needs to
compute with fractions or ratios of whole numbers less than 100 or so. So the
efficient ability to find recognize prime factors of whole numbers less than 169
(or 100) appears sufficient for most purposes in high school and college
mathematics and science courses.
Curiosity
Theorem: If N = AB is product of two whole numbers A and B
where A > B > 1 then N has a prime factor p <
N with square p2 < N.
Contrapositive Consequence: If N has is not a proper multiple of
all primes p with square p2 > N then N cannot be
decomposed in to a product of two smaller whole numbers, and hence N is
prime.
The "density" of primes relative to the set of whole numbers
gets smaller as the primes increase. So if you are searching for
primes factors of a large number N with the aid of a calculator or
computer program, checking for divisibility of N starting with the largest
primes p satisfying p < N with square p2 >
N might involve less work (fewer divisions) than starting with the
smallest primes p with square p2 < N. |
|