The following is a proof of the statement ‘If \(n\) is not
divisible by any primes that are \(\sqrt{n}\) or less, then \(n\) is
prime’ for all integers \(n\) greater than \(1\).
<Proof>
Let us assume the conclusion is false and \(n\) is not prime. Then
there are integers \(l\) and \(m\) greater than \(1\) such that
\(n=lm\). Let \(p\) be a prime factor of \(l\), and \(q\) be a prime
factor of \(m\). Then \(pq\) is a divisor of \(lm\), so \(pq\leq
n\). If \(p>\sqrt{n}\) and \(q>\sqrt{n}\), then
\(pq>\sqrt{n}\sqrt{n}=n\) which is a contradiction. Thus, it
should be that \(\fbox{\(\qquad\quad(\alpha)\quad\qquad\)}\).
This means there is a prime factor of \(n\) that is \(\sqrt{n}\) or
less. However, this contradicts the premise.
Thus \(n\) is prime.
In the proof above, what is appropriate for \((\alpha)\)?
[2 points]
- \(p\leq\sqrt{n}\) or \(q\leq\sqrt{n}\)
- \(p\leq\sqrt{n}\) and \(q\leq\sqrt{n}\)
- \(p\leq\sqrt{n}\) or \(q\geq\sqrt{n}\)
- \(p\leq\sqrt{n}\) and \(q\geq\sqrt{n}\)
- \(p\geq\sqrt{n}\) or \(q\geq\sqrt{n}\)