Please do 5.2 part (a) 5.1 The Euclidean Algorithm The Euclidean algorithm, or p
ID: 3210379 • Letter: P
Question
Please do 5.2 part (a)
5.1 The Euclidean Algorithm 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 de- velopments 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 + ab 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 5.2 Applications of the Euclidean Algorithm (a) Prove, using Problem Study 5.l(f), that if p is a prime and divides the product u, then either p divides u or p divides v.Explanation / Answer
5.2 a) Given p is a prime and p divides uv.
Suppose p does not divide u then u and p are relatively prime since p is a prime thus by 5.1 if there exists integers x,y such that
px+uy=1
multiplying by v on both sides we get
pxv+uvy=v
p|pvx and p|uvy thus p|(pvx+uvy) i.e. p|v