Number Theory: Prime Factorization Trial Division (Brute
In this series we are concerned with factorizing small numbers, less
than a million or so, but often much smaller.
It is useful for various reasons to know whether a number is prime.
A prime number, p, is a number greater than 1, with two factors only:
itself and one. If we fail to find any factors othere than these after
testing all possibilities directly or otherwise, then the number is
It is sometimes more useful to say that if a number has a factor other
than one and itself, then it isn't prime. Number Theory Contents
A simple way to check whether a number is prime or composite (has
factors other than 1 and itself) is to trial divide all possible
numbers. These numbers are integers.
Naturally, every factor is one of a pair. For instance,
3•7=21. So 3 divides 21, and it needs to be paired with
another number, 7. If 3 divides 21, then there is another factor, 7,
which also divides 21 and also produces 21 when it is multiplied by 3.
(There can be many such pairs of factors).
With each pair of factors, one factor is less than or equal to the
square root of the number. For instance, √21= ⌊4.58...⌋,
or floor(4.58...) so one factor is less than or equal to 4. If the
number is a perfect square and one factor is the root, then the factors
are equal to each other. This means we need to check numbers less than
or equal to the floor of the square root of the number.
Proof: In any pair of factors, the smallest factor is less than or equal to the square root of the number
Numbers n, a and b are positive integers. Suppose that n can be factored as a•b, where a≤b. So a•b=n Let r=√n, where r is the positive root of n. Let a>r. As a>r, let a=r+x, where x is a positive number. b>r, because b>a (by assumption) and a>r. Let b=r+y, where y>x, because b≥a=r+x (and y is therefore positive) So a•b=(r+x)(r+y)= r2+r(x+y)+xy=n (because a•b=n) As r2=n, then n+r(x+y)+xy=n So r(x+y)+xy=0 That is the positive numbers combine to produce zero, which is impossible.
Therefore a≤r The
equation: r(x+y)+xy=0, has a solution when x=0 and y=0, when the number
n is a perfect square and the factors are equal to r.
So, in any pair of factors, one factor is less than or equal to the square root of the number (product of the factors). ■
seeking factors in 1631 we need only try numbers up to 40 (because
40.38... is the square root). Of these, 20 are even numbers, and one
number is unity, leaving 19 possible numbers to check: 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39
We can progressively eliminate the numbers which have prime factors: 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39
This leaves us with 11 numbers to check.
As it happens, we find
a factor, 7, quite quickly, because it is early in the list. We can
find another factor by division: 7•233=1631
In seeking factors of 253, we find that 11 is one
factor, and 23 is the other one. Because ∛253=6.32...<11, then we
know that 23 is prime.
If we found that one factor of 67159 is
239, and another factor is 281, found by division, then because
239>∛67159=40.6... we do not have to seek factors of 281, because it
Proof: If the least factor of a pair is greater than the cube root of the number, then the greater factor is prime.
Suppose n=r3, where n is a positive integer and r is the cube root. Also suppose n=a•b, where a and b are positive integers. Suppose that a
is the smallest positive integer which is a factor of n. For instance,
we might have found a by trying all the positive integers up to a. Also a<b and suppose a>r
If b has factors, say c and d which are positive integers, then: n=a•c•d
Because a is the smallest factor of n, and a>r, then because a<c and a<d, then a, c and d are each greater than r.
That is, the product of the factors a, c, d exceeds n, which is impossible.