Determine if $n$ is prime?

Question

If $n < 10^6$ and no integer between $1$ and $10^4$ divides $n$. Is n prime?

Here is my attempt: Assume $n$ is prime. Then using trial division, $n$ must be divisible by an integer between $1$ and the square root of $10^6$ (which is $1000$). Thus, its a contradiction because $n$ is not divisible any integer between $1$ and $10^4$ (which is $10,000$). Then n is not prime.

You need to show that if $n$ is not divisible by any $a$ with $1\lt a\lt 10000$, then $n$ is prime. — André Nicolas, Apr 12 '15 at 22:39
I think you want to assume n is NOT prime, otherwise everything seems fine. — SE318, Apr 12 '15 at 22:42
you mean like n/a, such that a <10,000. ? that contradicts the question.Im sorry, can you explain to me how to prove this? — Peter, Apr 12 '15 at 22:44
@Peter You should start with “assume $n$ is not prime”: if you assume $n$ is prime, you know that it's not divisible by any number between $1$ and $n$, don't you? The conclusion should be that $n$ is prime. — egreg, Apr 12 '15 at 22:55
If a number $n<10^6$ is not divisible by any prime below $1\ 000$, it is already prime. — Peter, Apr 12 '15 at 22:58

score 2 · Accepted Answer · answered Apr 12 '15 at 22:59

2

You're switching “is prime” with “is not prime”.

Suppose $n$ is not prime. Then $n$ is divisible by a number $k$ with $1<k<\sqrt{n}<10^3$.

But $n$ is not divisible by any number $k$ with $1<k<10^4$. So the assumption $n$ is not prime leads to a contradiction.

Hence $n$ is prime.

Without prior knowledge that a non prime is divisible by a number less than its square root, you can argue as follows.

If $n$ is not prime, then $n=ab$, with $a>1$ and $b>1$. Then $a$ and $b$ are divisors of $n$, so $a\ge10^4$ and $b\ge10^4$, giving $n=ab\ge10^8$: a contradiction.

answered Apr 12 '15 at 22:59

egreg

238,574

1

The latter method immediately yields a proof of the prior-used Lemma, so one could argue that it does involve such knowledge. – Bill Dubuque Apr 12 '15 at 23:47
@BillDubuque The OP seems aware of the prior-used lemma. – egreg Apr 13 '15 at 06:31

score 0 · Answer 2 · answered Apr 12 '15 at 22:54

Yes. This is rather fundamental, but in general, you only need to test integers less than or equal to the square root of your integer to know if it is prime or not. This is fairly easy to prove, and you can do this by assuming that $n$ is composite and that there exist two unique divisors greater than $\sqrt{n}$. Upon multiplying these two integers, we find that $n>n$, which is a contradiction.

Determine if $n$ is prime?

2 Answers2