0

$\forall n \in \mathbb N^+$, $n$ is composite $\;\rightarrow\; \exists p\in \mathbb N^+, p \textrm{ is prime and } p \leq \sqrt{n} \textrm{ and } p\; |\; n$.

So far this is what I have... Suppose this is false.

$p> \sqrt{n}$, $p|n$

Then, $p^2 > n, p|n,$ where $p|n$ is also $pa=n$

Then $p^2 > pa$

Demophilus
  • 3,982
  • 1
    Hint: If $p|n$ so does $n/p$. – Henrik supports the community Oct 28 '17 at 17:54
  • if $p|n$ is for example: 56=30, how does $n|p$ become 30?=5 –  Oct 28 '17 at 18:00
  • If $p = 5$ and $n=30$ and $p|n$ then $\frac np = \frac {30}5 = 6$ and $6|30$. Which isn't relevant as $5 < \sqrt{30}$. A better example is $7|35$. $7 > \sqrt{35}$. But if $7|35$ then $\frac {35}7 = 5$ also divides $35$ and $5 < \sqrt {35}$. Another example is $7|28$ so $\frac {28}7 = 4$ has $4|28$ and $4< \sqrt {28}$. But $4$ isn't prime. But so what? It must have a prime factor that is even smaller. i.e. $2$ – fleablood Oct 28 '17 at 18:13
  • That a dash, not a vertical line $\frac np$ not "$n|p$. So 5.6 = 30, becomes 5. 6 = 30 trivially. 5 and 6 can't both be larger than that the $\sqrt {30}$. If $5 > \sqrt{30}$ and $6 > \sqrt{30}$ we get $30=56 > \sqrt{30}\sqrt{30} = 30$. So at least one* factor is $\le \sqrt{30}$. – fleablood Oct 28 '17 at 18:19
  • thank you for responding, but could you explain what you're trying to show when there are two factors of a number, where one is greater and the other is less than sqrt of the number? What does that represent? For some reason, I don't see anything wrong with sqrt30 x sqrt30 = 30 –  Oct 28 '17 at 18:57
  • @fleablood Can you answer my question above when you have time? Thanks! –  Oct 28 '17 at 19:26
  • The question is "show that there is always a prime factor less than or equal to the square root of $n$". I have shown that factors come in pairs where one is always less than or equal to the square root of $n$ and the other is larger or equal to the square root of $n$.... So that's it! We are done! I have shown there is always a factor that is less than or equal to the square root of $n$. That is what we were asked to prove. ...Okay, we haven't proven it is prime. But if it isn't prime it will have a smaller prime factor. So there is a prime factor less or equal to $\sqrt{n}$. – fleablood Oct 28 '17 at 20:22
  • Who said there was anything wrong with $\sqrt{30} * \sqrt{30} = 30$. $\sqrt{30} \le \sqrt{30}$ so that is fine. (except $\sqrt{30}$ isn't an integer.) Suppose we have $jk = n$ and $j \le k$.. Then $j \le \sqrt{n} \le k$. Then if $p$ is prime and $p|j$ then $p \le \sqrt{n}$ and $p|n$ and ..... that's it.... that is EXACTLY* what we were asked to prove. – fleablood Oct 28 '17 at 20:26
  • Take a number.... $76$ .... take a factor ...okay .... $19$... Take the "compliment" or $\frac {76}{19} = 4$. One of them is $\le$ to $\sqrt{76}$. ... Okay... $4 \le 76$. ... is $4$ prime.... No it is not. ... okay, take a prime factor of $4$. $2$. So 1) $2$ is prime and 2) $2 \le \sqrt {76}$ and 3) $2|76$ and.... what more do you want. That satisfies EVERYTHING you were asked to prove. Do it with every number. It will always work. – fleablood Oct 28 '17 at 20:33
  • Try a flow chart. $n$ is composite. A) Take a non trivial factor $k$. Is $k\le \sqrt{n}$ if so let $m =k$ and go to step C. If not continue to step B. B) Let $m = \frac nk$. $m|n$ and as $k > \sqrt n$ we know $m =\frac nk < \frac n{\sqrt{n}} = \sqrt{n}$. C) we have $m|n$ and $m \le \sqrt{k}$. Is $m$ prime? If so let $p=m$ and go to step E. Otherwise go to step D. D) $m$ is not prime and $m\ne 1$, so $m$ has a prime factor $p$. $p < m\le \sqrt{n}$ and $p|m$ and $m|n$ so $p|n$. Go to step E. E) We are done. $p$ is prime, $p \le \sqrt{n}$ and $p|n$. – fleablood Oct 28 '17 at 20:47
  • I'm sorry if I have frustrated you. Math is not my strongest subject. But, your explanations really helped with my understanding for this question. I sincerely appreciate your help. Thank you @fleablood –  Oct 29 '17 at 00:54
  • If your question has been answered, you shouldn't edit out your question. Otherwise anyone who has the same question, won't be able to find the answer that is posted here. So I rolled back your edit for this reason. – Demophilus Oct 29 '17 at 17:35
  • @fleablood One more question... how can you know that when two factors are produced, one is larger than sqrt n and the other is less than sqrt n? –  Oct 29 '17 at 23:32
  • larger than OR EQUAL and the othe is less than OR EQUAL. Suppose $m|n$. Then one of three things will happen. $m < \sqrt{n}$. In that case $k = \frac nm > \frac n{\sqrt{n} }= \sqrt{n}$. Or $m = \sqrt{n}$. Then $k = \frac nm = \frac n{\sqrt n} = \sqrt{n}$. Or $m > \sqrt{n}$. Then $k = \frac nm < \frac n{\sqrt{n}} = \sqrt{n}$. So if $m*k = n$ then either $m \le \sqrt{n} \le k \le n$. or $k \le \sqrt{n} \le m \le n$. – fleablood Oct 30 '17 at 01:25
  • Also. If $mk = n$ and if $m > \sqrt{n}$ and $n> \sqrt{n}$ then $n = mk > \sqrt{n}*\sqrt{n} = n$ and that is impossible. So either $m \le \sqrt{n}$ or $k \le \sqrt{n}$ – fleablood Oct 30 '17 at 01:27

1 Answers1

0

Factors come in pairs. If $j|n$ then there is a $k$ so that $j*k = n$. And $k$.... is also a factor.

If one of the factors is $j \ge \sqrt{n}$ then $k = \frac nj \le \frac n{\sqrt{n}} = \sqrt{n}$.

So at least one of $j$ or $k$ is $\le \sqrt{n}$ (and the other is $\ge \sqrt{n}$).

So if we assume $j*k = n$ and $1 \ne k \le j \ne n$ we have $k \le \sqrt{n}$.

If $p$ is any prime factor of $k$ than $p \le \sqrt{n}$ and $p|n$.

That's it. We're done.

fleablood
  • 124,253