Ken Ward's Mathematics Pages

Number Theory: Prime Factorization Trial Division (Brute Force)

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 prime.

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

Page Contents

1. Trial Division
2. Proof: In any pair of factors, the smallest factor is less than or equal to the square root of the number
3. Proof: If the least factor of a pair is greater than the cube root of the number, then the greater factor is prime.

Trial Division

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)=
r²+r(x+y)+xy=n (because a•b=n)
As r²=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).
■

Example 1

In 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

Example 2

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 is prime.

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=r³, 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.

So:
a•c•d>r³=n,

That is, the product of the factors a, c, d exceeds n, which is impossible.

b is therefore prime.
■















Ken Ward's Mathematics Pages

---

---

Faster Arithmetic - by Ken Ward