Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Least one solution of ax+by=c

  1. Feb 7, 2010 #1
    I was wondering if someone could help me with a proof.

    If ab<0 (can we assume that either a or b is negative then?) and d(gcd of a and b)│c, there there is at least one solution of ax+by=c with x and y positive.
     
  2. jcsd
  3. Feb 9, 2010 #2
    Re: Diophantine

    I haven't read it yet but https://www.physicsforums.com/showthread.php?t=367945", is most certainly relevant to your question.

    Here is my attempt, which to be honest is a complete overkill since it resorts to a more advanced theorem!:), but it was pretty much the first thing that came into my head.

    First we note that if we have one solution to the equation, say (x,y), then (x+nb, y+na) is also a solution. Therefore if we can find one solution, we can always, from this solution, construct another solution for which both coordinates are positive.

    With the aim of finding a single solution, we note that it is clear that the problem is equivalent to (where I have redefined the meaning of the variables a,b,c):

    [tex]
    ax - by = c
    [/tex]

    For a>0, b>0, and where a and b are coprime [I have divided both sides of the equation by the gcd(a,b), and then redefined the variables (e.g. c now represents the result of this division on the rhs etc..likewise for a,b)].

    It is also clear that if we can find a solution to the equation :

    [tex]
    ax - by = 1
    [/tex]

    (where a>0, b>0, and where a and b are coprime), then we can immediately find a solution to the equation above (simply by multiplying both sides of the equation by c).

    We proceed by noting that from a "[URL [Broken] of fermat's little theorem[/URL], and given the coprimality of a and b :

    [tex]
    \exists\ p\ s.t.\ a^p = 1 (mod\ b)
    [/tex]

    In particular p is given by http://en.wikipedia.org/wiki/Euler%27s_totient_function" [Broken] : [tex]p=\phi(b)[/tex]. Therefore :

    [tex]
    a^p = Nb + 1\ for\ some\ integer\ N
    [/tex]

    So that

    [tex]
    a^p - N b = 1
    [/tex]

    Therefore the solution to :

    [tex]
    ax - by = 1
    [/tex]

    (where a>0, b>0, and where a and b are coprime) is given by :

    [tex]
    (x,y) = (a^{p-1}, N)
    [/tex]

    where x, y are both integers, and therefore we have achieved the desired result
     
    Last edited by a moderator: May 4, 2017
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Least one solution of ax+by=c
  1. Least-squares solution (Replies: 1)

  2. Ax+by=c => gcd(a,b)|c ? (Replies: 13)

  3. Least Square Solution (Replies: 2)

Loading...