Integral Solutions in Diophantine Equation

Question

How do you solve this problem:

Describe the integral solutions to the equation $317a + 241b = 9.$

I know the answer is

$(a, b) = (35 + 241k, −46 − 317k)$ for integers k

but I don't know how to get to it.

Answer 1

This is a typical Euclidean Algorithm problem for expressing GCD as a linear combination.

Hint

First use Euclid's algorithm to find $p,q \in \mathbb{Z}$ such that $$317p+241q=\gcd(317,241)=1.$$ Once you get $p,q$, then you can get all the solutions by a simple observation: for any $k \in \mathbb{Z}$, $$317(p\color{red}{+ 241k})+241(q\color{red}{-317k})=\gcd(317,241)=1.$$

Now you can express any integer $n$ as a linear combination by $$317\underbrace{\color{green}{n}(p+\color{red}{241k})}_{a}+241\underbrace{\color{green}{n}(q\color{red}{-317k})}_{b}=\color{green}{n}.$$

Answer 2

With any particular solution $(a_0,b_0)$ you have $\begin{cases}317a+241b=9\\317a_0+241b_0=9\end{cases}$

It follows $317(a-a_0)+241(b-b_0)=0$ so making $(a-a_0)=241k$ and $(b-b_0)=317k$

you have the solutions $(a,b)=(a_0+241k,b_0+317k)$

The solution you mention is not the only one in its explicit form and your couple $(35,-46)$ can be replaced by any other particular solution; for example you can take $(a_0,b_0)=(-206,271)$ or $(-447,588)$ or any other solution.