Find all pairs of positive integers $(x, y)$ for which $261x + 48y = 7881$

Question

How do you use the Euclidean Algorithm to solve the following: Find all pairs of positive integers $(x, y)$ for which $261x + 48y = 7881$

Answer 1

Euclidean algorithm:

$261=5\times48+21$

$48=2\times21+6$

$\color{blue}{21}=3\times6+3$

so $\color{blue}{(261-5\times48)}=3\times(48 - 2\color{blue}{(261-5\times48)})+3;$

i.e., $7\times261-38\times48=3.$

Therefore, $2627\times7\times261-2627\times38\times48=3\times2627=7881;$

i.e., $18389\times261-99826\times48=7881.$

More generally $(18389-16k)\times261+(87k-99826)\times48=7881.$

$18389-16k>0$ and $87k-99826 > 0$ were requested.

Thus $k < 1149.3125$ and $k > 1147.4...$; i.e., $k = 1148$ or $1149.$

Solutions are therefore $21\times261+50\times48=7881$ and $5\times261+137\times48=7881.$