Section 5.2 Factoring Integers
There are two very important questions that arise when dealing with prime numbers and factorizations.
How do we determine whether a given integer \(n\) is prime?
How do we find the prime factorization of a given integer \(n?\)
The following theorem is a good starting point.
Theorem 5.2.1.
A number \(n \in\mathbb{N}\) is composite if and only if it is divisible by some prime \(p \leq \sqrt{n}.\)
Proof.
If \(n\) is divisible by some prime \(p\leq \sqrt{n},\) then it follows that \(n\) is composite. Conversely, if \(n\in\mathbb{N}\) is composite, then \(n = ab\) where \(1\lt a\lt n;\) at least one of \(a\) and \(b\) is less than or equal to \(\sqrt{n}\) (if not, \(ab\gt n\)), and this factor will be divisible by a prime \(p\leq\sqrt{n},\) which then divides \(n.\)
If we want to factor an integer \(n,\) the above theorem says all that we have to do is divide it by every prime less than \(\sqrt{n},\) and if one of the primes divides evenly (with remainder \(0\)), then the number is composite, and we have a factorization.