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

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

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.

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

As r

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

■

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

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.

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

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

b is therefore prime.

■

Ken Ward's Mathematics Pages

No script follows:

Ken's book is packed with examples and explanations that enable you to discover more than 150 techniques to speed up your arithmetic and increase your understanding of numbers. Paperback and Kindle: