# Finding all solutions for diophantine equations

• Oct 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)?....

• Oct 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$.
• Oct 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)
• Oct 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)
• Oct 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.)