# Problem dealing with Euclidean Algorithm/gcd

• Feb 10th 2011, 07:35 PM
steph3824
Problem dealing with Euclidean Algorithm/gcd
Let a=2,655,271 and b=1,836,253.

I used the Euclidean Algorithm and found that d=gcd(a,b)=523. I also found that, for ax+by=d, x=-1334 and y=1929. The next problem is what I need help with. It says to find all solutions in integers to ax+by=d. I have no idea what to do! Help please
• Feb 10th 2011, 08:56 PM
LoblawsLawBlog
There's a general formula for equations like these. I'll get you started and leave some details to fill in (like making sure you get every solution).

We already know one solution $(x,y)$. Suppose that there's another solution $(x+k,y-j)$. Then
$a(x+k)+b(y-j)=d\Rightarrow ax+by=d+(bj-ak)$, so $bj=ak$.
Now $b=\overline{b}d$ and $a=\overline{a}d$ for some $\overline{b},\overline{a}\in\mathbb{Z}$, which upon substitution and cancellation leads to $\overline{b}j=\overline{a}k$.

Now when will a multiple of $\overline{b}$ equal a multiple of $\overline{a}$? Think of their gcd.