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.  

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 A² > N and N² > B.

Proof:  N = AB < AA = A² .Therefore A² > N. Similarly N = AB > BB = B² .Therefore B² < 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 p² < N.

Contrapositive Consequence: If N has is not a proper multiple of all primes p with square p² < 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 = 13² 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 p² < 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.

Number Theory

A. Start of Number Theory

Origins of Counting or Tallying
Adding Wholes
Multipling Wholes
Distributive Law  Preamble
Distributive Law for Wholes
Consequences
More Consequences
What is a Fraction
Compound Fractions

B. Number Theory
Continued

Decimal Place Value
Place Value Reinforcement
Addition Method
Comparison Method
Subtraction Methods
Multiplication Methods
Division Methods
Long Division Continued
Remainder Arithmetic I
Primes & Composites
Primes Factorization Theorem
Primes & Composites
Prime Factorization Examples
Counting  Whole No.  Factors
Prime Factorization Aids
Square Roots  & Primes
Fractions & Decimals
Fractions as Decimals
1 = 0.999 Recurring
Infinite Decimals Expansion Arithmetic
Ratio of Simple Fractions
Ratio of Decimal Fractions
Unsigned Reals Numbers
Signed Coordinates
Plane Vectors
Horizontal Vectors
Adding Vector Multiplies
Adding Signed Numbers
Multiplying Signed Numbers
Distributive Law for Reals
Real Numbers Axioms
Remainder Arithmetic II

Related Site Folders

Euclidean-Geometry/Complex No.s
Complex Numbers More 2

www.whyslopes.com   [ Back ] [ Up ] [ Next ] [Top of this Page]

Custom www Search

Road Safety Message  Do not walk on a road with your back to the traffic - rule of thumb Please report by email,  errors in mathematics or grammar or terminology to site author If an arithmetic topic you need is not covered in site pages,  report that as well. Topics in most demand will be covered first in site growth.

All trademarks and copyrights on this page are owned by their respective owners.
Copyright to comments & contributions are owned by the Poster. 
The Rest © 1995 onward by site author,   Alan Selby (email form) All Rights Reserved.