1.2 Trial 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

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

Try it

A practice question on this appears here. Practise primes hcf lcm.

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

$\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.

Practise this

Questions on Primes, HCF and LCM, marked as you go, with the working shown.

Practise Primes, HCF and LCM

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$