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}