1. GCD(19,14)
    19 = 14*1+5
    r -> 5 = 19-1*14

    GCD(14,5)
    14 = 5*2+4
    r -> 4 = 14 - 2*5 = 14 - 2(19-4*1) = 14 - 2*19 + 1*14 = 3*14-2*19

    GCD(5,4)
    5 = 1*4 + 1
    r -> 1 = 5 - 1(4) = (19 - 1*14) - (3*14-2*19) = 3*19-4*14

    Thus you would give the casheere 3 19$ coins and they would give you back
    4 14$ coins

2.
    GCD(109, 95)
    109 = 95*1 + 14
    r -> 14 = 109 - 1*95

    GCD(95, 14)
    95 = 14*6 + 11
    r -> 11 = 95 - 6(14) = 95 - 6(109 - 1*95) = 7*95 - 6*109

    GCD(14, 11)
    14 = 11*1 + 3
    r -> 3 = 14 - 1(11) = 109 - 1*95 - (7*95 - 6*109) = 7*109 - 8*95

    GCD(11, 3)
    11 = 3*3 + 2
    r -> 2 = 11 - 3(3) = 7*95 - 6*109 - 3(7*109 - 8*95)
    = 31*95 - 27*109

    GCD(3,2)
    3 = 2*1 + 1
    1 = 3 - 1*2 = 7*109 - 8*95 - (31*95 - 27*109) = 34*109 - 39*95

    Thus the you give 34 109$ coins and you get back 39 95$ coins

3.
    GCD(37, 16)
    37 = 2*16 + 5
    r -> 5 = 37 - 2*16

    GCD(16, 5)
    16 = 5*3 + 1
    r -> 1 = 16 - 3(37 - 2*16) = 7*16 - 3*37

    Thus you use 7 16 lb weights on one side and 3 37 lb weights on the other +
    1 lb of coffee  and they should balance out

4.
    Im not sure how to approach the problem!