# Integral Solutions in Diophantine Equation

How do you solve this problem:

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

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

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

• Whenever you see linear diophantine equations, think of gcd and Bézout. – dohmatob Jan 24 '16 at 15:31

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}.$$

• How would you use Euclid's Algorithm to find p and q? – Ayush Jan 23 '16 at 22:28
• @Ayush please click on the link in my answer (Euclidean Algorithm) – Anurag A Jan 24 '16 at 12:02
• The link doesn't actually explain how to find the p and q. "working upward through the equations" doesn't actually say anything about which values to take for p and q. – Sunspawn Jun 10 '19 at 15:33

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.