2

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.

klorzan
  • 787
  • Tell us what your thoughts are? How would you try to go about doing this? – Alekos Robotis Oct 26 '15 at 01:56
  • 1
    Try it with a few numbers (like 6 or 12 or 9 or 18) and list all there divisors. see what you notice that might relate to this. How'd you go about finding the divisors. – fleablood Oct 26 '15 at 02:05
  • 1
    I have edited my post including what I have done so far. – klorzan Oct 26 '15 at 02:10
  • 1
    If $n$ is not prime, then there exists integers $a$ and $b$, both bigger than $1$, such that $n = ab$. Now what can you say about $a$ or $b$? – Joey Zou Oct 26 '15 at 02:35
  • 1
    All right. BIG HINT. If a divides n that means there is some m such that n = am. If a divides n then m also divides n. Is it true that a and m are both bigger than the square root of n? – fleablood Oct 26 '15 at 03:13
  • Correct me if I am wrong, but a and m can not possibly be bigger than the square root of n, because $n=am$, so $\sqrt{n} = \sqrt{am}$ ? – klorzan Oct 26 '15 at 04:30
  • After much more thought, if $n=ab$ where $a$ and $b$ are integers greater than 1, then either $a$ or $b$ must be less than $\sqrt{n}$ because if they were both greater than $\sqrt{n}$, then $n<ab$. – klorzan Oct 26 '15 at 05:00

3 Answers3

1

I think I can prove this directly! Here is what I would do.

If $n$ is a square, obviously it suffices to choose $a = \sqrt{n}$. So suppose $n$ is not a square, and not prime. We do know that $n$ has a prime factorization, $n = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$ with $\alpha_i \geq 1$. If $k>1$ then without loss of generality let $p_1 = \text{min}\{p_1,p_2,\ldots, p_k\}$. We know $$p_1^2 < p_1p_k \leq p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k} = n $$ and hence $p_1 < \sqrt{n}$ (and obviously $p_1 \geq 2$). Else if $k = 1$ we must have $\alpha_1 = 2j+1$ where $j \geq 1$ (this follows from choosing $n$ not to be a square, and $n$ not being prime). We see quickly that $$p_1^2 < p_1^{\alpha_1} = n$$ and so $\space 2 \leq p_1<\sqrt{n}$ in either case. So a choice of $a$ as the smallest prime in $n$'s prime factorization will suffice.

Can you proceed as you've said and arrive at this result through contrapositive?

graydad
  • 14,077
1

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

Noah Schweber
  • 245,398
1

If $n$ is not prime, there exist 2 integers $a$ and $b$ (where $a$ and $b$ are both greater than $1$) and $n=ab$. Assume towards contradiction that both $a$ and $b$ are greater than $\sqrt{n}$. Thus, $ab>\sqrt{n}\sqrt{n}$. Then, $ab>n$, $ab \neq n$. So, if both $a$ and $b$ are greater than $\sqrt{n}$, then $a$ does not divide $n$.

Thus, either $a$ or $b$ is less than or equal to $\sqrt{n}$. Without loss of genrality, let $a$ be the integer that is less than or equal to $\sqrt{n}$.

$\therefore $ 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}$.

klorzan
  • 787