Problem dealing with Euclidean Algorithm/gcd

**steph3824** · February 10th 2011, 06:35 PM

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

**LoblawsLawBlog** · February 10th 2011, 07:56 PM

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.

Thread: Problem dealing with Euclidean Algorithm/gcd

LinkBack

Thread Tools

Display

Problem dealing with Euclidean Algorithm/gcd

Similar Math Help Forum Discussions

Euclidean Algorithm

Euclidean Algorithm Problem

Euclidean algorithm

Problem - highest common factor, Euclidean Algorithm

Euclidean algorithm gcd lcm help..

Search Tags