Intuition — An integer $n > 1$ is composite $\iff \color{purple}{p \le \sqrt{n}}$ divides it.

Question

Origin — Elementary Number Theory — Jones — p32 — Lemma 2.14

Backward direction — I need to prove there exists a divisor $d$ of $n$ satisfying $1<d<n$. Because $p$ is prime, $1 < p$. Backward direction postulates $\color{purple}{p \le \sqrt{n}}$. $\sqrt{n} < n$ for every $n > 1$. All in all, $1 < \color{purple}{p \le \sqrt{n}} < n$. Backward direction also postulates $p|n$, thence the required $d = p$.

Forward direction — Let $n \ge 0$ be composite. This is defined as $n = a b$ where $a, b \in \mathbb Z$ and $1 < a, b < n$. Suppose [[Definition:WLOG|WLOG]] that $\color{green}{a \le b}$. I prove $ \color{magenta}{a \le \sqrt n}.$

(1) Where does $ a \le \sqrt n$ hail from — it feels uncanny? How can you anticipate this?

To instigate a contradiction, purport that $\color{brown}{a > \sqrt n}$. Then $\color{green}{b \ge a} \color{brown}{> \sqrt n} $.
$ \implies \color{green}{b} \qquad \color{brown}{> \sqrt n} $. Multiply by $a$ $\implies a \color{green}{b} \color{brown}{> \color{black}a \sqrt n.}$ Use $\color{brown}{a > \sqrt n} \implies \color{brown}{> \sqrt n\sqrt n }$, contradiction.

I defined $ 1< a $, thence by the Fundamental Theorem of Arithmetic, some prime $p$ divides $a \; (♯)$.
By reason of Jones - p4 - Exercise 1.3(d), $p \le a$ and so $p \color{magenta}{\le \sqrt n}$
From $(♯)$, $p|a$. By definition of $n = ab$, $a|n$. Thence by reason of Jones - p4 - Exercise 1.3(a) (scilicet Divides is Partial Ordering on Positive Integers), $p|a \, and \, a|n \implies p \mathop \backslash n$.

(2) What's the intuition?

Answer 1

I'll just prove the statement all over again, with some additional comments.
Suppose there is a prime $1<p\leq \sqrt n$ that divides $n$. Then, $n$ is composite, since it has a non-trivial divisor.

If $n$ is composite, there are two integers $1<a,b<n$. We may assume wlog that $a\leq b$, because until now, there is no distinction between them. Now suppose (thus, this is a proof using contradiction) that $a> \sqrt n$. Then, we have $b\geq a> \sqrt n$. $$ n=ab\geq a\cdot a=a^2>(\sqrt n)^2=n $$ Thus, we get $n>n$. This is a contradiction. Thus, the assumption that $a>\sqrt n$ must have been wrong. Thus, we now know that $1<a\leq \sqrt n$. Now, we have a number $a>1$, thus there is a prime $1<p\leq a$ such that $p|a$. Because $a|n$, we now have $p|a|n$, and $p|n$. (This is the partially ordering argument I think.) Because $p\leq a\leq \sqrt n$, we now know for sure that there is a prime $1<p<\sqrt n$ s.t. $p|n$, which was all that remained to be proven.

The intuition behind this is fairly simple I think, but in my case, my intuition is just this proof, so I think that understanding it will give you it.

Answer 2

(1) Assume there exists a prime $p$ with $p\mid n$ and $p\le\sqrt n$. Write $n=pd$. Then $p>1$ because $2$ is the smallest prime. Also $d=\frac np=\sqrt n\cdot\frac{\sqrt n}p\ge \sqrt n\ge p>1$. Thus $n=pd$ wshows that $n$ is composite.

(2) Instead of "let" it should rather "assume". The assumption $a\ge n$ is lead to a contradiction thus showing the intended goal $a\le \sqrt n$.

(3) $p\mid a$ and $a\mid N$ means that there are integers $d,e$ such that $pd=a$ and $ae=n$. Then $p(de)=n$. As $de$ is an iunteger, this shows $p\mid n$.

(4) Well ...

Answer 3

(1) The point of this is to show that $n$ is composite by showing the existence of a divisor $d$ of $n$ satisfying $1 < d < n$, namely $d = p$. Because $p$ is prime, $1 < p$. Backward direction postulates $p \leq \sqrt{n}$ by assumption. $\sqrt{n} < n$ for every $n > 1$.

(2) The proof assumes that $a > \sqrt{n}$ in order to obtain a contradiction, showing that in fact $a \leq \sqrt{n}$. "Let $a > \sqrt{n}$ could have been better phrased as "Assume that $a > \sqrt{n}$.

(3) The relation "divides" ($|$) is a partial order relation. The only fact that is relevant here is that, by definition of a partial order, this entails that if $x | y$ and $y | z$, then $x | z$. If you are familiar with that fact, then that is all you need. Here it is used to say that since $p | a$ and $a | n$, we have $p | n$.

(4) What follows is not so much "intuition" different from the text, but a paraphrase of what has been proved. Split any composite number $n$ into two factors $a$ and $b$, where $a$ is the smaller one. $a$ has some prime divisor $p$, which must also divide $n$.

For example, if you want to check whether 473 is prime, instead of testing all possible divisors that 473 could have, it's enough to see whether 473 has any prime divisors that are $\leq \sqrt{473}$. If 473 doesn't have any such divisors, then it is prime.