Factors and Multiples

Section 7.4 Factors and Multiples

Subsection 7.4.1 Primes As Building Blocks

From the previous sections, we know some interesting and important facts about prime numbers themselves. Now we will look at how prime numbers are the building blocks of every composite number.

🔗

Let’s try and factor a number completely; that is, let’s also factor the composite factors we use so that there are no composite factors left and all of our factors are prime. Let’s try \(72\) again.

🔗

We know that

\begin{equation*} 72=6 \times 12\text{,} \end{equation*}

and both of these are composite, so we can factor both of these numbers:

\begin{equation*} 72= (2 \times 3) \times (3 \times 4). \end{equation*}

We know the numbers \(2\) and \(3\) are prime, so we cannot factor them any further. However, we can factor \(4\text{:}\)

\begin{equation*} 72=(2 \times 3) \times (3 \times (2 \times 2) ). \end{equation*}

Now all of our factors in our factorization are prime! Since multiplication is commutative and associative, we can regroup our factors so all of the \(2\)’s and \(3\)’s are together:

\begin{equation*} 72=(2\times 2 \times 2) \times (3 \times 3) = 2^3 3^2. \end{equation*}

We call this factorization of \(72\) a prime factorization. Let’s define this more carefully:

🔗

Definition 7.4.1.

A prime factorization of a number \(n \in \mathbb{N}\) is a factorization of \(n\) in the form \(n = p_1^{e_1}p_2^{e_2} \ldots p_k^{e_k}\) where the \(p_1, \ldots, p_k\) are distinct prime numbers in increasing order, there are \(k\) distinct primes, and the \(e_1, \ldots, e_k \) are the (natural number) exponents of these primes.

🔗

Example 7.4.2.

For \(72 = 2^3 3^2,\) we have that \(p_1 = 2, p_2 = 3\) (and in this case there are \(2\) distinct primes in the prime factorization), \(e_1=3\) (how many of the prime \(2\) we have in our prime factorization), and \(e_2=2\text{.}\)

🔗

If \(n=21000\) then you can check that \(21000=2^3 3 5^3 7\text{,}\) so \(p_1=2, p_2=3, p_3 = 5, p_4=7\text{,}\) there are \(4\) distinct primes so \(k=4,\text{,}\) and \(e_1=3, e_2=1, e_3=3, e_4=1.\)

🔗

We can make a tree diagram to show this factorization into primes: INSERT PIC OF TREE DIAGRAM

🔗

There are many different factorizations of \(72\) into two different factors, so let’s see what happens if we try starting with another one:

\begin{equation*} 72=4 \times 18 = (2\times 2) \times (2 \times 9) = (2\times 2) \times (2 \times (3 \times 3)) = (2\times 2 \times 2) \times (3 \times 3) = 2^3 3^2. \end{equation*}

We send up with the same prime factorization as the first example. Here is the tree diagram of this factorization: INSERT PIC OF TREE DIAGRAM

🔗

Checkpoint 7.4.3.

Try determining the prime factorization of \(72\) starting with other factorizations. What do you notice?

🔗

It looks like no matter how we start factoring \(72\) we end up with the same prime factorization.

🔗

Checkpoint 7.4.4.

Add some strength to this conjecture by choosing another number \(n\) and determine prime factorizations of \(n\) beginning with different factorizations into two numbers.

🔗

It looks like our conjecture may be true, and in fact it is. We will show that every number has exactly one prime factorization, so we can indeed talk about *the* prime factorization of \(n\text{.}\)

🔗

The idea of showing a prime factorization always exists is by using Theorem 7.3.10. We’ll factor out a prime at each step, and then keep going with the remaining composite factor until we have factored \(n\) completely into a product of primes.

🔗

Example 7.4.5.

Let’s start with \(60\text{.}\) We can easily see that \(2\) is a factor, so we write

\begin{equation*} 60=2 \times 30. \end{equation*}

Since \(30\) is composite, we can factor a prime out of it as well; again, it is easy to see that \(2\) is a prime factor:

\begin{equation*} 60 = 2 \times (2 \times 15). \end{equation*}

