Results 1 to 2 of 2

Thread: Problem dealing with Euclidean Algorithm/gcd

  1. #1
    Member
    Joined
    Nov 2009
    Posts
    79

    Question 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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Jan 2011
    Posts
    71
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Sep 30th 2010, 10:46 AM
  2. Euclidean Algorithm Problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Oct 15th 2009, 07:52 AM
  3. Euclidean algorithm
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Aug 8th 2009, 08:28 AM
  4. Replies: 1
    Last Post: Jun 23rd 2009, 05:44 AM
  5. Euclidean algorithm gcd lcm help..
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Aug 10th 2006, 05:46 AM

Search Tags


/mathhelpforum @mathhelpforum