Finding the number of factors

Question

To find the number of factors of a number, we can prime factorise that number and add one to every power, before multiplying those powers together. By why can every factor of that number be made via some part of the original numbers prime factorisation. How can we prove that this method holds true for all numbers?

Furthermore, how do we prove the method for finding the LCM and GCF of a number via prime factorisation. I can't see the logic behind it.

Answer 1

This holds true because of the following fact:

Every natural number $n$ greater then $2$ is either prime or a product of prime numbers. To prove it, you can use strong induction:

• base case: for $n=2$ is immediate
• assume it is true for all $k \leq n$.

If we show that $n+1$ is either prime or a product of primes, the result follows

If there are $2\leq c,d \leq n$ s.t. $cd=n+1$. By hypothesis, $c,d$ are either prime or product of primes. Thus, $n+1$ is product of primes. If there aren't $2\leq c,d \leq n$ s.t. $cd=n+1$, $n+1$ is prime.

Hence, the result follows.