3
$\begingroup$

On my exam recently, we had the following question:

Use the prime number theorem to estimate the number of primes less than $\sqrt{10301}$, and hence, give a concise argument whether 10301 is prime or not.

I answered as best I could, using the estimate $\frac{\sqrt{10301}}{\ln{\sqrt{10301}}}$, which is about 22. I think there are about 25 primes but whatever. As for the next part of the question, how could I "concisely" argue that 10301 is prime? I know that $n$ prime $\Rightarrow \sqrt{n}$ is irrational, but obviously the converse is not necessarily true. I threw it down anyways. Short of saying "the only two factors of 10301 are 1 and 10301", but that's not an argument. How does $\sqrt{10301}$ come into play here? Thanks in advance for help.

$\endgroup$
  • $\begingroup$ Basically, You want a prediction Algorithm $\endgroup$ – user171358 Oct 19 '14 at 9:38
  • $\begingroup$ I'm not quite sure what you mean by that. Could you explain? $\endgroup$ – Sultan of Swing Oct 19 '14 at 9:40
3
$\begingroup$

By definition, any factor $p$ of a natural number $N$ has a complement, that is, a natural number $q$ such that $N = pq$. Now, one of $p, q$ must be $\leq \sqrt{N}$ (if not, we would have $N = pq > \sqrt{N} \cdot \sqrt{N} = N$, a contradiction), so to check whether $N$ prime, it is enough to show that it has no factors $\leq \sqrt{N}$. Any factor itself has a prime factor, so in fact it suffices to check whether $N$ has any factor among the primes $p \leq \sqrt{N}$.

So, the quantity $$\frac{\sqrt N}{\ln \sqrt N} \sim \# \{p \text{ prime}: p \leq \sqrt N\}$$ you computed for $N = 10301$ is an estimate of how many primes you need to check to determine that $N$ is prime (which in this case it is). Whether checking $\sim 22$ (actually $26$) primes manually is "concise" is up for debate.

$\endgroup$
  • $\begingroup$ That is clever; I should have thought of this. So the argument uses the fact that every composite number $n$ has a factor (and thus a prime factor) $\leq \sqrt{n}$, right? If we methodically go through every prime, and find none, then we know no prime factors $\leq \sqrt{n} \Rightarrow n$ is prime. $\endgroup$ – Sultan of Swing Oct 19 '14 at 10:01
  • $\begingroup$ Yes, that's exactly it. $\endgroup$ – Travis Oct 19 '14 at 10:02
1
$\begingroup$

use that $101<\sqrt{10301}$ and $10301$ is a prime number

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.