1.2Trial Division

To test whether $n$ is prime you do not have to try every number below it. Test only the primes up to $\sqrt{n}$ . If $n = a \times b$ then one of $a$ and $b$ is at most $\sqrt{n}$ , so if nothing that small divides $n$ , nothing larger will either.

Work out $\sqrt{n}$ .
Divide $n$ by each prime up to $\sqrt{n}$ : $2, 3, 5, 7, 11, \ldots$
One divides exactly, so $n$ is composite. None does, so $n$ is prime.

Testing large numbers for primality

For each number below, state whether it is prime or composite, and give your reasoning: (a) 861 (b) 509

Show solution▾

(a) Digit sum of

861

8 + 6 + 1 = 15

, divisible by

3

\therefore 861

is composite (

861 = 3 \times 287

(b)

\sqrt{509} = 22.6

(to 1 d.p.), so test all primes

\leq 22

2, 3, 5, 7, 11, 13, 17, 19

509

is odd (not div. by 2), digit sum

= 14

(not div. by 3), does not end in 0 or 5, and

509 \div 7 = 72.7\ldots

509 \div 11 = 46.2\ldots

509 \div 13 = 39.1\ldots

509 \div 17 = 29.9\ldots

509 \div 19 = 26.7\ldots

\therefore 509

is prime.

Now you try

To be sure $787$ is prime, what is the largest prime you would need to divide by?

Show solution▾

\sqrt{787} = 28.05\quad \scriptsize\text{(to 2 d.p.)}

787 = a \times b

then one of

a

and

b

is at most

\sqrt{787}

, so nothing above 28 can divide

787

unless something at or below it already does.

Primes up to 28:

2, 3, 5, 7, 11, 13, 17, 19, 23

\therefore

the largest prime you need to divide by is 23.

Want it marked, with hints, and a new question each time? Practise this →

Predict

Is $91$ prime? It is odd, its digits add to $10$ , and it does not end in $0$ or $5$ , so it passes the tests for $2$ , $3$ and $5$ .

Show the answer▾

\sqrt{91} = 9.5

(to 1 d.p.), so

7

is still on the list of primes to test.

91 = 7 \times 13

, so

91

is composite.

Stopping at

2

3

and

5

is the usual reason a composite number gets called prime.

Divisible by	Test
$2$	the last digit is even
$3$	the digits add to a multiple of $3$
$5$	it ends in $0$ or $5$
$11$	the alternating digit sum is a multiple of $11$