Is n a prime if $n\in\mathbb{N}$, $n<10^{6}$ and $1

Question

Can I get hints on how I can explain this?

Question 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.

What happens if $n $ is not prime? It will have a divisor $k $ greater than $10^4$. Now $n/k $ also divides $n $, but is smaller than $10^4$. — Uncountable, Apr 18 '15 at 01:41

score 4 · Answer 1 · answered Apr 18 '15 at 01:39

4

The smallest divisor of $n$ is at most $\sqrt{n}$. In your case, if $n$ has a non-trivial divisor, then it has a non-trivial divisor of at most $10^{3}=\sqrt{10^{6}}$.

answered Apr 18 '15 at 01:39

TravisJ

7,426

I'll leave it to you to explain why the smallest non-trivial divisor is at most $\sqrt{n}$. – TravisJ Apr 18 '15 at 01:42

Is n a prime if $n\in\mathbb{N}$, $n<10^{6}$ and $1

1 Answers1