\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

QUESTION

\begin{description}

\item[(i)]
Prove that a positive integer $n$ is composite if and only if it
is divisible by some prime $p$ such that $p\leq\sqrt{n}$.

\item[(ii)]
Design a test for deciding when $n$ is the product of at most two
primes, including the possibility that $n=p^2$ for some prime $p$.

\item[(iii)]
Use your test from (ii) to find all the integers $n$ in the range
$600\leq n\leq620$ which are either prime or the product of two
(not necessarily distinct) primes.

\item[(iv)]
Use (i) together with your result in (iii) to fine all the primes
$p$ in the range $600\leq p\leq 620$.

\end{description}



ANSWER

\begin{description}

\item[(i)]
If $n$ is composite then $n=p_1p_2\ldots p_s$ where the $p_i$ are
(not necessarily distinct) primes. If $p_1$ is the smallest $p_i$
then $p_1^2\leq p_1p_2\leq n$ so that $p_1\leq\sqrt{n}$.
Conversely, a prime divisor in the range $2\leq p\leq \sqrt{n}$
must be a proper divisor.

\item[(ii)]
If $n$ is composite then $n=p_1p_2\ldots p_s$ where the $p_i$ are
(not necessarily distinct) primes and if $s\geq3$ we must have
$p_1^3\leq p_1p_2p_3\leq n$, where $p_1$ is the smallest $p_i$.
Therefore if one attempts unsuccessfully to divide $n$ by each of
the primes in the range $2\leq p\leq n^\frac{1}{3}$ then $n$ is
the product of at most two primes.

\item[(iii)]
Since $729=9^3$ we need only eliminate from the set $600\leq
n\leq620$ all multiple of 2,3,5 and 7. Deleting all multiple of
2,3,5 leaves

$$611,613,617,619$$

and none of these are divisible by 7 since $600\equiv5$ (modulo 7)
and none of 16,18,22,24 are divisible by 7.

\item[(iv)]
Since $25^2=625$ we need only test the divisibility of
611,613,617, 619 by the primes 11,13,17,19,23 (having already
dealt with 2,3,5 and 7). None are divisible by 11. However
$13\times47=611$ so that 613, 617, 619 are not divisible by 13.
None of 613,617,619 is divisible by 17,19 or 23. Therefore 613,617
and 619 are all prime.

\end{description}




\end{document}