Prime factorization

• For example, \(6=2\times 3\), and \(8=2\times 2\times 2\).
• The process by which we express a composite number as the product of primes is called prime factorization.

Prime factorization

The most systematic method of doing this is to attempt dividing the number by the smallest prime (which is \(2\)). If the number is divisible, then we repeat the process with the quotient of division. If it is not divisible, we try the next prime. The process continues until the quotient is \(1\), at which point we are done. Consider the following examples.

\[\begin{array}{ccc} \begin{array}{r|r} 2 & 18 \\ 3 & 9 \\ 3 & 3 \\ & 1 \end{array}\qquad&\qquad \begin{array}{r|r} 3 & 75 \\ 5 & 25 \\ 5 & 5 \\ & 1 \end{array}\qquad&\qquad \begin{array}{r|r} 2 & 48 \\ 2 & 24 \\ 2 & 12 \\ 2 & 6 \\ 3 & 3 \\ & 1 \end{array} \\ 18=2\times 3^2 \qquad&\qquad 75=3\times 5^2 \qquad&\qquad 48=2^4\times 3 \end{array}\]

Another method is the ‘tree’ method, by which a number is divided into whatever you can figure out quickly. You write the divisor and the quotient in the ‘leaves’ of a tree, with its trunk at the original number. You continue doing the same thing with each leaf until it is not divisible by any prime anymore. For example, the previous numbers can be factored as follows.