Find a particular integer solution to the linear equations:
(a) $156x + 18y= \gcd (156, 18)$
(b) $129x + 1011y= \gcd (129, 1011)$
(c) 703x + 111y= \gcd (703, 111)$
(d) $181x + 232y= \gcd (181, 232)$
We first notice the coefficients of these equations are the values from the previous exercise. We can therefore re-use the working there to develop solutions here.
(a) Applying the Division Algorithm to 156 and 18 gives
$ 156 = 8 (18) + 12 $
$ 18 = 1(12) + 6 = 1(12) + \gcd(156,18)$
Re-arranging,
$ 18 - 1(12) = \gcd(156,18) $
$ 18 - (156-8(18)) = \gcd(156,18) $
$ (9)(18) + (-1)156 = \gcd(156,18)$
So, a particular solution is $x=-1, y=9$.
(b) Applying the Division Algorithm to 1011 and 129 gives
$ 1011 = 7(129) + 108 $
$ 129 = 1(108) + 21 $
$ 108 = 5(21) + 3 = 5(21) + \gcd(1011,129) $
Re-arranging,
$ 108 - 5(21) = \gcd(1011,129) $
$ 108 - 5(129-1(108)) = \gcd(1011,129) $
$ (6)108 - 5(129) = \gcd(1011,129) $
$ (6)(1011-7(129)) - 5(129) = \gcd(1011,129) $
$ (6)(1011) - 47(129) = \gcd(1011,129) $
So, a particular solution is $x=-47, y=6$.
(c) We apply the Division Algorithm to 703 and 111.
$ 703 = 6(111) + 37 = 6(11) + \gcd(703,111)$
Re-arranging,
$ 703 - 6(111) - \gcd(703,111) $
So, a particular solution is $x=1, y=-6$.
(d) We apply the Division Algorithm to 232 and 181.
$ 232 = 1(181) + 51 $
$ 181 = 3(51) + 28 $
$ 51 = 1(28) + 23 $
$ 28 = 1(23) + 5 $
$ 23 = 4(5) + 3 $
$ 5 = 1(3) + 2 $
$ 3 = 1(2) + 1 = 1(2) + \gcd(232,181)$
Re-arranging
$ \gcd(232,181) = 3 - 1(2) $
$ \gcd(232,181) = 3 - (5-3) $
$ \gcd(232,181) = 2(3) - (5) $
$ \gcd(232,181) = 2(23-4(5)) - (5) = 2(23) - 9(5) $
$ \gcd(232,181) = 2(23) - 9(28-23) = 11(23) - 9(28) $
$ \gcd(232,181) = 11(51-28) - 9(28) = 11(51) - 20(28)$
$ \gcd(232,181) = 11(51) - 20(181-3(51)) = 71(51) -20(181)$
$ \gcd(232,181) = 71(232-181) -20(181) = 71(232) -91(181) $
So, a particular solution is $x=-91, y=71$.