# A calculus of the absurd

##### 19.1.3 How large are divisors?

Suppose that $$n = pq$$ for $$n, p, q$$ which are all integers. In this case, a question worth asking is how large can $$p, q$$ be. A little bit of thought reveals that $$p, q \leq n$$ (as otherwise neither could divide $$n$$).

So then the next question is that if both $$p$$ and $$q$$ are less than $$n$$, how large can they be. To solve this we need to consider the fact that $$n = pq$$. Here I would suggest writing down some numbers and their factors. If you’ve written down a few, it will hopefully become apparent that either $$p$$ or $$q$$ has to be less than $$\sqrt {n}$$.

• Theorem 19.1.2 Let $$n, p, q$$ be integers such that $$n = pq$$. If $$p, q \ne 1$$ and $$p, q \ne n$$, then one of $$p, q$$ is less than $$\sqrt {n}$$.

Proof: we can prove this statement by contradiction; suppose without loss of generality that $$p \geq \sqrt {n}$$. If $$q \geq p$$ then

\begin{align} n &= pq \\ &> \sqrt {n} q \\ &\geq \sqrt {n}\sqrt {n} \\ &= n \end{align}

and $$n > n$$ is absurd. If $$q < p$$ then

\begin{align} n &= pq \\ &> \sqrt {n} q \\ &= \end{align}