Show that the solution for $ , $ is not unique

Question

Compute $ = \gcd (402,147)$ and find integers $, $ such that $ = 402 + 147$. Show that the solution for $, $ is not unique; that is, find a different pair of integers $, $ that also satisfies the required condition.

I found the $\gcd =3$ and $r=15, s=-41$

I don't know how to find the other pair of integers. Please help

Answer 1

Note that $LCM(402,147)=\frac{402 \times 147}{GCD(402,147)} = 19698$

This, of course, means that 19698 is divisible by both 402 and 147. In fact, $19698=402 \times 49$ and $19698=147 \times 134$

Because any multiples of $19698$ will also be multiples of both $402$ and $147$, you could add and subtract such multiples.

For example, you have found that $15 \times 402 - 41 \times 147 = 3$, so we could just rewrite this as: $$15 \times 402 + 1968 - 1968 - 41 \times 147 = 3$$ Then, you have: $$15\times 402 + 49 \times 402 - 134 \times 147 -41 \times 147 =3$$ $$ 64 \times 402 -175 \times 147 = 3$$ You could do similarly with any multiple of 19698 - add it and subtract it. Note: a second, distinct solution should be sufficient to demonstrate that the solution is not unique, but what we have shown here is that this will work for any integers n such that: $$(15+49n) \times 402 + (-41-134n) \times 147 = 3$$

Answer 2

Note that if $402a+147b=402f+147g=d$ then $402(a-f)=147(g-b)$, which is the condition you need to satisfy to find any additional solution.

Answer 3

Once you have a particular solution, $(x,y)$, all others are of the form $(x+ku,y-kv)$ where $u=\frac b{\gcd (a,b)}$ and $v=\frac a{\gcd (a,b)}$.

So, $(15+49 ,-41-134)=(64,-175)$, for instance, would be another solution.