Prime Factorization
In number theory, the prime factorization of a number \(N\) is the set consisting of prime numbers whose product is \(N.\) As an example, the prime factorization of 90 is
\[90 = 2 \times 3 \times 3 \times 5.\]
Due to its uniqueness for every positive integer, the prime factorization provides a foundation for elementary number theory.
Prime Factors
The uniqueness of prime factorization is an incredibly important result, thus earning the name of fundamental theorem of arithmetic:
Fundamental Theorem of Arithmetic
Any integer greater than \(1\) is either a prime number, or can be written as a unique product of prime numbers, up to the order of the factors.
This statement implies that if a number is not prime, it has a prime number as its factor. For example, the factors of \(10\) are \(1, 2, 5,\) and \(10\), where \(2\) and \(5\) are both prime numbers. "Up to the order of the factors" means that it does not matter the order in which the product of the prime numbers is written.
What are the prime factors of \(12?\)
The factors of \(12\) are \(1\), \(2\), \(3\), \(4\), \(6\), and \(12\). The prime factors are \(2\) and \(3\). \(_\square\)
What are the prime factors of \(60?\)
The factors of \(60\) are \(1\), \(2\), \(3\), \(4\), \(5\), \(6\), \(10\), \(12\), \(15\), \(20\), \(30\) and \(60\). The prime factors are \(2\), \(3\), and \(5\). \(_\square\)
If \(x,y,z\) are three different prime numbers such that \(N=x\times y\times z\), how many positive divisors does \(N\) have excluding \(1\) and itself.
Since \(N=x\times y\times z\), we can conclude that \(x, y\) and \(z\) are the factors of \(N\). Since \(x, y\) and \(z\) are prime numbers, we can't factor them to get any other number, so that gives us a total of \(3\) numbers.
But wait, we know that if \(x\) and \(y\) are factors of \(N\), then \(x\times y\) is also a factor of \(N\). So a combination of two factors out of the three factors is also a divisor of \(N\). In other words, we have \(x\times y\), \(x\times z\) , and \(y\times z\) as factors of \(N,\) which are another \(3\) in addition to the \(3\) above.
Note that \(x\times y\times z \) is also a combination that is a factor of \(N\), but it equals the number itself and is therefore omitted.
So we have a total of \(6\) divisors, excluding \(1\) and the number itself. \(_\square\)
Prime Factorization
Prime factorization means writing a number as a product of primes.
What is the prime factorization of \(12?\)
We have
\[ 12 = 2 \times 2 \times 3 = 2^2 \times 3. \ _\square\]
For larger numbers, it is often easiest to find the prime factorization of a number by starting with smaller primes. For example, when factorizing the number \(72\), we start by dividing it by \(2,\) which leaves us with \(36\). We observe that this is still divisible by \(2\), so we once again divide it, obtaining \(18\). We repeat this once more, which leaves us with \(9\). We then realize \(9\) is not divisible by \(2\) and thus look for the next prime integer that the number is divisible by, which happens to be \(3\). We then divide \(9\) by \(3\), which leaves us with \(3\). Therefore, \(72\)= \(2^{3} \times 3^{2}\).
Prime Factor Trees
A prime factor tree provides a pictorial representation of the prime factorization for a positive integer. Starting with the given integer \(N\) at the top of the tree, two branches are drawn toward two positive factors of \(N.\) The process is repeated for the numbers at the end of each branch that is drawn until each "leaf" is a prime number.
The factor tree for 72 is shown below.
tree
Keep factoring the divisors until the divisors reach a prime number:
tree
All the divisors have been factored to a prime number. Multiplying all the leaves of the tree gives
\[2\times 2\times 2\times3\times 3=72.\]
What is the prime factorization of \(120?\)
The factor tree looks like this:
Thus, the prime factorization of \( 120 \) is \( 2^{3} \times 3 \times 5 \). \(_\square\)
Applications
The problem of prime factorization is highly associated with the field of cryptography, since factorizing large numbers is difficult even for computers. Cryptosystems such as RSA encryption are based (in part) on this principle.
The concept of primality can also be extended to ring theory and fields other than the integers. For instance, 5 is prime in the integers, but not in the Gaussian integers, since \(5=(2+i)(2-i)\). This idea is paramount in algebraic number theory, particularly in analyzing problems like writing integers as the sum of two squares.