We now continue with \(15\) which is composite. We easily see that \(5\) is a prime factor:

\begin{equation*} 60 = 2 \times (2 \times (3 \times 5)). \end{equation*}

Since \(5\) is already prime, there is nothing more to factor; we can regroup to make it easier to read.

\begin{equation*} 60 = 2^2 \times 3 \times 5. \end{equation*}

🔗

Before we get to this theorem, we will need a small lemma. This lemma was originally proved by the ancient Greek mathematician Euclid and is usually named after him. The proof of this lemma uses some techniques from later in this section, so we will prove it later.

Lemma 7.4.6. Euclid’s Lemma.

Let \(a_1,a_2, \ldots, a_k \in \mathbb{N}\) and \(p\) be a prime number. If \(p\) divides the product of our \(a\)’s; that is, \(p \mid a_1a_2 \ldots a_k\) then \(p | a_i\) for some \(1 \leq i \leq k\text{.}\)

🔗

Here’s an example showing how the theorem above works:

🔗

Example 7.4.7.

Suppose \(a \in \mathbb{N}\) and we know that \(7 | (15\times 36 \times a)\text{.}\) By Lemma 7.4.6 we know that at least one of \(7 \mid 15 \text{,}\) \(7 \mid 36,\) or \(7 \mid a\) is true. Since we know both of the first two divisibility statements are false, it must be that \(7 \mid a\text{.}\)

🔗

The theorem we are about to prove is so important and special, it is given a name to reflect this fact.

🔗

Theorem 7.4.8. Fundamental Theorem of Arithmetic.

If \(n \geq 2\) is a natural number then \(n\) has a prime factorization and that prime factorization is unique.

🔗

Proof.

Let’s do this proof in two cases: first the easy case when \(n\) is a prime number itself. Then \(n\) is its own prime factorization, and we are done.

🔗

Now let \(n\) be a composite number. There are two things to show here: first, that we can factor \(n\) into a product of primes (the existence of a prime factorization), and secondly, that there is only one way to do so (the uniqueness of the prime factorization). We will do these two parts separately.

🔗

Existence: By Theorem 7.3.10 we know that \(n\) has at least one prime factor, let’s call one of them \(p\text{.}\) So we can factor this out so \(n=pc\) for some number \(c\text{.}\) If \(c\) is itself prime, we are done. If it isn’t, then \(c\) is composite and we can use Theorem 7.3.10 again. And we can repeat this process, which must end since \(n\) is a finite number and \(c < n\text{,}\) until we have completely factored \(n\) into a product of primes. Example 7.4.5 is an example of this part of the theorem.

🔗

Uniqueness: we will show this by contradiction, like in some previous proofs in this section. If there are numbers with two distinct prime factorizations, there must be a smallest one. We’ll show that if we pick the smallest one, we can find an even smaller number with two different prime factorizations, which is our contradiction.

🔗

Let \(n\) be the smallest number to have have two different prime factorizations, say \(n=p_1p_2\ldots p_s\) and \(n=q_1q_2\ldots q_t\) where the \(p\)’s and \(q\)’s are (not necessarily distinct) primes, and let’s say that \(s \leq t\text{.}\) We know that since \(p_1 \mid n\text{,}\) \(p_1 \mid q_1q_2\ldots q_t\) since \(n=q_1q_2\ldots q_t\)By Euclid’s Lemma, Lemma 7.4.6, we know that \(p_1 \mid q_i\) for one of the primes \(q_i\text{.}\) But since \(q_i\) is prime, its only factors are \(1\) and \(q_i\text{.}\) Since \(p_1 \neq 1\text{,}\) since it is a prime as well, it must be that \(p_1=q_i\text{.}\) Now let’s divide both sides by this common prime, remembering that \(p_1=q_i\text{:}\)

\begin{equation*} (n)\div p_1 = (p_1p_2p_3 \ldots p_s) \div p_1 = (q_1 q_2 \ldots q_{i-1}q_{i}q_{i+1} \ldots q_t) \div p_1 \end{equation*}

