Results 1 to 5 of 5

Math Help - Finding all solutions for diophantine equations

  1. #1
    Newbie
    Joined
    Oct 2010
    Posts
    9

    Finding all solutions for diophantine equations

    Hi, this is my first post here. I'm taking a discrete mathematics course in University and it's kicking my ass. I'm not good at math and the professor barely speaks english, not a good combination. So this is probably the first of many questions I'll be asking here. I hope that you'll be patient with me as long as I show that I really am trying to learn this stuff.

    How do you find all solutions for a diophantine equation? Currently I only know how to find a single solution, and after that it gets a little fuzzy.

    This is what I know:
    1)find gcd(a,b) *using Euclidean Algorithm
    2)Use extended/reverse Euclidean Algorithm to solve for x and y
    3)?....

    Thanks for your help!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member HappyJoe's Avatar
    Joined
    Sep 2010
    From
    Denmark
    Posts
    234
    It appears you are dealing with a linear Diophantine equation in two variables x and y.

    The third step involves using the one solution (x,y) that you already have to generate all of the solutions. To be specific, given the solution (x,y), all other solutions are given by

    (x+\frac{nb}{\gcd(a,b)} , y - \frac{na}{\gcd(a,b)}),

    where n\in\mathbb{Z}. This means that for any choice of integer n, the above pair gives you a solution to your equation, and vice versa, any solution to your equation is of the above form for some n.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2010
    Posts
    9
    Wow that's so simple. Thanks! So when A and B are coprime that simply becomes: (x + nb, y- na)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by archon View Post
    Hi, this is my first post here. I'm taking a discrete mathematics course in University and it's kicking my ass. I'm not good at math and the professor barely speaks english, not a good combination. So this is probably the first of many questions I'll be asking here. I hope that you'll be patient with me as long as I show that I really am trying to learn this stuff.
    Pun intended?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Apr 2005
    Posts
    14,973
    Thanks
    1121
    Exactly. That way a(x+ nb)+ b(y- na)= ax+ by+ anb- bna= ax+ by.

    (If a and b are NOT coprime, say gcd(a, b)= n so that a= pn and b= qn, then, for the equation ax+ by= c, either
    1) the greatest common divisor of a and b divides c: ax+ by= pnx+ qny= un so we can divide through by n and have px+ qy= u with p and q coprime or

    2) ax+ by= pnx+ qny= n(px+ qy)= c. Now the left side is a multiple of n while the right is not. That's impossible so there is no solution.

    That is, we can always assume that, perhaps after simplifying, that the coefficients are coprime.)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Finding all solutions to Trig Equations
    Posted in the Trigonometry Forum
    Replies: 10
    Last Post: April 18th 2011, 01:43 PM
  2. Finding approximate solutions to equations
    Posted in the Trigonometry Forum
    Replies: 1
    Last Post: January 17th 2010, 07:07 AM
  3. Solutions to this diophantine equation.
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 25th 2008, 01:19 PM
  4. Replies: 2
    Last Post: March 5th 2008, 05:46 PM
  5. Finding all solutions to a Diophantine equation
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 10th 2006, 01:10 PM

Search Tags


/mathhelpforum @mathhelpforum