Perform the Euclidean Algorithm on given pairs of numbers


For each of the following pairs of integers a and b, determine their greatest common divisor and their least common multiple, and write their greatest common divisor in the form ax + by for some integers x and y.
  • a = 20 and b = 13.
    • To find the greatest common divisor, we apply the Euclidean algorithm as follows.
      20 = (1)13 + 7
      13 = (1)7 + 6
      7 = (1)6 + 1
      6 = (6)1 + 0.
      Hence \mathsf{gcd}(20,13) = 1.
    • To find the least common multiple, recall that for all integers a and b, \mathsf{gcd}(a,b) \cdot \mathsf{lcm}(a.b) = a \cdot b. In particular, \mathsf{lcm}(20,13) = (20 \cdot 13)/\mathsf{gcd}(20,13) = 260.
    • “Reversing” the Euclidean algorithm, we have
      1 = 7 – 6
       = 20 – 2(13) + 7
       = 2(20) – 3(13).
  • a = 69 and b = 372.
    • We apply the Euclidean algorithm to find the greatest common divisor as follows.
      372 = (5)69 + 27
      69 = (2)27 + 15
      27 = (1)15 + 12
      15 = (1)12 + 3
      12 = (4)3 + 0.
      Hence \mathsf{gcd}(372,69) = 3.
    • We have \mathsf{lcm}(372,69) = (372 \cdot 69)/\mathsf{gcd}(372,69) = 8556.
    • Reversing the Euclidean algorithm, we have
      3 = 15-12
       = 69 – 3(27) + 15
       = 17(69) – 3(372) – 2(27)
       = 27(69) – 5(372)
  • a = 792 and b = 275.
    • We apply the Euclidean algorithm to find the greatest common divisor as follows.
      792 = (2)275 + 242
      275 = (1)242 + 33
      242 = (7)33 + 11
      33 = (3)11 + 0
      Hence \mathsf{gcd}(792,275) = 11.
    • We have
      \mathsf{lcm}(792,275) = (792 \cdot 295)/\mathsf{gcd}(792,275) = 19800.
    • Reversing the Euclidean algorithm as before gives
      11 = 8(792) - 23(275).
  • a = 11391 and b = 5673.
    • We apply the Euclidean algorithm to find the greatest common divisor as follows.
      11391 = (2)5673 + 45
      5673 = (126)45 + 3
      45 = (15)3 + 0
      Hence \mathsf{gcd}(11391,5673) = 3.
    • As before, \mathsf{lcm}(11391,5673) = 21540381.
    • Reversing the Euclidean algorithm as before gives
      3 = 253(5673) - 126(11391).
  • a = 1761 and b = 1567.
    • We apply the Euclidean algorithm to find the greatest common divisor as follows.
      1761 = (1)1567 + 194
      1567 = (8)194 + 15
      194 = (12)15 + 14
      15 = (1)14 + 1
      14 = (14)1 + 0
      Hence \mathsf{gcd}(1761,1567) = 1.
    • As before, \mathsf{lcm}(1761,1567) = 2759487.
    • Reversing the Euclidean algorithm as before gives
      1 = 118(1567) - 105(1761).
  • a = 507885 and b = 60808.
    • We apply the Euclidean algorithm to find the greatest common divisor as follows.
      507885 = (8)60808 + 21421
      60808 = (2)21421 + 17966
      21421 = (1)17966 + 3455
      17966 = (5)3455 + 691
      3455 = (5)691 + 0
      Hence \mathsf{gcd}(507885,60808) = 691.
    • As before, \mathsf{lcm}(507885,60808) = 44693880.
    • Reversing the Euclidean algorithm gives
      691 = 142(60808) - 17(507885).





Posted by
Labels: , , , ,

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)