[Math] Prove or disprove: If $n$ is not prime, then there exists an integer $a$ which divides $n$ and is in the interval $2\leq a \leq \sqrt{n}$.

prime numbers

If $n$ is not prime, then there exists an integer $a$ which divides $n$ and is in the interval $2\leq a \leq \sqrt{n}$.

I need to either prove or disprove this.

My approach would to first attempt to test values for $a$ and $n$ to see if it seems true.

I have tried $a = 4$ and $n = 16$. This statement holds for these $n$ = 16. I then tried $n = 36$, and found an integer $a$ to be $4$. This statement so far seems true.

Next, I will try to prove this by proving the statement's contrapositive, because it seems easier to do that than proving the original statement.

This is where I am running into trouble.

Best Answer

Suppose $n$ is not prime. Then $n$ has a nontrivial factor, $c$. There are two possibilities:

  • $2\le c\le\sqrt{n}$. Yay! We're done!

  • $\sqrt{n}<c$. Uh oh, that's not good. But: can you think of another factor of $n$, related to $c$, which we know is "small" precisely because we know $c$ is "big"?

EDIT: You might find the following problem easier to think about, although the math is really the same:

Suppose $n$ can be written as the sum of two primes. Show that, for some prime $a$ with $a\le {n\over 2}$, $n-a$ is prime.

(The "prime" here is basically irrelevant - it's just added to make this not completely trivial.)

Related Question