3

I have proved a basic theorem in prime numbers, If $n \ge 2$ and $n$ is composite, then it is divisible by some prime $p \le \sqrt n$. This is a fairly basic result, and then my textbook shows me how the 'Sieve' works etc. But I am interested to know, does

$ p | n $ where p > $\sqrt n$

provide a contradiction? The first theorem does not imply anything about the existence/ non existence of such a prime...

I would like to know, because when asked to determine whether 111 is prime, I would say that $\sqrt{111} < 11 <\sqrt{121} $ and argue that 111 is not divisible by any of the primes less than 11. But i am currently not convinced that there does exists $p > \sqrt n$ such that p | n.

2 Answers2

1

The theorem doesn't say anything about the primes larger than $\sqrt{n}$, but for the type of argument you want to make, you don't need.

So Step by step here is what you are doing:

  • Step 1: Check that $n$ is not divisible by any prime $p \leq \sqrt{n}$.

If it is, like for example if $3|111$, then $n$ is not prime, because you found a divisor. If it is not, go to step 2.

  • Step 2: Assume by contradiction $n$ is not prime. Then by the above theorem, $n$ is divisible by some $p \leq \sqrt{n}$. But this is not the case, as you have seen in case 1. This is a contradiction.
N. S.
  • 132,525
1

Yes it can happen that there is a prime greater than $\sqrt{n}$ that divides $n$. For an explicit example note that $11 \mid 33$ and $11 > \sqrt{33}$.

In fact, for any two distinct primes $p,q$ the number $pq$ will have a prime divisor larger than $\sqrt{pq}$, namely the larger of the two primes $p,q$.

The point is though that for your application this is not relevant as you know if it is composite then there exists a "small" prime divisor. So, if there is no "small" prime divisor it cannot be composite.

In our example, by the usual sieving you would in fact not find directly that $11 \mid 33$, but it does not matter as you would have found $3 \mid 33$ and this suffices to show that $33$ is composite.

More generally, there is an involution on the set of divisors of $n$, given by $d \mapsto n/d$, thus knowing all divisors of $n$ up to $\sqrt{n}$ is essentially as good as knowing all of them.

quid
  • 42,135