How to understand special prime factorization method

Question

Normally when we want to find the Prime Factorization of a number, we will keep dividing that number by the smallest prime number (2), until it can't be divided then we move on to the next prime number after that (3) and move on until it become 1, right?

For example number $18$: we will keep dividing $18$ by $2$, $(18/2 = 9)$, $9$ can't be divided by $2$ so we move on $3$, $9/3 = 3$, $3/3 = 1$. So $18 = 2\cdot3\cdot3$

But the above method requires us to know the prime number first $(2,3,5,...)$. I found a method on the internet which doesn't care about the prime numbers at all. Instead of dividing by $2,3,5$ (prime number), keep dividing by $2,3,4,5,6,....n$ (the same rule as above). Problem is I don't know why it works.

For example number $420$:

$$420/2 = 210;\quad 210/2 = 105;\quad 2 \nmid 105$$

$$105/3 = 35;\quad 3 \nmid 35$$

$$35/4,\quad 4 \nmid 35$$ $$35/5 = 7,\quad 5,6 \nmid7,\quad 7/7=1.$$ so $420 = 2\cdot2\cdot3\cdot5\cdot7.$

My question is, how can after being divided by the prime number as many times as possible, the remaining can't be divided by other normal numbers anymore? For example, after being divided by $2,3$ as many times as possible, the remain can't be divided by $4$ anymore; after being divided by $2,3,5,7$, as many times as possible, the remain can't be divided by 8,9,10 anymore; etc. How to prove this?

I think this is quite important. Since if you write a program finding Prime Factorization of a number, we don't need to write another program to check for Prime Number any more. Just divided from $2$ to $n$.

Answer 1

The very first composite number is 4. Let's say you took a number x, say 210, and you removed the factors 2 leaving 105, then 3 leaving 35. Now the remainder cannot be divisible by 4, because if it was, it would also be divisible by every factor of 4, that is 2. But the factors 2 have been removed. The next composite number is 6; the remainder cannot be divisible by 6 because it would have to be divisible both by 2 and 3. These are the factors that were already removed.

You check for factors 2, 3, 4, 5, 6, 7, 8 etc. but only the primes in that sequence, 2, 3, 5 and 7 can possibly be found as factors.

If you think finding all the primes that might be divisors is too much work, you can check for divisibility by 2 and 3, and all larger primes are of the form 6k +/- 1, so you can check for divisibility by 5/7, 11/13, 17/19, 23/25 etc. with 25 being the first non-prime in the sequence.

Answer 2

I am going to address more than was asked in the question, because the idea of prime factoring $n$ by dividing by numbers (or primes) all the way up to $n$ is excruciatingly inefficient.

Important facts include:

(1) Every integer greater than $1$ is divisible by a prime (this includes the case of a prime being divisible by itself).

(2) Every composite number $n$ is divisible by a prime $p$ with $p\le \sqrt{n}$.

(3) If $n$ is divisible by a composite number, say $c$, it is also divisible by all the prime factors of $c$. [More generally for positive integers, if $x$ is divisible by $y$ and $y$ is divisible by $z$, then $x$ is divisible by $z$.]

To answer the question in the post: Fact (3) means that when you use the method of dividing by every number ($2, 3, 4, 5, 6,...$) in order, you never get anything new when you are dividing by a composite. For instance, by the time you divide by $6$ you will have removed all factors of $2$ and $3$, so the remaining piece will not be divisible by $6$. This is inefficient in terms of the number of trial divisions you do, but it has the advantage of not having to know all the primes up to an appropriate limit in advance. (So it's a trade off).

Also because of (2), once your trial divisor is greater than the square root of the remaining piece, you are done. That remaining piece, if greater than $1$ is prime.

Example: To prime factor $8253$, your work might look like this:

$8253$ is not divisible by $2$.

$8253 = 3\cdot 2751=3\cdot 3\cdot 917$. [The "remaining piece" is $917$.]

$917$ is not divisible by $5$, but it is divisible by $7$. We get:

$8253=3\cdot 3\cdot 7\cdot 131$. [The "remaining piece" is $131$.]

$131$ is not divisible by $7$ or $11$. The next prime $13$ is greater than $\sqrt{131}$, and so $131$ is prime.

Our final result is $8253=3^2\cdot 7\cdot 131$, and we only had to trial divide up to $11$.