Results 1 to 2 of 2

Math Help - 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 (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.
    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: September 30th 2010, 11:46 AM
  2. Euclidean Algorithm Problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 15th 2009, 08:52 AM
  3. Euclidean algorithm
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: August 8th 2009, 09:28 AM
  4. Replies: 1
    Last Post: June 23rd 2009, 06:44 AM
  5. Euclidean algorithm gcd lcm help..
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 10th 2006, 06:46 AM

Search Tags


/mathhelpforum @mathhelpforum