Diophantine Equations

Definition: A diophantine equation is an equation of the form Ax^2 + Bxy + Cy^2 + Dx + Ey + F = 0 together with its whole number solutions, that is the set of solutions (x,y) \in Z \times Z

Example: The equation 4y^2 - 20y + 25 = 0 has the solution \{ (x,y)|y = 2.5 \} , but 2.5 is not an integer so this diophantine equation has no solution.

Solution methods depend on the values of A, B and C. These values also determine the type of curve in the real plane R \times R so we categorize the solution methods in this way: linear, simple hyperbolic, eliptical, parabolic and (standard) hyperbolic. Of course, we are only interested in finding the isolated integer valued points where the respective curve intersects with the 1-1 grid.

Cases:

Linear case: A = B = C = 0 .
Simple hyperbolic case: A = C = 0 ; B \ne 0 .
Eliptical case: B^2 - 4AC < 0 .
Parabolic case: B^2 - 4AC = 0 .
Hyperbolic case: B^2 - 4AC > 0 .

Linear diophantine equations Dx + Ey + F = 0 - Graphical solution

Linear diophantine equations: Dx + Ey + F = 0 -Algebraic solution

There are several subcases:

1. D = 0 and E = 0 means we have F=0 . This has a solution if only if F is 0.

So such a diophantine equation has a solution only if it is: 0=0 .

The diophantine equation: 0=0 has infinitely many solutions, namely every grid point: M= \{(x,y), x,y \in Z \} .

2. D = 0 and E \ne 0 means we have Ey + F = 0 => y = -F/E . This has a solution if and only if E is a factor of F.

So such a diophantine equation has a solution only if it is: Ey-eE=0, e \in Z .

The diophantine equation: Ey-eE=0 has infinitely many solutions, namely every grid point along the horizontal line y=e or M= \{(x,e), x \in Z \}.

3. D \ne 0 and E=0 means we have Dx + F = 0 => x = -F/D . This has a solution if and only if D is a factor of F.

So such a diophantine equation has a solution only if it is: Dx-dD=0, e \in Z .

The diophantine equation: Dx-dD=0 has infinitely many solutions, namely every grid point along the vertical line x=d or M= \{(d,y), y \in Z \}.

4. D \ne 0 and E \ne 0 means we have Dx + Ey + F = 0 .

Let g = GCD(D, E) . This means g is a factor of D and a factor of E.

So such a diophantine equation has a solution only if g is a factor of F. Let \color{red}{d}=D/g, \color{green}{e}=E/g, \color{magenta}{f}=F/g \in Z.

The diaphantine equation reduces to:

\color{red}{d}x + \color{green}{e}y = \color{magenta}{-f} , where GCD(\color{red}{d},\color{green}{e})=1 .