\begin{equation*} \rightarrow n\div p_1 = p_2p_3 \ldots p_s = q_1 q_2 \ldots q_{i-1}q_{i+1} \ldots q_t. \end{equation*}

Since \(p_1 > 1\) it’s clear that \(n > (n \div p_1)\text{.}\) But the equation above is two different prime factorizations for \(n \div p_1\text{,}\) so \(n\) was not the smallest number with two different prime factorizations. So this is a contradiction, which means that our original statement is true.

🔗

This is a very special idea. It means that every natural number is built from prime numbers, and is built in exactly one way. So we can study properties of factors of numbers by studying their prime factorization. We will do so in upcoming sections.

🔗

Subsection 7.4.2 How Many Factors Does A Number Have?

We know that all factors of numbers come in pairs, as if \(a \mid n\text{,}\) then \(n=ab\) for some other (possibly the same as \(a\)) factor \(b\text{.}\) We can also use the fact that one of the factors of \(n\) must be at most \(\sqrt{n}\text{.}\) So we can determine if each number \(a \leq \sqrt{n}\) is a factor, and we can get the other factor "for free".

🔗

Example 7.4.9.

Consider \(n=144\text{.}\) We know, checking via long division or using our divisibility rules, we obtain the following pairs of factors:

1 and 144
🔗

🔗
2 and 72
🔗

🔗
3 and 48
🔗

🔗
4 and 36
🔗

🔗
6 and 24
🔗

🔗
8 and 18
🔗

🔗
9 and 16
🔗

🔗
12 and 12
🔗

🔗

Since we have reached \(\sqrt{144}\) we know we can stop. We now count the unique factors (we don’t want to count 12 twice) and see we have 15 factors.

🔗

However, if we had a larger number, such as 3600, this would take a while, as we would have to check the divisibility of every number up to \(\sqrt{3600} = 60.\) Let’s see if we can determine an easier and more efficient way of counting the number of factors of a number. We will use the fact that each number has a prime factorization to help us out.

🔗

Example 7.4.10.

Let’s look again at \(n=144\text{.}\) Using our method from Theorem 7.3.10 we can write \(n\) as a product of primes: \(144=2^4 \times 3^2\text{.}\) Now let’s list the factors again, but also write their prime factorization:

🔗

1 and 144 \((2^0 \times 3^0)(2^4 \times 3^2)\)
🔗

🔗
2 and 72 \((2^1 \times 3^0)(2^3 \times 3^2)\)
🔗

🔗
3 and 48 \((2^0 \times 3^1)(2^4 \times 3^1)\)
🔗

🔗
4 and 36 \((2^2 \times 3^0)(2^2 \times 3^2)\)
🔗

🔗
6 and 24 \((2^1 \times 3^1)(2^3 \times 3^1)\)
🔗

🔗
8 and 18 \((2^3 \times 3^0)(2^1 \times 3^2)\)
🔗

🔗
9 and 16 \((2^0 \times 3^2)(2^4 \times 3^0)\)
🔗

🔗
12 and 12 \((2^2 \times 3^1)(2^2 \times 3^1)\)
🔗

🔗

Note that if \(a \mid n\text{,}\) then \(a\) must either be \(1\text{,}\) or a product of some of the \(2\)’s and \(3\)’s that are in the prime factorization of \(144\text{,}\) since we can think about grouping the primes in the prime factorization to make a pair of factors.

🔗

We can think: if \(a\) is a factor of \(144\) that we are making, how many choices for the number of \(2\)’s do we have? How many choices for the number of \(3\)’s do we have? Our factor \(a\) can have 0,1,2,3, or 4 copies of \(2\) (so 5 choices in total), and either 0,1, or 2 copies of \(3\) (so 3 choices in total). For example, if our factor has three \(2\)’s and one \(3\text{,}\) then \(a=2^3 \times 3 = 24\text{.}\)

🔗

Since we have 5 choices for the number of \(2\)’s and 3 choices for the number of \(3\)’s, we have \(5 \times 3 = 15\) total factors of \(144=2^4 \times 3^2\text{.}\)

🔗

This process works for any number, as long as we have it factored into its prime factorization. We will state this result as a theorem.

🔗

Theorem 7.4.11.

Let \(n \in \mathbb{N}\) where \(n\) has a prime factorization of \(n=p_1^{e_1}p_2^{e_2}\ldots p_k^{e_k}\) for some primes \(p_1, \ldots, p_k\) and non-negative exponents \(e_1, \ldots, e_k\text{.}\) Then \(n\) has \((e_1+1) \times (e_2 +1) \times \ldots \times (e_k+1)\) factors in total.

🔗

Proof.

If \(a\) is a factor of \(n\text{,}\) then \(a\) can be written as a subset of the prime factorization of \(n\text{.}\) Thus, for each prime \(p_i\text{,}\) we can have \(0, 1, 2 \ldots e_i\) copies of \(p_i\) in our factor, for a total of \(e_i+1\) choices. Since we have to make a choice for each different prime, and each choice is independent of other choices (that is, choosing the number of copies of one prime does not affect the number of choices for another prime), we can multiply these numbers of choices for each prime to determine the number of factors in total.

🔗

Example 7.4.12.

Let \(n=2^5 \times 3^3 \times 7 \times 11^2.\)

How many factors does \(n\) have in total?
🔗

🔗
How many prime factors does \(n\) have?
🔗

🔗
How many composite factors does \(n\) have?
🔗

🔗

🔗

Solution.

Using Theorem 7.4.11 we can say that \(n\) has \((5+1)(3+1)(1+1)(2+1) = 6 \times 4 \times 2 \times 3 = 144\) factors in total.
🔗

🔗
Since we were given the prime factorization of \(n\) we can simply read off the prime factors: \(2,3,7,\) and \(11\text{.}\) So \(n\) has \(4\) prime factors.
🔗

🔗
We know how many total factors there are, and we know how many prime factors there are. Let \(x\) be the number of composite factors of \(n\text{.}\) Remembering that factors are either composite, prime, or the number \(1\text{,}\) we can say that \(4+1+x=144\) and thus \(x=139\text{.}\)
🔗

🔗

🔗

Subsubsection 7.4.2.1 Putting It All Together

Let’s work through one example that uses many of the techniques and idea that we’ve encountered so far.

🔗

Example 7.4.13.

Determine the total number of factors of the number \(n=30,177,400\text{.}\)

🔗

Solution.

Since we don’t have the prime factorization of \(n\) we need to factor it completely into its prime factorization. There are many ways of doing this, but we can use our divisibility tests to determine some small factors, and then once our divisibility tests fail, we can use trial division to determine other prime factors.

🔗

First, it’s worth noting that by our divisibility test for \(3\) we know that \(3 \nmid n\text{.}\)

🔗

We first notice that \(n\) ends in two zeros, so we know that \(100 | n\text{.}\) Since \(100=2^2 \times 5^2\) we can write \(n=(2^2 \times 5^2)301,774\text{.}\) We now look for more prime factors of \(301,774.\) Since \(301,774\) ends in an even digit, we know that \(2 | 301,774\) and by division we can determine that \(301,174=2 \times 150,887. \) So \(n=(2^{2+1} \times 5^2) \times 150,887\text{.}\)

🔗

Next we may notice that \(1-5+0-8+8-7=-11\) so \(11 | 150,887\text{.}\) By division we see that \(150887=11 \times 13717\text{.}\) We then notice that \(1-3+7-1+7=11\) so \(11 | 13717\) and, again by division, \(13717=11 \times 1247\text{.}\) Putting this together we have \(n =(2^3 \times 5^2 \times 11^2) \times 1247.\)

🔗

We can check all of our divisibility tests and find that \(1247\) fails all of them. So by Summary we need to determine if \(1247\) has any prime factors great than 11. We note that \(31^2 = 961\) and \(37^2 = 1369\) and that \(31\) and \(37\) are consecutive primes so \(31 < \sqrt{1247} < 37\) so we need to check all prime numbers of size \(31\) and smaller. We’ve already checked \(2,3,5,11\) so we need to check \(7,13,17,19,23,29,31\) by trial division.

🔗

Using this trial division, we see that \(1247 \div 29=43\text{,}\) so we know that \(29\) is a factor of \(n\text{.}\) And since \(43\) is also prime, we have decomposed \(n\) into its prime factorization: \(n = 2^3 \times 5^2 \times 11^2 \times 29 \times 43\text{.}\) Thus by Theorem 7.4.11 we see that \(n\) has \((3+1)(2+1)(2+1)(1+1)(1+1)=144\) total factors. Of these factors, \(5\) are prime, \(1\) is the number \(1\text{,}\) and \(138\) are composite.

🔗

Subsection 7.4.3 Greatest Common Divisor and Least Common Multiple

Subsubsection 7.4.3.1 Unraveling the Concepts

When exploring the properties of numbers, particularly sets of natural numbers, the concept of the Greatest Common Divisor (GCD), also known as the Greatest Common Factor (GCF), is an important idea. The GCD of a set of numbers is essentially the largest factor that divides each number in the set without leaving a remainder.

🔗

Subsection Understanding GCD Through Prime Factorization

To understand the GCD, we can use the idea of prime factorizations to help us. Let’s consider an example to elucidate this process: finding the GCD of 42, 294, and 132. We begin by determining the prime factorization of each number. For instance, the prime factorization of these numbers would be:

🔗

\(\displaystyle 42 = 2 \times 3 \times 7 \)
🔗

🔗
\(\displaystyle 294 = 2 \times 3 \times 7^2\)
🔗

🔗
\(\displaystyle 132 = 2^2 \times 3 \times 11\)
🔗

🔗

If \(d\) is the GCD of our three numbers, then we know that \(d \mid 42, \ d \mid 294, \) and \(d \mid 132\text{.}\) So we must be able to make \(d\) by grouping prime factors of our three numbers in each number. For example, we know that \(2 \mid d\) since \(2\) is a factor or each of our numbers, and similarly for \(3\text{.}\) However, we know that \(7 \nmid d\) since \(7\) is not a prime factor of \(132\text{.}\) It follows that the smallest number of each prime factor will be factors of \(d\text{.}\)

🔗

In these factorizations, we identify the common prime factors and consider the lowest power (exponent) of these primes present in each number. For our example, the common primes are 2 and 3, and the lowest powers for these are \(2^1\) and \(3^1\text{,}\) respectively. Thus, the GCD is \(2 \times 3 = 6\) and we can write \(\text{GCD}(42,294,132)=6\text{.}\) This can be verified as:

🔗

\(\displaystyle 42 = 6 \times 7 = (2 \times 3) \times 7\)
🔗

🔗
\(\displaystyle 294 = 6 \times 49 = (2 \times 3) \times 7^2\)
🔗

🔗
\(\displaystyle 132 = 6 \times 22 = (2 \times 3) \times 2 \times 11\)
🔗

🔗

Note that there are no common factors of the remaining factors of each number. That is, \(\text{GCD}(7,49,22)=1\text{.}\)

🔗

Subsection Least Common Multiple (LCM)

The concept of the Least Common Multiple (LCM) is somewhat the inverse of the GCD. It represents the smallest number that is a multiple of every number in a set. To find the LCM, we again turn to prime factorization.

🔗

Subsection Exploring LCM with an Example

Using the same set of numbers (42, 294, and 132), we want a number \(m\) such that \(42 \mid m, \ 294 \mid m\text{,}\) and \(132 \mid m\text{.}\) So we need that the prime factorization of each number appears in the prime factorization of \(m\text{.}\) We can try and "build" \(m\text{:}\) We know that since \(42 = 2 \times 3 \times 7\text{,}\) it must be that \(m = 2 \times 3 \times 7 \times k\text{,}\) where \(k\) is the prime factors of the remaining numbers (294 and 132 so far; we’ll redefine \(k\) as we go), since \(m\) must be a multiple of \(42\text{.}\)

🔗

