Question
e please!
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. (a) Find, by the Euclidean algorithm, the g.c.d. of 5913 and 7592. b) Find, by the Euclidean algorithm, the g.c.d. of 1827, 2523, and 3248. (c) Prove that the Euclidean algorithm does lead to the g.c.d. (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. (e) Find p and q for the integers of (a). (f) 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
In (a) the numbers given are 5913 and 7592. (d) states that there exist integers p and q such that
pa + qb = h.
=> 5913p + 7592q = gcd(5913,7592) = 73.
To determine p and q, we shall revisit Euclid's algorithm in the following way:
7592 = 5913*1 + 1679 (1)
5913 = 1679*3 + 876 (2)
1679 = 876*1 + 803 (3)
876 = 803*1 + 73 (4)
Proceeding in the reverse direction
=> 73 = 876 - 803*1
=> 73 = 876 - (1679 - 876*1)
=> 73 = (5913 - 1679*3) - (1679 - [(5913 - 1679*3)*1])
=> 73 = (5913 - [(7592 - 5913*1)*3]) - ((7592 - 5913*1) - [(5913 - [(7592 - 5913*1)*3]*1)]
=>73 = 9*5913 - 7*7592
=> p =9 and q=-7
