## 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].

### Theorem 10.3.1. Fundamental Theorem of Arithmetic.

Every integer greater than \(1\) can be written uniquely as a prime number or a product of prime numbers.

The unique representation of each integer greater than 1 that is guaranteed by the Fundamental Theorem of Arithmetic (Theorem 10.3.1) 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.3.2. Prime factorization.

We provide the prime factorization for sample integers greater than 1.

\(\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.3.3 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.3.4. Find prime factorization.

Give the prime factorization of 18810.

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

Now, 10 is definitely composite, so we can further break it down as \(10=2\cdot 5\) to get

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

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

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

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

### Subsection 10.3.1 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.3.5. \(\gcd\) from factorization with details.

Let integers \(a\) and \(b\) be given in factored form:

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 \(a\) 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

#### Example 10.3.6. \(\gcd\) from factorization.

Let integers \(a\) and \(b\) be given in factored form:

So \(gcd(a,b) = 2^3 \cdot 7^4 \cdot 19^2\text{.}\)

In Checkpoint 10.3.7 find the greatest common divisor of two integers whose prime factorization is given.

#### Checkpoint 10.3.7. 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 10.3.2 A primality test

There are many possible paths to finding the prime factorization of a number. Because the Fundamental Theorem of Arithmetic (Theorem 10.3.1) 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.3.4, 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.3.8.

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.3.8 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.3.8 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.3.8 in the next example. This method of showing that a number is prime is called *trial division*.

#### Problem 10.3.9. Prove primality.

Prove that \(523\) is prime.

By Theorem 10.3.8 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

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.3.10. Determine primality.

Determine whether \(139\) is a prime number.

We use Theorem 10.3.8 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

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.3.11.

#### Checkpoint 10.3.11. 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

select

divides 323

does not divide 323

we do not need to check divisibility

3 is

select

less than w

greater than w

select

divides 323

does not divide 323

we do not need to check divisibility

5 is

select

less than w

greater than w

select

divides 323

does not divide 323

we do not need to check divisibility

7 is

select

less than w

greater than w

select

divides 323

does not divide 323

we do not need to check divisibility

11 is

select

less than w

greater than w

select

divides 323

does not divide 323

we do not need to check divisibility

13 is

select

less than w

greater than w

select

divides 323

does not divide 323

we do not need to check divisibility

17 is

select

less than w

greater than w

select

divides 323

does not divide 323

we do not need to check divisibility

19 is

select

less than w

greater than w

select

divides 323

does not divide 323

we do not need to check divisibility

23 is

select

less than w

greater than w

select

divides 323

does not divide 323

we do not need to check divisibility

29 is

select

less than w

greater than w

select

divides 323

does not divide 323

we do not need to check divisibility

31 is

select

less than w

greater than w

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

\(17.9722007556114\)

\(\text{less than w}\)

\(\text{does not divide 323}\)

\(\text{less than w}\)

\(\text{does not divide 323}\)

\(\text{less than w}\)

\(\text{does not divide 323}\)

\(\text{less than w}\)

\(\text{does not divide 323}\)

\(\text{less than w}\)

\(\text{does not divide 323}\)

\(\text{less than w}\)

\(\text{does not divide 323}\)

\(\text{less than w}\)

\(\text{divides 323}\)

\(\text{greater than w}\)

\(\text{we do not need to check divisibility}\)

\(\text{greater than w}\)

\(\text{we do not need to check divisibility}\)

\(\text{greater than w}\)

\(\text{we do not need to check divisibility}\)

\(\text{greater than w}\)

\(\text{we do not need to check divisibility}\)

\(\text{composite}\)

Factoring becomes harder as numbers become larger.