Thread: Problem dealing with Euclidean Algorithm/gcd

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

2. 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 $\displaystyle (x,y)$. Suppose that there's another solution $\displaystyle (x+k,y-j)$. Then
$\displaystyle a(x+k)+b(y-j)=d\Rightarrow ax+by=d+(bj-ak)$, so $\displaystyle bj=ak$.
Now $\displaystyle b=\overline{b}d$ and $\displaystyle a=\overline{a}d$ for some $\displaystyle \overline{b},\overline{a}\in\mathbb{Z}$, which upon substitution and cancellation leads to $\displaystyle \overline{b}j=\overline{a}k$.

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