Now, \(m\) must also be a multiple of \(294\) so we can include the minimum prime factors in \(m\) so that \(m\) is a multiple of both \(42\) and \(294\) (so we need to keep all the prime factors of \(42\) in the prime factorization of \(m\)). We note that we need another \(7\text{,}\) so we can say that \(m=2 \times 3 \times 7^2 \times k\text{.}\)

🔗

Finally, we note that we need to include the prime factors of \(132\) in \(m\) as well. We note we already have a \(2\) and \(3\text{,}\) but still need to include another \(2\) and an \(11\text{.}\) So we must include these in our prime factorization. So \(m=2^2 \times 3 \times 7^2 \times 11\text{.}\)

🔗

We note that we needed to include the *maximum* number of each prime factor in each of our numbers.

🔗

Using the same set of numbers (42, 294, and 132), we determine the LCM by looking for the highest power (exponent) of each prime factor present in the factorizations of these numbers. In our example:

🔗

The maximum exponent for 2 is 2 (from 132)

🔗
The maximum exponent for 3 is 1 (common in all)

🔗
The maximum exponent for 7 is 2 (from 294)

🔗
The maximum exponent for 11 is 1 (from 132)

🔗

Thus, the LCM is calculated as \(2^2 \times 3 \times 7^2 \times 11\) which when expanded, gives us the LCM.

🔗

Understanding GCD and LCM is not just an academic exercise. These concepts are crucial in various mathematical operations, such as simplifying fractions (GCD) and finding common denominators (LCM). Moreover, they form a foundational understanding for more advanced mathematical concepts.

🔗

Subsection 7.4.4 Word Problems: GCD and LCM in Practice

Let’s delve into some practical word problems to see how the concepts of GCD and LCM are applied in real-life scenarios.

🔗

Subsubsection 7.4.4.1 Problem 1: Distributing Items in Boxes

Consider an online shop that needs to send \(72\) shirts, \(100\) hats, and \(144\) bags to a supplier. The goal is to use the smallest number of boxes possible, with each box containing the exact same items. This is a typical problem where we need to find the greatest common divisor (GCD) of the numbers \(72\text{,}\) \(100\text{,}\) and \(144\text{.}\)

🔗

After calculating, we find that the GCD of these numbers is \(4\text{.}\) Therefore, we need \(4\) boxes. Each box will contain \(72 \div 4 = 18\) shirts, \(100 \div 4 = 25\) hats, and \(144 \div 4 = 36\) bags. This distribution ensures that each box has the same items and uses the minimum number of boxes possible.

🔗

Subsubsection 7.4.4.2 Problem 2: Buying Ingredients for Burgers

Imagine owning a burger restaurant that requires patties, buns, and cheese slices for its burgers. Patties come in boxes of \(36\text{,}\) buns in bags of \(50\text{,}\) and cheese slices in packs of \(60\text{.}\) The objective is to purchase these ingredients in such quantities that there are no leftovers, and the number of burgers made is as small as possible.

🔗

This scenario calls for finding the least common multiple (LCM) of \(36\text{,}\) \(50\text{,}\) and \(60\text{.}\) Calculating this, we find the LCM to be \(900\text{.}\) Consequently, to make \(900\) burgers without leftovers, we need \(900 \div 36 = 25\) boxes of patties, \(900 \div 50 = 18\) bags of buns, and \(900 \div 60 = 15\) packs of cheese slices. This is the least number of burgers we can make without any ingredient left over.

🔗

Subsubsection 7.4.4.3 Visualizing GCD and LCM with Venn Diagrams

GCD and LCM can also be visualized using Venn diagrams. For example, consider the numbers \(180\) and \(144\text{.}\) By placing the prime factors of these numbers in a Venn diagram, we can easily identify the GCD (intersection of the sets) and the LCM (union of the sets). This visual approach offers a clear and intuitive understanding of how these concepts interrelate.

🔗

Subsection 7.4.5 Understanding the Euclidean Algorithm

The Euclidean Algorithm offers a systematic approach to finding the greatest common divisor (GCD) of two numbers, especially when their prime factorizations are complex or cumbersome. This algorithm is named after the ancient Greek mathematician Euclid.

🔗

Subsubsection 7.4.5.1 Basic Principles

To begin with, let’s review some essential principles:

🔗

List 7.4.14.

🔗

These principles reduce the problem of finding the GCD of two large numbers to a series of simpler calculations.

🔗

Theorem 7.4.15. Euclidean Algorithm.

Given two positive integers \(a\) and \(b\) (without loss of generality, assume \(a \geq b\)), the greatest common divisor (GCD) of \(a\) and \(b\) can be computed using the following iterative process:

🔗

Divide \(a\) by \(b\) to get a quotient \(q\) and a remainder \(r\text{,}\) where \(0 \leq r < b\text{.}\) Then, the GCD of \(a\) and \(b\) is the same as the GCD of \(b\) and \(r\text{.}\) Continue this process, replacing \(a\) with \(b\) and \(b\) with \(r\text{,}\) until \(r\) is zero. The GCD is the non-zero remainder from the previous step.

🔗

Proof.

Let \(d\) be the greatest common divisor of \(a\) and \(b\text{.}\) By the quotient-remainder theorem, \(a\) can be expressed as \(a = qb + r\text{,}\) where \(q\) is the quotient and \(r\) is the remainder, and \(0 \leq r < b\text{.}\)

🔗

Since \(d\) divides both \(a\) and \(b\text{,}\) it also divides \(a - qb\) (which is equal to \(r\)). Therefore, \(d\) divides \(r\text{.}\) Now, if there exists a larger common divisor of \(b\) and \(r\text{,}\) it would also divide \(a\) (since \(a = qb + r\)), contradicting the fact that \(d\) is the greatest common divisor of \(a\) and \(b\text{.}\) Hence, \(d\) is also the greatest common divisor of \(b\) and \(r\text{.}\)

🔗

Repeating this process iteratively, we reduce the problem to finding the GCD of smaller and smaller pairs of numbers, until the remainder \(r\) becomes zero. At that point, the GCD of the original pair \(a\) and \(b\) is the non-zero remainder from the previous division.

🔗

This completes the proof that the Euclidean Algorithm correctly computes the GCD of two positive integers.

🔗

Proof of the Euclidean Algorithm.

🔗

This completes the proof that the Euclidean Algorithm correctly computes the GCD of two positive integers.

🔗

Subsubsection 7.4.5.2 Applying the Euclidean Algorithm

The Euclidean Algorithm iteratively applies these principles. Let’s consider an example: finding the GCD of \(2716\) and \(9478\text{.}\)

🔗

We start by dividing the larger number by the smaller one, and then replace the original pair with the divisor and the remainder. We repeat this process until the remainder is zero. The GCD is the non-zero remainder just before this point.

🔗

In our example, we proceed as follows:

🔗

List 7.4.16.

🔗

Hence, the GCD of \(2716\) and \(9478\) is \(14\text{.}\)

🔗

Subsubsection 7.4.5.3 Additional Examples

Let’s explore another example: finding the GCD of \(785\) and \(554\) using the Euclidean Algorithm.

🔗

Following the same process, we calculate the GCD of these numbers to be \(1\text{.}\) This means that the numbers are coprime, since they have no common prime factors.

🔗

We can use the Euclidean algorithm to help us simplify fractions with large numerators and denominators:

🔗

Example 7.4.17. Example: Simplifying a Complex Fraction.

Simplify the fraction \(\frac{78696}{120932}\text{.}\)

🔗

Solution.

We use the Euclidean Algorithm to find the GCD of \(78696\) and \(120932\text{:}\)

🔗

List 7.4.18.

🔗

The GCD is \(4\text{.}\) Simplify the fraction by dividing both the numerator and denominator by \(4\text{:}\)

🔗

\(\frac{78696}{120932} = \frac{78696 \div 4}{120932 \div 4} = \frac{19674}{30233}\text{.}\)

🔗

Note that we know for certain that this fraction is in lowest terms since if this could be reduced further, we would have found a larger factor as the GCD of these numbers.

🔗

Prev Top Next