Test the following numbers for compositeness. If they are composite, write down their prime decomposition:
(a) 161
(b) 203
(c) 1003
(d) 1009
We use Corollary (2.10).
If $n > 1$ is composite then it has a prime divisor $p$ such that $p ≤ ⌊√n⌋$.
(a) $\lfloor \sqrt(161) \rfloor = 12$, so we only need to test prime factors less than or equal to 12, that is $2,3,5,7,11$. This gives us
$ 161 = 7 \times 23$
(b) $\lfloor \sqrt(203) \rfloor = 14$, so we only need to test prime factors less than or equal to 14. This gives us
$ 203 = 7 \times 29 $
(c) $\lfloor \sqrt(1003) \rfloor = 31$, so we only need to test prime factors less than or equal to 31. This gives us
$ 1003 = 17 \times 59 $
(c) $\lfloor \sqrt(1009) \rfloor = 31$, so we only need to test prime factors less than or equal to 31.
There are no factors, and so 1009 is prime.