The Euclidean algorithm, or process, for finding the greatest common integral di
ID: 3121233 • Letter: T
Question
The Euclidean algorithm, or process, for finding the greatest common integral divisor (g. c. d.) of two positive integers is so named because it is found at the start of Book VII of Euclid's Elements, although the process no doubt was known considerably earlier. This algorithm is at the foundation of several developments in modern mathematics. Stated in the form of a rule, the process is this: Divide the larger of the two positive integers by the smaller one, then divide the divisor by the remainder. Continue this process, of dividing the last divisor by the last remainder, until the division is exact. The final divisor is the sought g. c. d. of the two original positive integers. Find, by the Euclidean algorithm, the g. c. d. of 5913 and 7592. Find, by the Euclidean algorithm, the g. c. d. of 1827, 2523, and 3248. Prove that the Euclidean algorithm does lead to the g. c. d. Let h be the g. c. d. of the positive integers a and b. Show that there exist integers p and q (not necessarily positive) such that pa + qb = h. Find p and q for the integers of (a). Prove that a and b are relatively prime if and only if there exist integers p and q such that pa + qb = 1.Explanation / Answer
a) Set up a division problem where a is larger than b.
a ÷ b = c with remainder R. Do the division. Then replace a with b, replace b with R and repeat the division. Continue the process until R = 0.
7592 ÷ 5913 = 1 R 1679 (7592 = 1 × 5913 + 1679)
5913 ÷ 1679 = 3 R 876 (5913 = 3 × 1679 + 876)
1679 ÷ 876 = 1 R 803 (1679 = 1 × 876 + 803)
876 ÷ 803 = 1 R 73 (876 = 1 × 803 + 73)
803 ÷ 73 = 11 R 0 (803 = 11 × 73 + 0)
When remainder R = 0, the GCF is the divisor, b, in the last equation. GCF = 73
b) The factors of 1827 are: 1, 3, 7, 9, 21, 29, 63, 87, 203, 261, 609, 1827
The factors of 2523 are: 1, 3, 29, 87, 841, 2523
The factors of 3248 are: 1, 2, 4, 7, 8, 14, 16, 28, 29, 56, 58, 112, 116, 203, 232, 406, 464, 812, 1624, 3248
Then the greatest common factor is 29.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.