Finding Primitive SolutionsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/