# 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.

• The extended Euclidean algorithm still works for 3 or more integers, e.g. see this answer or this answer. Aug 20, 2017 at 15:07

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$