Finding Primitive Solutions

Date: 10/11/2000 at 02:47:11
From: J.F WETS
Subject: Extended Pythagorean equations

How do I find all the solutions for (x,y,z) belonging to Z for this?

     x^2 + 5*y^2 = z^2

One solution is (4,2,6). Are there solutions with GCD(x,y) = 1?

Date: 10/11/2000 at 09:56:31
From: Doctor Rob
Subject: Re: Extended Pythagorean equations

Thanks for writing to Ask Dr. Math, J.F.

Yes, there are solutions with GCD(x,y) = 1. Here are two: (2,1,3) and 
(1,0,1). In fact, if GCD(x,y) = d, then d | z, too, and (x/d,y/d,z/d) 
is a smaller solution. One can then just search for solutions with 
GCD(x,y) = 1, and all of x, y, and z positive, which are called 
primitive solutions.

If you change the sign of x, y, or z, or any combination of these, you 
will turn a solution into another solution. This means that you can 
restrict your search for solutions to ones with x, y, and z all 
positive.

Each positive primitive solution will give you an infinite family of 
solutions (k*x, k*y, k*z), for k any positive integer. Also observe 
that GCD(x,z) = 1 and GCD(y,z) = 1. Also observe that the only 
primitive solution with one of the variables 0 is (1,0,1), so we can 
assume that all variables are positive.

Start by rewriting the equation in the form

       z^2 - x^2 = 5*y^2
     (z-x)*(z+x) = 5*y^2

Observe that GCD(z-x,z+x) = 1 or 2, according to whether y is odd or 
even. Then there are the following cases.

Case 1: y is odd and 5 | (z + x). Then GCD(z-x,z+x) = 1, z - x and 
z + x are odd, and

     (z+x)/5 = b^2
       z - x = a^2

for some odd positive integers a and b. Then

     z = (5*b^2+a^2)/2
     x = (5*b^2-a^2)/2
     y = a*b

Now it must be that GCD(a,b) = 1, or else (x,y,z) would not be 
primitive.

Case 2: y is odd and 5 | (z - x). Then GCD(z-x,z+x) = 1, z - x and 
z + x are odd, and

     (z-x)/5 = b^2
       z + x = a^2

for some odd positive integers a and b. Then

     z = (a^2+5*b^2)/2
     x = (a^2-5*b^2)/2
     y = a*b

Now it must be that GCD(a,b) = 1, or else (x,y,z) would not be 
primitive.

Case 3: y is even and 5 | z + x. Then GCD(z-x,z+x) = 2, z - x and 
z + x are even, and

     (z+x)/10 = b^2
      (z-x)/2 = a^2

for some positive integers a and b. Then

     z = 5*b^2 + a^2
     x = 5*b^2 - a^2
     y = 2*a*b

Now it must be that GCD(a,b) = 1, or else (x,y,z) would not be 
primitive. Furthermore a and b cannot both be odd, or else x, y, and z 
would all be even, and (x,y,z) would not be primitive.

Case 4: y is even and 5 | z - x.  Then GCD(z-x,z+x) = 2, z - x and 
z + x are even, and

     (z-x)/10 = b^2
      (z+x)/2 = a^2

for some positive integers a and b. Then

     z = a^2 + 5*b^2
     x = a^2 - 5*b^2
     y = 2*a*b

Now it must be that GCD(a,b) = 1, or else (x,y,z) would not be 
primitive. Furthermore a and b cannot both be odd, or else x, y, and z 
would all be even, and (x,y,z) would not be primitive.

Summing up the four cases, all the positive primitive solutions of

     x^2 + 5*y^2 = z^2

are given by

     x = |a^2 - 5*b^2|
     y = 2*a*b
     z = (a^2 + 5*b^2)

where a and b are positive integers with GCD(a,b) = 1, or half these 
values when a and b are both odd.

Non-primitive solutions can be found by multiplying x, y, and z from a 
primitive solution by any integer k > 1. Every positive solution gives 
seven other solutions with one or more of x, y, and z negative, just 
by changing signs.

Table:

     a   b      x    y    z
     1   0      1    0    1
     1   1      2    1    3
     1   2     19    4   21
     2   1      1    4    9
     1   3     22    3   23
     3   1      2    3    7
     1   4     79    8   81
     2   3     41   12   49
     3   2     11   12   29
     4   1     11    8   21

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/