Section 1: Rings and Fields
The Greatest Common Divisor of Two Numbers
HW # 1-2 p. 7 at the end of the notes
In this section, we examine the important concept of the greatest common divisor of two numbers and the computations involved when computing it.
The Greatest Common Divisor of Two Numbers
The greatest common divisor of two numbers, denoted as gcd(a,b), is the largest number that divides a and b evenly with no remainder. For example, gcd(20, 30) = 10 and
gcd(72, 108) = 36. Find the greatest common division of two numbers becomes more difficult is the numbers become larger. However, there is a well known method known as the Euclidean algorithm that will allows us to find the greatest common divisor of larger numbers which we state next.
The Euclidean Algorithm
The Euclidean Algorithm makes repeated use of the division algorithm to find the greatest common divisor of two positive integers. If we are given two positive integers a and b where [pic], then if [pic], then [pic], If [pic], then we compute
[pic]
The last nonzero remainder, [pic], is the greatest common divisor of a and b, that is, [pic].
Note: In general, we can write each equation of the Euclidean Algorithm Table as
[pic]
Here, we can assign [pic] and [pic].
Example 1: Find the greatest common divisor of a = 2299 and b = 627.
Solution:
█
Example 2: Find the greatest common divisor of a = 54321 and b = 9875.
Solution: Noting that 54321 > 9875 and applying the Euclidean algorithm gives
[pic]
Since the last non-zero remainder is 1, gcd(54321, 9875)= 1.
█
Theorem 1: For any two positive integers a and b, there are integers u and v where
[pic]
Fact: When executing the Euclidean algorithm equations,
[pic]
We can create a table to determine the [pic], [pic], and [pic] as follows:
[pic][pic]
Notes
1. The quotients under Q and remainders under R are computed using the basic Euclidean
algorithm process. The table is complete when [pic]. The last non-zero remainder [pic] is the greatest common divisor of a and b, that is, [pic].
2. The [pic] under U and [pic] under V are found using the formulas
[pic].
3. For row i, we have [pic]. The values u and v where [pic] are found in the last row where [pic]. That is, [pic] and [pic].
Example 3: Use an Euclidean algorithm table to find values u and v where [pic] for a = 2299 and b = 627.
Solution:
█
Example 4: Use an Euclidean algorithm table to find values u and v where [pic] for a = 54321 and b = 9875.
Solution: From Example 2, we ran the Euclidean Algorithm to find that [pic] using the following process:
[pic]
Hence, the [pic]. Setting [pic] and [pic] and [pic] and using the equations
[pic]
gives the following calculation for each row.
[pic], [pic], [pic].
[pic], [pic].
[pic], [pic].
[pic], [pic]
[pic].
[pic], [pic]
[pic].
The previous results give the following Euclidean Algorithm Table:
[pic]
continued on next page
From the last row, we see that [pic] and [pic] This answer can be verified by checking
[pic].
█
Exercises
1. Use the Euclidean Algorithm to find the greatest common divisor of the following
numbers.
a. 72 and 300.
b. 629 and 357
c. 52598 and 2541
d. 3854682 and 1095939
e. 101 and 127.
2. For each exercise for Exercise 1, assign a and b and generate an Euclidean algorithm table to find integers u and v where [pic].
-----------------------
[pic]
[pic]
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- the nature of science section 1 answers
- 14th amendment section 1 summary
- 14th amendment section 1 meaning
- article 1 section 1 constitution
- chapter 15 section 1 pages 532 537
- section 1 5 salary
- section 1 reinforcments
- article ii section 1 of the constitution
- section 1 chapter 2 science
- 14th amendment section 1 explained
- 14th amendment section 1 text
- economics section 1 assessment answers