2
$\begingroup$

Let $n$ be a positive natural number. You know the following facts about $n$ . Firstly, $n<10^{6}$ . Moreover, not a single integer $k$ between $1$ and $10^{4}$ divides $n$ . Does it follows that $n$ is prime. Explain your answer.

My attempt is: Suppose $n$ is not a prime, that is $n$ is a composite. This means that $k$ divides $n$ such that $k>10^{4}$ . Now $\frac{n}{k}$ also divides $n$ but is smaller than $10^{4}$ . This means that if $n$ is prime then $10^{4}<n<10^{6}$ and it would only be divisible by itself. .

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

You assumed $n$ being composite and reached a contradiction, namely $\frac{n}{k}<10^2$ dividing $n$. Hence, by the principle of proof by contradiction, $n$ is indeed prime.

$\endgroup$
2
  • $\begingroup$ so that means my answer correct? $\endgroup$
    – Curious_guy1111
    Commented Apr 18, 2015 at 10:03
  • 1
    $\begingroup$ @ZainalShariff Yes, it is! $\endgroup$
    – Christoph
    Commented Apr 18, 2015 at 10:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .