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.

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

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


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

  • $\begingroup$ How would you use Euclid's Algorithm to find p and q? $\endgroup$ – Ayush Jan 23 '16 at 22:28
  • $\begingroup$ @Ayush please click on the link in my answer (Euclidean Algorithm) $\endgroup$ – Anurag A Jan 24 '16 at 12:02
  • $\begingroup$ 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. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.