1
$\begingroup$

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.

|cite|improve this question
$\endgroup$
2
$\begingroup$

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$

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Can you explain by giving a particular example? $\endgroup$ – vishal mishra Aug 20 '17 at 15:44
  • $\begingroup$ 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? $\endgroup$ – vishal mishra Aug 22 '17 at 8:29

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.