Post a New Question

Math

posted by .

Find the smallest positive integer d such that d=105m+216n, where m & n are integers.

  • Math -

    Compute the GCD of 105 and 216 using thr Euclidean algorithm. A linear combination of 105 and 216 of the form

    a 105 + b 216

    can be reprented by the vector:

    (a, b, a 105 + b 216)

    We start with the two vectors:

    v1 = (105, 0, 105)

    v2 = (0,216, 216)

    The integer part of 216/105 is 2.

    v2 - 2 v1 = (-210, 216, 6)

    We now define the new v2 to be the old v1 while the above vector becomes the new v1:

    v1 = (-210, 216, 6)

    v2 = (105, 0, 105)

    We now repeat the previus step.

    Integer part of 105/6 is 17.

    v2 - 17 v1 = (3675, -3672, 3)

    If you then would run another step, you would end up with a last component of zero, this means that the GCD is 3 and you have:

    3 = 3675*105 - 3672*216

    You can then add that last vector with zero last component to make the integers m and n positive.

Answer This Question

First Name
School Subject
Your Answer

Related Questions

More Related Questions

Post a New Question