Now we use Euler's method to find integers \color{teal}{u'} and \color{purple}{v'} such that \color{red}{d}\color{teal}{u'}+\color{green}{e} \color{purple}{v'} = 1 .

Multiply this last equation by ( \color{magenta}{-f}) to get \color{red}{d}(\color{magenta}{-f}) \cdot \color{teal}{u'} +\color{green}{e}(\color{magenta}{-f}) \cdot \color{purple}{v'} = \color{magenta}{-f}

So one solution is: (\color{magenta}{-f} \cdot \color{teal}{u'},\color{magenta}{-f} \cdot \color{purple}{v'})

To find all possible solutions, to the last equation we add: 0= \color{red}{d}\color{green}{e} \cdot k -\color{red}{d}\color{green}{e} \cdot k where k \in Z .

We reorganize this equation to get:

\color{red}{d} (\color{magenta}{-f} \cdot \color{teal}{u'}+\color{green}{e} \cdot k ) + \color{green}{e} (\color{magenta}{-f} \cdot \color{purple}{v'}-\color{red}{d} \cdot k )= \color{magenta}{-f}

Answer The solution set to the diophantine equation is: M= \{(x,y)= (\color{magenta}{-f} \cdot \color{teal}{u'}+\color{green}{e} \cdot k ,\color{magenta}{-f} \cdot \color{purple}{v'}-\color{red}{d} \cdot k ), k \in Z \}

Example 1

Example: Solve the diophantine equation: 6x+34y=4 .

This means D=6 , E=34 and F=-4 .

g= GCD(6,34)=2 and -4 is divisible by 2 so the equation has solution(s).

We divide the equation by g=2: \color{red}{3}x+\color{green}{17}y=\color{magenta}{2} .

Now we are ready to apply Euler's Algorithm.

Step	q Quotient	r Remainder	Substitution	Result
1		\color{green}{17}		\color{green}{17}=\color{green}{17} \cdot 1 + \color{red}{3} \cdot 0
2		\color{red}{3}		\color{red}{3}= \color{green}{17} \cdot 0 + \color{red}{3} \cdot 1
3	\color{purple}{5}	\color{teal}{2}=\color{green}{17}-\color{red}{3} \cdot \color{purple}{5}	\color{teal}{2}=(\color{green}{17} \cdot 1 + \color{red}{3} \cdot 0 \cdot 1) -(\color{green}{17} \cdot 0 + \color{red}{3} \cdot 1) \cdot \color{purple}{5}	\color{teal}{2}=\color{green}{17} \cdot 1 + \color{red}{3} \cdot (-5)
4	\color{blue}{1}	\color{magenta}{1}=\color{red}{3}-\color{teal}{2} \cdot \color{blue}{1}	\color{magenta}{1}=\color{green}{17} \cdot 0 + \color{red}{3} \cdot 1 -(\color{green}{17} \cdot 1 + \color{red}{3} \cdot (-5)) \cdot \color{blue}{1}	\color{magenta}{1}=\color{green}{17} \cdot (-1) + \color{red}{3} \cdot (6)

We have: \color{magenta}{1}=\color{green}{17} \cdot (-1) + \color{red}{3} \cdot (6) . So \color{teal}{u'}=\color{teal}{6} and \color{purple}{v'}=-1 .

This means: \color{red}{3} \cdot (\color{teal}{6})+\color{green}{17} \cdot (\color{purple}{-1}) =\color{magenta}{1} .

In order to get the desired equation, we multiply this last by -f=2 :

\color{red}{3} \cdot \color{teal}{(6 \cdot 2)}+\color{green}{17} \cdot \color{purple}{(-1\cdot 2)} =\color{magenta}{1 \cdot 2} or \color{red}{3} \cdot \color{teal}{(12)}+\color{green}{17} \cdot \color{purple}{(-2)} =\color{magenta}{2} .

Answer: The solution of the diophantine equation \color{red}{3}x+\color{green}{17}y=2 is

М= \{(x,y)=(\color{teal}{12}+\color{green}{17}k,\color{purple}{-2}-\color{red}{3}k),k \in Z \}

Example 2

Example: Solve the diophantine equation: \color{red}{27}x+\color{green}{59}y=\color{magenta}{210} .

So D=27 , E=59 and F=-210 .

g= GCD(27,59)=1 so we go directly to Euler's Algorithm.

Step	q Quotient	r Remainder	Substitution	Result
1		\color{green}{59}		\color{green}{59}=\color{green}{59} \cdot 1 + \color{red}{27} \cdot 0
2		\color{red}{27}		\color{red}{27}= \color{green}{59} \cdot 0 + \color{red}{27} \cdot 1
3	\color{purple}{2}	\color{teal}{5}=\color{green}{59}-\color{red}{27} \cdot \color{purple}{2}	\color{teal}{5}=(\color{green}{59} \cdot 1 + \color{red}{27} \cdot 0 ) -(\color{green}{59} \cdot 0 + \color{red}{27} \cdot 1) \cdot \color{purple}{2}	\color{teal}{5}=\color{green}{59} \cdot 1 + \color{red}{27} \cdot (-2)
4	\color{blue}{5}	\color{darkyellow}{2}=\color{red}{27}-\color{teal}{5} \cdot \color{blue}{5}	\color{darkyellow}{2}=\color{green}{59} \cdot 0 + \color{red}{27} \cdot 1 -(\color{green}{59} \cdot 1 + \color{red}{27} \cdot (-2)) \cdot \color{blue}{5}	\color{darkyellow}{2}=\color{green}{59} \cdot (-5) + \color{red}{27} \cdot (11)
5	\color{darkgreen}{2}	\color{magenta}{1}=\color{teal}{5}-\color{darkyellow}{2} \cdot \color{darkgreen}{2}	\color{magenta}{1}=(\color{green}{59} \cdot 1 + \color{red}{27} \cdot (-2))-(\color{green}{59} \cdot (-5) + \color{red}{27} \cdot (11)) \cdot \color{darkgreen}{2}	\color{magenta}{1}=\color{green}{59} \cdot (11) + \color{red}{27} \cdot (-24)

We have: \color{magenta}{1}=\color{green}{59} \cdot (11) + \color{red}{27} \cdot (-24) . So \color{teal}{u'}=\color{teal}{-24} and \color{purple}{v'}=\color{purple}{11} .

This means: \color{red}{27} \cdot (\color{teal}{-24})+\color{green}{59} \cdot (\color{purple}{11}) =\color{magenta}{1} .

In order to get the desired equation, we multiply this last by -F=210 :

\color{red}{27} \cdot \color{teal}{(-24 \cdot 210)}+\color{green}{59} \cdot \color{purple}{(11\cdot 210)} =\color{magenta}{1 \cdot 210} or \color{red}{27} \cdot \color{teal}{(-5040)}+\color{green}{59} \cdot \color{purple}{(2310)} =\color{magenta}{210} .

Answer: The solution of the diophantine equation \color{red}{27}x+\color{green}{59}y=210 is

М= \{(x,y)=(\color{teal}{-5040}+\color{green}{59}k,\color{purple}{2310}-\color{red}{27}k),k \in Z \}

Simple hyperbolic diophantine equation: Bxy + Dx + Ey + F = 0 - Graphical solution

Simple hyperbolic diophantine equation: Bxy + Dx + Ey + F = 0 - Algebraic solution

Step 1 - Multiply through by B: B^2xy + BDx + BEy + BF = 0

Step 2 - Factor: (Bx+E)(By+D) = DE - BF

There are two subcases

1. If DE - BF \ne 0 we find the factors of DE - BF and solve (see Example 1 below).

2. If DE - BF = 0 ... (under construction)

Example 1

Example: Solve the diophantine equation \color{red}{5}y-\color{green}{5}x=xy .

Here \color{magenta}{1}xy+\color{red}{5}x-\color{green}{5}y=0 . So B=\color{magenta}{1} , D=\color{red}{-5} , E=\color{green}{5} and F=0 .

\color{magenta}{1}xy +\color{red}{5}x-\color{green}{5}y=0

\color{magenta}{1}^2xy+ \color{magenta}{1} \cdot \color{red}{5}x-\color{magenta}{1} \cdot \color{green}{5}y=\color{magenta}{1} \cdot 0

(\color{magenta}{1}x- \color{green}{5})(\color{magenta}{1}y+ \color{red}{5})=\color{red}{5} \cdot (\color{green}{-5})+\color{magenta}{1} \cdot 0

(x- \color{green}{5})(y+ \color{red}{5})= \color{teal}{-25}

\color{teal}{-25} has 6 integer factors, namely \pm1, \, \pm 5 \, и \, \pm 25 . So there are 6 solution points.

Solution 1: (x- \color{red}{5})=1 и (y+ \color{green}{5})= -25 oдносно x=6 и y=-30 или (6,-30).

Solution 2: (x- \color{red}{5})=5 и (y+ \color{green}{5})= -5 oдносно x=10 и y=-10 или (10,-10).

Solution 3: (x- \color{red}{5})=25 и (y+ \color{green}{5})= -1 oдносно x=30 и y=-6 или (30,-6).

Solution 4: (x- \color{red}{5})=-1 и (y+ \color{green}{5})= 25 oдносно x=4 и y=20 или (4,20).

Solution 5: (x- \color{red}{5})=-5 и (y+ \color{green}{5})= 5 oдносно x=0 и y=0 или (0,0).

Solution 6: (x- \color{red}{5})=-25 и (y+ \color{green}{5})= 1 oдносно x=-20 и y=-4 или (-20,-4).

Answer: The solution of the diophantine equation \color{red}{5}y-\color{green}{5}x=xy is the points: (6,-30), (10,-10), (30,-6), (4,20), (0,0) и (-20,-4)