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.

$\endgroup$
1

1 Answer 1

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$

$\endgroup$
2
  • $\begingroup$ Can you explain by giving a particular example? $\endgroup$ Aug 20, 2017 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$ Aug 22, 2017 at 8:29

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .