why check all primes under the root of an interger?

Question

I am in high school and I need to factorize numbers. My teacher told me to check all numbers which are smaller than the root of the number I want to factorize. This seems to work just fine, but I do not know why it works and neither does my teacher.

Is there someone here who knows why this trick works?

Answer 1

First, you need only check the prime numbers less than $\sqrt n$, for the number $n$ that you are trying to factorize.

Why? If you find a composite number that goes into $n$, all of that composite number's prime factors will also go into $n$ (basically, if $p$ divides $a$ and $a$ divides $n$, then $p$ divides $n$).

---

Now as for why we are checking (prime) numbers less than $\sqrt n$, that is because each factor of $n$ that is less than $\sqrt n$ will correspond to one factor that is greater than $\sqrt n$. (Imagine if we had a factorization $n = a \cdot b$, where both $a$ and $b$ are less than $\sqrt n$. Then their product would ALSO be less than - and not equal to! - $n$)

Indeed, you could switch your method to just testing primes that are greater than $\sqrt n$, but we usually do it with smaller numbers, as those are easier to check.

Answer 2

1. If there is one factor $a$ that divides $n$, and $a\ge\sqrt n$, then $b=\frac na$ also divides $n$ and $b\le\frac n{\sqrt{n}}=\sqrt{n}$.

   In other words, if there is a factor greather than the square root of $n$ there is also a factor lesser that that root.

2. If there is a non-prime factor $a$ that divides $n$, then any factor of $a$, including all its prime factors, divide $n$.

So, once you find a prime $p$ between $2$ (included) and $\sqrt n$, you have simplified the problem by having $n/p$ an easier number to check. If you don't find that $p$ means that $n$ is prime.

Answer 3

The other elementary method, usually attributed to Fermat, is to check the squares slightly larger than $n$ and see if the difference is also a square. This works because $$ a^2 - b^2 = (a-b)(a+b). $$

The example I remember reading was a contest in Russia, they were asked simply to factor $8051.$ The person writing the story tried small primes and could not finish when time was up. However, $8100 = 90^2$ and $8100 - 8051 = 49 = 7^2,$ so $$ 8051 = 8100 - 49 = 90^2 - 7^2 = (90 - 7)(90 +7) = 83 \cdot 97. $$ As both $83$ and $97$ are primes, that is a complete factorization.

Your method, often called trial division, quickly finds small prime factors, if there are any. Fermat's method, which requires that you be quick and sure with squares, rapidly finds factors near $\sqrt n,$ which may not be prime already, so further work may be required.