# Diophantine Equation extended

I just started with number theory and encountered Euclid ' Algorithm to find greatest common divisor. Also I understand that greatest common divisor of two integers can be expressed as linear combination of two. I was just wondering if same could be done for greatest common divisor of three integers and I can prove that $gcd(a,b,c) = ax +by +cz$ where $x,y,z$ are integers. Naturally arises the question how to find solutions of diophantine Equation :

$ax +by +cz = td$ where$d$ is gcd of $a,b,c$ and $t$ is integer. Firstly it is difficult to find even a single solution to this and if in case by hit and trial I get a solution say $(x',y',z')$ then how can find all solution parametrized in terms of the known solution.

## 1 Answer

You can do it in stages. Let $q=\gcd(a,b)$ and express $q=x'a+y'b$. Now $d=\gcd(q,c)$, solve $x''q+y''c=td$ and plug in the expression you have for $q$

Added: as an example, take $a=6, b=10, c=15.$ the GCD of all three is $1$, but the GCD of any pair is higher. $q=\gcd(a,b)=2$ and we can find $2=2\cdot 6-1\cdot 10.$ Now $d=\gcd(2,15)=1$ and we find $1=8 \cdot 2-1\cdot 15=8(2\cdot 6-1\cdot 10)=16\cdot 6-8\cdot 10-1\cdot 15$

• Can you explain by giving a particular example? – vishal mishra Aug 20 '17 at 15:44
• Alright but how generalize all the solutions in terms of one obtained it is easily possible in case where c is 0. Is it not possible in this case? – vishal mishra Aug 22 '17 at 8:29