Proof That Every Number is Diviisible by a Prime Number Less That or Equal to it's Square Root
Each composite integer
\[n \gt 2\]
is divisible by a prime number \[q \le \sqrt{n}\]
.Proof
\[n\]
is composite, so \[n=ab\]
where \[a, \; b\]
are integers with \[2 \le a \le b\]
. \[a\]
cannot be greater than \[\sqrt{n}\]
since then \[b \lt \sqrt{n}\]
contradicting that \[a \le b\]
, so \[a \le \sqrt{n}\]
. Now use this theorem, which guarantees the existence of a prime \[p\]
dividing \[a\]
, and therefore \[n\]
.\[p \le a \le \sqrt{n}\]
so we can take \[p\]
as the required prime.This theorem is useful when finding divisors of a number
\[n\]
. We need only consider numbers and primes less than or equal to \[\sqrt{n}\]
as divisors/ 
