Theorem 10.10. Fundamental Theorem of Arithmetic.
Every integer greater than \(1\) can be written uniquely as a prime number or a product of prime numbers.
Section 10.3 Prime Factorization
Most of the results of unique prime factorization were already contained in Euclid’s Elements [5]. An early modern formulation of the result can be found in Gauss Disquisitiones arithmeticae [6].
The unique representation of each integer greater than 1 that is guaranteed by the Fundamental Theorem of Arithmetic (Theorem 10.10) is called the prime factorization of the integer.
For composites, the prime factorization may include multiple copies of the same prime. If so, exponents are typically used to condense the prime factorization. This is demonstrated in the following example.
Example 10.11. Prime factorization.
We provide the prime factorization for selected integers.
- \(\displaystyle 100 = 2 \cdot 2 \cdot 5 \cdot 5 = 2^2 \cdot 5^2\)
- \(\displaystyle 7007 = 7 \cdot 7 \cdot 11 \cdot 13 = 7^2 \cdot 11 \cdot 13\)
- \(\displaystyle 23498357349 =3 \cdot 53 \cdot 397 \cdot 372263\)
In the video in Figure 10.12 we present once more the fundamental theorem of arithmetic and give examples of its application. This is followed by a detailed description of these applications.
In order to arrive at the prime factorization of a composite \(n\text{,}\) we can begin by simply breaking the composite \(n\) into the product of two integers \(a\) and \(b\) that are each greater than 1. We write \(n=a\cdot b\) and then take a closer look at whether or not \(a\) and \(b\) are prime. If \(a\) and \(b\) are prime, we are essentially done. However, if either \(a\) or \(b\) is composite, we must continue the process by finding factors of the composite number(s). But, note that it will always be true that \(a\) and \(b\) are both less than \(n\text{,}\) so progress has been made.
Problem 10.13. Find prime factorization.
Give the prime factorization of 18810.
Solution.
We present a solution that explains some of the “figuring” that might be useful in determining the prime factorization. Since 18810 ends in a 0, we automatically know that 10 is a factor, and we write
\begin{equation*}
18810=10\cdot 1881\text{.}
\end{equation*}
Now, 10 is definitely composite, so we can further break it down as \(10=2\cdot 5\) to get
\begin{equation*}
18810=2\cdot 5\cdot 1881\text{.}
\end{equation*}
It is less clear whether 1881 is prime or composite. Since 1881 is an odd number, it does not have a factor of 2. We move onto the next prime number, 3, and see if that is a factor of 1881. It turns out that it is.
A quick check to determine whether or not a number is divisible by 3 is to add up the digits of the number and determine whether or not that sum is divisible by 3. For the case of 1881, we have that \(1+8+8+1=18\text{.}\) It is easier to see that the sum, 18, is divisible by 3. But if that is not obvious, we can continue to sum the digits to get that \(1+8=9\text{,}\) which is clearly divisible by 3.
Since \(1881\) is divisible by \(3\text{,}\) we can compute that \(1881=3\cdot 627\text{.}\) We now have
\begin{equation*}
18810=2\cdot 5\cdot 3\cdot 627\text{.}
\end{equation*}
We can perform the same summing digits check mentioned above to determine that 627 is also divisible by 3. Since \(627=3\cdot 209\text{,}\) we now have
\begin{equation*}
18810=2\cdot 5\cdot 3\cdot 3\cdot 209\text{.}
\end{equation*}
Summing the digits of \(209\) tells us that 209 is not divisible by 3 since \(2+0+9=11\) is not divisible by 3. So, we move onto the next prime number, 5. Since 209 does not end in 0 or 5, we conclude that 5 is not a factor. We continue moving through the prime numbers and conclude that 7 is not a factor of 209 but that 11 is. Since \(209=11\cdot 19\text{,}\) we now have
\begin{equation*}
18810=2\cdot 5\cdot 3\cdot 3\cdot 11\cdot 19\text{.}
\end{equation*}
Since 19 is also a prime, we have now found all of the prime factors of 18810 and how many times they each occur. However, we typically rearrange the prime factors into non-decreasing order and use exponents to condense the prime factorization. Our final answer is
\begin{equation*}
18810=2\cdot 3^2\cdot 5\cdot 11\cdot 19\text{.}
\end{equation*}
Subsection Greatest common divisor from prime factorization
Sometimes it is convenient when the prime factorization of numbers is known. For example when two numbers are given in factored form their greatest common divisor can be composed from the common factors of the two numbers.
Example 10.14. \(\gcd\) from factorization with details.
Let integers \(a\) and \(b\) be given in factored form:
\begin{equation*}
a=2^{7} \cdot 3^2 \cdot 5 \cdot 7^6 \cdot 11 \text{ and } b= 3^{4} \cdot 7^4 \cdot 11^{3} \cdot 17
\end{equation*}
To determine the greatest common divisor of \(a\) and \(b\) we go through all the prime power factors of both \(a\) and \(b\) and check whether they yield a common factor.
The integer \(a\) has the factor \(2^7\text{,}\) but the integer \(b\) is not divisible by \(2\text{.}\) Thus the greatest common divisor of \(a\) and \(b\) is not divisible by \(2\)
The integer \(a\) has the factor \(3^2=3\cdot 3\) and the integer \(b\) has the factor \(3^4=3\cdot 3\cdot 3\cdot 3\text{.}\) Thus the greatest power of \(3\) that divides both \(a\) and \(b\) is \(3^2=3\cdot 3\text{.}\) So the greatest common divisor of \(a\) and \(b\) is divisible by \(3^2\text{.}\)
The integer \(a\) has the factor \(5\text{,}\) but the integer \(b\) is not divisible by \(5\text{.}\) So the greatest common divisor of \(a\) and \(b\) is not divisible by \(5\text{.}\)
The integer \(a\) has the factor \(7^6=7\cdot 7\cdot7\cdot7\cdot7\cdot7\) and the integer \(b\) has the factor \(7^4=7\cdot7\cdot7\cdot7\text{.}\) Thus the greatest power of \(7\) that divides both \(a\) and \(b\) is \(7^4=7\cdot7\cdot7\cdot7\text{.}\) So the greatest common divisor of \(a\) and \(b\) is divisible by \(7^4\text{.}\)
The integer \(a\) has the factor \(11\) and the integer \(b\) has the factor \(11^3=11\cdot 11\cdot 11\text{.}\) Thus the greatest power of \(11\) that divides both \(a\) and \(b\) is \(11\text{.}\) So the greatest common divisor of \(a\) and \(b\) is divisible by \(11\text{.}\)
The integer \(b\) has the factor \(17\text{,}\) but the integer \(a\) is not divisible by \(17\text{.}\) Thus the greatest common divisor of \(a\) and \(b\) is not divisible by \(17\)
We have found that the greatest common divisor \(\gcd(a,b)\) of \(a\) and \(b\) is divisible by \(3^2\) and \(7^4\) and \(11\text{.}\) So we know that \(\gcd(a,b)\) has the factor \(3^2\cdot 7^4 \cdot 11\text{.}\)
We have also checked the other prime power factors of both \(a\) and \(b\) and found that the primes do not yield a common factor of \(a\) and \(b\text{.}\) The greatest common divisor of \(a\) and \(b\) cannot have any prime factors that do not occur in the prime factorization of both \(a\) and \(b\text{.}\) So we have found all prime power factors of \(\gcd(a,b)\text{.}\)
We conclude that
\begin{equation*}
\gcd(a,b)=3^2\cdot 7^4 \cdot 11\text{.}
\end{equation*}
Example 10.15. \(\gcd\) from factorization.
Let integers \(a\) and \(b\) be given in factored form:
\begin{equation*}
a=2^{3} \cdot 3^2 \cdot 7^5 \cdot 19^2 \text{ and } b= 2^{5} \cdot 7^{4} \cdot 19^{5} \cdot 23
\end{equation*}
So \(gcd(a,b) = 2^3 \cdot 7^4 \cdot 19^2\text{.}\)
In Checkpoint 10.16 find the greatest common divisor of two integers whose prime factorization is given.
Checkpoint 10.16. Find \(\gcd\) given factors.
What are the greatest common divisors of the following pairs of integers ?
If \(a= 2^3 \cdot 3^3 \cdot 5\) and \(b= 2^4 \cdot 3^4 \cdot 5\) then
\(\gcd(a,b)=\)
If \(a=2^{12} \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13\) and \(b= 3^{12} \cdot 5 \cdot 11^{9} \cdot 17\) then
\(\gcd(a,b)=\)
If \(a= 2^3 \cdot 7\) and \(b= 5^3 \cdot 13\) then
\(\gcd(a,b)=\)
Subsection A primality test
There are many possible paths to finding the prime factorization of a number. Because the Fundamental Theorem of Arithmetic (Theorem 10.10) guarantees the uniqueness of the prime factorization, the order in which we find the factors does not matter. Based on the solution given for Problem 10.13, it is apparent that finding the prime factorization of composite numbers can involve many steps.
Generally speaking, the bigger the composite number is, the harder it is to find its prime factorization. It could be true that a big composite number has lots of different prime factors, lots of repeated prime factors, or even big prime factors. The next result provides us with a tool that will help us determine when we can say with confidence that we have completed a prime factorization of a composite.
Theorem 10.17.
If \(n\) is composite, then \(n\) has a prime factor less than or equal to \(\sqrt{n}\text{.}\)
Proof.
A composite \(n\) can be written as \(n = a\cdot b\text{,}\) where \(a\) and \(b\) are integers greater than 1. If \(a\) and \(b\) are both greater than \(\sqrt{n}\text{,}\) then \(n = a\cdot b > \sqrt{n}\cdot \sqrt{n} = n\) would have to be true. However, \(n > n\) is false, so either \(a\) or \(b\) must be less than or equal to \(\sqrt{n}\text{.}\) All prime factors of \(a\) are less than or equal to \(a\text{,}\) and these are also prime factors of \(n\text{.}\) If \(a \le \sqrt{n}\text{,}\) then \(n\) has a prime factor less than or equal to \(\sqrt{n}\text{.}\) The analogous argument holds if \(b\le \sqrt{n}\text{.}\)
A consequence of Theorem 10.17 is that if an integer \(n>1\) does not have a prime factor less than or equal to \(\sqrt{n}\text{,}\) then \(n\) is prime. This understanding of Theorem 10.17 gives us a tool to verify that an integer \(n>1\) is prime without exhaustively checking that each integer \(2, 3, \ldots,
n-1\) fails to be a factor.
To conclude that a natural number \(n>1\) is prime, we only need to know that \(n \fmod p \neq 0\) for each prime \(p\leq \sqrt{n}\text{.}\) We do not actually need to know the exact value of each \(n \fmod p\text{,}\) we just need to know that the value is not zero. So, if we do not get an integer when we divide \(n\) by \(p\text{,}\) then we automatically know that \(n \fmod p \neq 0\text{,}\) and that is sufficient.
We demonstrate this use of Theorem 10.17 in the next example. This method of showing that a number is prime is called trial division.
Problem 10.18. Prove primality.
Prove that \(523\) is prime.
Solution.
By Theorem 10.17 it suffices to show that no prime less than or equal to \(\sqrt{523} = 22.869\ldots\) is a factor of \(523\text{.}\) The primes less than or equal to \(\sqrt{523}\) are 2, 3, 5, 7, 11, 13, 17, and 19. We compute
\begin{align*}
523 \fmod 2 \amp = 1\\
523 \fmod 3 \amp = 1\\
523 \fmod 5 \amp = 3\\
523 \fmod 7 \amp = 5\\
523 \fmod 11 \amp = 6\\
523 \fmod 13 \amp = 3\\
523 \fmod 17 \amp = 13\\
523 \fmod 19 \amp = 10\text{.}
\end{align*}
Since none of the above values is 0, we conclude that none of the primes less than or equal to \(\sqrt{523}\) is a factor of 523. Thus, \(523\) is prime.
Problem 10.19. Determine primality.
Determine whether \(139\) is a prime number.
Solution.
We use Theorem 10.17 to determine whether or not \(139\) is prime by checking whether or not each prime less than or equal to \(\sqrt{139} = 11.7898\ldots\) is a factor of 139. The primes less than or equal to \(\sqrt{139}=11.7\ldots\) are \(2\text{,}\) \(3\text{,}\) \(5,\) \(7,\) and \(11\text{.}\) We compute
\begin{align*}
139 \fmod 2 \amp =1\\
139 \fmod 3 \amp =1\\
139 \fmod 5 \amp =4\\
139 \fmod 7 \amp =6\\
139 \fmod 11 \amp =7\text{.}
\end{align*}
Since none of the above values is 0, we conclude that none of the primes less than or equal to \(\sqrt{139}\) is a factor of 139. Thus 139 is prime,
Now try this method for determining primality yourself in Checkpoint 10.20.
Checkpoint 10.20. Prime or composite with proof.
We want to determine whether the integer 323 is prime or composite.
Let w be an approximation to the square root of 323 (to a precision of at least one digit after the decimal point).
We use w= (give at least one digit after the decimal point).
In the following select `we do not need to check divisibility’, if the selection for a previous line already allows you to make the conclusion.
2 is
- select
- less than w
- greater than w
and
- select
- divides 323
- does not divide 323
- we do not need to check divisibility
3 is
- select
- less than w
- greater than w
and
- select
- divides 323
- does not divide 323
- we do not need to check divisibility
5 is
- select
- less than w
- greater than w
and
- select
- divides 323
- does not divide 323
- we do not need to check divisibility
7 is
- select
- less than w
- greater than w
and
- select
- divides 323
- does not divide 323
- we do not need to check divisibility
11 is
- select
- less than w
- greater than w
and
- select
- divides 323
- does not divide 323
- we do not need to check divisibility
13 is
- select
- less than w
- greater than w
and
- select
- divides 323
- does not divide 323
- we do not need to check divisibility
17 is
- select
- less than w
- greater than w
and
- select
- divides 323
- does not divide 323
- we do not need to check divisibility
19 is
- select
- less than w
- greater than w
and
- select
- divides 323
- does not divide 323
- we do not need to check divisibility
23 is
- select
- less than w
- greater than w
and
- select
- divides 323
- does not divide 323
- we do not need to check divisibility
29 is
- select
- less than w
- greater than w
and
- select
- divides 323
- does not divide 323
- we do not need to check divisibility
31 is
- select
- less than w
- greater than w
and
- select
- divides 323
- does not divide 323
- we do not need to check divisibility
Now conclude whether 323 is prime or composite.
The integer 323 is
- select
- prime
- composite
.
Factoring becomes harder as numbers become larger.
One man is sitting at a computer. Another man is sitting at a separate desk. There is a clock which reads 2:53
Man at desk: 253 is 11x23 Man at computer: What? Man at desk: I’m factoring the time.
Man at desk: I have nothing to do, so I’m trying to calculate the prime factors of the time each minute before it changes. Man at desk: It was easy when I started at 1:00, but with each hour the number gets bigger. Man at desk: I wonder how long I can keep up.
Man at desk reaches back and touches the clock. Clock: beep
Clock now reads 14:53. Man at desk: Hey! Man at computer: Think fast.
Title text: I occasionally do this with mile markers on the highway.
I occasionally do this with mile markers on the highway.
https://xkcd.com/247).
