Finding all solutions for diophantine equations

Printable View

October 21st 2010, 08:37 AM
archon

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!
October 24th 2010, 03:07 AM
HappyJoe

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$ .
October 24th 2010, 05:28 AM
archon

Wow that's so simple. Thanks! So when A and B are coprime that simply becomes: (x + nb, y- na)
October 24th 2010, 03:27 PM
Bruno J.

Quote:

Originally Posted by archon

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? (Giggle)
October 25th 2010, 05:33 AM
HallsofIvy

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.)