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

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?

-
To clarify, in (1) you want to know where $\sqrt{n}$ comes from, and in (2), you want the intuition for $p \mid a \text{ and } a \mid n \implies p \mid n$? –  Anant May 6 '14 at 16:54
@Anant hello! thanks. (1) i want to know how to prefigure that I need to prove $\color{magenta}{a \le \sqrt n}.$ (2) No, intuition for the $\iff$ result in the title of this question. –  Dwayne E. Pouiller May 6 '14 at 19:16
(1) For composite $n = ab$, we have $a \le b \iff a \le \frac{n}{a} \iff a^2 \le n \iff a \le \sqrt{n}$ –  Anant May 6 '14 at 20:11
Why do you keep making new accounts? –  Potato May 7 '14 at 17:53
end of the first paragraph "Backward direction also postulates $p\mid n$, thence the required $d=p$." Do you mean $d=\frac{n}{p}$? –  snulty May 7 '14 at 18:10

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

-
Thanks. Upvote. I don't understand what you mean by 'Well ...'? Furthermore, can you please work out how you can prefigure $\color{red}{a > \sqrt{n}}$ (2)? It is still uncanny to me. Where does it hail from? –  Dwayne E. Pouiller Jan 6 '14 at 5:32

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

-
Thanks. Upvote. I now understand you need it to work out a contradition but can you please work out how you can prefigure $\color{red}{a > \sqrt{n}}$ (2)? It is still uncanny to me. Where does it hail from? –  Dwayne E. Pouiller Jan 6 '14 at 5:33

I would say that the intuition is that a composite number, $n$ can be written as a product of two factors both strictly less than $n$, say $n=a\cdot b$. If both of these factors were greater than $\sqrt n$, then their product ($a\cdot b$) would be greater than $n$.

It is similar to the idea that for any two numbers, $x$, $y$, at least one must be less than or equal to the average of the two numbers.

-

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.

-

Consider if $n$ was composite and $p$ prime, s.t. $p \mid n$ and $p\geq\sqrt n$. Then $p<n$ ($n$ is composite) implies there exists $a \in \mathbb{N}$ s.t. $pa=n$, $a> 1$ and $a \leq \sqrt{n}$ (by the same argument everyone else posted). By fundamental theorem of arithmetic, $a$ can be written as a product of primes so there exists $q$ prime s.t. $q \mid a$ and hence $q \mid n$, with $q \leq a \leq \sqrt n$. So we can simply replace our prime $p$ with a prime $q$ less than or equal to $\sqrt n$, as you require.

Hopefully that gives some feel why you can consider a prime divisor less than root $n$.

-