Mathematics and Logic - Skill and Concept Development

Prime Factorization and a square rule

This lesson focuses on obtaining prime factors and prime decomposition of whole numbers. Prime decompositions are also known as prime factorizations.

The the first primes 2, 3, 5, 7 or 11 are the smallest primes. A theorem of Euclid (300 B.C.) shows there the number of primes is unlimited. Given any finite sequence of prime numbers, their product plus one is not a multiplie of any in the sequence. So it is prime or has another prime as a factor. The latter observation implies one plus the product of the first m primes has a prime factor, the m+1st or later prime. So the list of prime numbers is un-ending - in other words is not finite or infinite.

Theorem A. 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. Whence the next theorem holds.

Theorem B. If N is composite then N has a prime factor p with square p² < N.

A Square Rule Method for Identifying Primes

When an implication rule (i) If A then B holds, the contrapositive of that rule, that is, (ii) if NOT B then NOT A, must also hold. Anything else would contradict or be inconsistent with the original rule (i). See the logic chapters in site Volumes 1A or 2 to learn more.

Theorem C - Contrapositive of Theorem B. If N has is not divisible by each primes p with square p² < N then N is prime. 

Theorem C provides the first part of square rule or method for recognizing prime and composite numbers

The the first six primes 2, 3, 5, 7 or 11 and 13 have squares 4, 9, 25, 49, 121 and 169. That should be by your lnowledge of the times table or decimal multiplication implies this.

Theorem C has the following consequence:

If N < 169 = 13² is not divisible by any of the primes 2, 3, 5, 7 or 11 then N is a prime number. 

To check if a whole number N < 169 is a prime, is enough to check for divisibility 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.

A Square Rule Method for Prime Factorization

Theorem: If a whole number N is composite then N has a prime factor p < then the whole number N has a prime factor p with square p² < N.

Contrapositive: If a whole number N is not divisible by each primes p with square p² > then N is prime.

In the prime decomposition of a whole number N with the check for divisibility of N with the smallest primes first. That will require less arithmetic work - fewer divisions - than starting with larger primes.

A rule of thumb, the probability that a given whole number N is divisible by prime p is greater than the probability that N is divisible by another prime q when p < q. Exercise - explain why.

In the prime decomposition of a whole number N, if you find q is the smallest prime among those with square $\le$ N that divides the whole number N, then $N = q \times M$ where M is a whole number with the property all primes less than q do not divide M. But q will divide M if $q^2$ divides N. Otherwise, q will not divide M. Moreover the set of primes $p \ge q$ that have have square $\le$ M are a subset of the set primes $p \ge q$ with with square $\le$ N. That implies fewer primes have to be checked in the prime factorization of M. The prime factorization of N will be given by q times the prime factorization of M.

Remark: The square rule itself is well-known. The site innovation consist of providing a name for it and emphasizing it as a tool to make master of primes and prime factorization easier to learn and teach.

Exercise: Identify all multiples of 7 less than 121 that are not also multiples of smaller primes 2, 3 and 5.  The first three are indicated above.

www.whyslopes.com >> Arithmetic and Number Theory Skills >> 3 Prime Factorization Skills >> 5 Prime Factorization and a Square Rule Next: [6 Sieve-of-Eratosthenes and Square Rule.] Previous: [4 video Prime Factorization Introduction.]   [1] [2 swf] [3] [4 swf] [5 swf] [6][7] [8] [9 swf] [10 swf] [11 swf] [12] [13] [14 swf] [15 swf] [16 swf] [17 swf] [18] [19 swf] [20 swf] [21]

Return to Page Top