Show that 34 and 15 are relatively prime numbers by factoringeach as a product o

Question

Show that 34 and 15 are relatively prime numbers by factoringeach as a product of prime numbers and by arguing based on theprime factors. To verify your result use the Extended Euclidalgorithm to find the gcd (34,15). Show how the algorithm executesfor this problem. These two numbers are relatively prime is based on what valuecalculated by the Extended Euclid algorithm? Show that 34 and 15 are relatively prime numbers by factoringeach as a product of prime numbers and by arguing based on theprime factors. To verify your result use the Extended Euclidalgorithm to find the gcd (34,15). Show how the algorithm executesfor this problem. These two numbers are relatively prime is based on what valuecalculated by the Extended Euclid algorithm? These two numbers are relatively prime is based on what valuecalculated by the Extended Euclid algorithm?

Explanation / Answer

a) 34 = 1 *2 * 17 15 = 1 * 3 * 5 As 34, 15 have no common factor other than 1...they are said to berelative prime numbers. b)Euclid algorithm GCD(34, 15) = GCD(15, 34 mod 15)                       = GCD(15, 4) [as 34 mod 15 = 4, where mod is the remainder operator]                      = GCD(4, 15 mod4)                         = GCD(4, 3)                         = GCD(3, 4mod3)                         =GCD(3,1)                           =GCD(1, 3mod1)                            =GCD(1,0)                             = 1 As the GCD of 34, 15 is 1..they are said to be relative primenumbers

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.