Quadratic Diophantine EquationDate: 01/16/2009 at 11:07:02 From: Dave Subject: Quadratic polynomial equals square of odd integer In solving a probability and combinatorics problem, I encountered the following question: Find all positive integers N such that 2*N^2 - 2*N + 1 is the square of an odd integer. I have found all solutions under 10 million (4, 21, 120, 697, 4060, 23661, 137904, 803761, 4684660) using the computer and could program it to find more by looping through, but is there a general form for the solution? Are there finitely many solutions or infinitely many? Thanks Dr. Math! Date: 01/17/2009 at 04:32:22 From: Doctor Jacques Subject: Re: Quadratic polynomial equals square of odd integer Hi Dave, This is a particular case of a quadratic Diophantine equation. There are a few articles on that subject in our archive, for example: Sum of First N Positive Integers Making a Perfect Square http://mathforum.org/library/drmath/view/70344.html In this case, we want to solve the equation: 2*N^2 - 2*N + 1 = y^2 [1] in integers (there is not need to specify that y must be odd; this results directly from the equation). The first thing to do is to "complete the square", to get rid of linear terms. In this case, we first multiply everything by 2 to get a square as the leading coefficient: 4*N^2 - 4*N + 2 = 2*y^2 and we complete the square: (2*N-1)^2 + 1 = 2*y^2 by putting x = 2*N-1, we can rewrite this as: x^2 - 2*y^2 = -1 [2] This equation has one obvious solution: x = y = 1, corresponding to N = 1 (which you forgot...). The problem is now to find all the solutions. Notice that we may write: x^2 - 2*y^2 = (x + y*sqrt(2))(x - y*sqrt(2)) and this leads us to investigate the properties of numbers of the form (x + y*sqrt(2)), where x and y are integers (or rationals). Note that those numbers constitute a ring, i.e., the sum and product of two such numbers is a number of the same type. We define the conjugate of the number u = (x + y*sqrt(2)) as u' = (x - y*sqrt(2)). This is somewhat similar to the notion of complex conjugates, and this is no coincidence: taking the conjugate amounts to replacing sqrt(2) by -sqrt(2), much like taking the complex conjugate amounts to replacing i by -i. Conjugation is compatible with addition and multiplication; specifically, we have: (u + v)' = u' + v' (u*v)' = u' * v' [3] as you can easily check. We next define the norm of the number u = x + y*sqrt(2) as the product of the conjugates: N(u) = u*u' = x^2 - 2*y^2 [4] Because of [3], we have: N(u*v) = (u*v)*(u*v)' = u * v * u' * v' = (u*u')*(v*v') = N(u)*N(v) [5] Let us now return to the problem at hand. We may write the equation [2] as: N(u) = N(x*y*sqrt(2)) = -1 [6] and we already have a solution u_1 = 1 + sqrt(2), corresponding to x = y = 1. Because of [5], if we can find a number v = a+b*sqrt(2) such that N(v) = a^2 - 2*b^2 = +1, we will have: N(u*v) = N(u)*N(v) = (-1)*(+1) = -1 which means that u*v will be another solution of [6], from which we can extract the new values of x and y as the rational and irrational parts of (u*v), respectively. By repeating the process, we can get an infinity of solutions. To find v, we need to solve: N(v) = a^2 - 2*b^2 = 1 [7] for integer a and b. This is (mistakenly) known as Pell's equation. There is a general method, based on continued fractions, for solving that kind of equation, but, in this case we find easily the solution v = 3*2*sqrt(2) by trial and error (a more enlightened approach would be to notice that, as N(u) = -1, N(u^2) = +1 by [5], and we have v = u^2). So, given a solution u[k] = x[k] + y[k]*sqrt(2), we find the next solution as: u[k+1] = u[k] * v = (x[k]+y[k]*sqrt(2))(3+2*sqrt(2)) = (3*x[k]+4*y[k]) + (2*x[k]+3*y[k])*sqrt(2) = x[k+1] + y[k+1]*sqrt(2) and this gives the recurrence relations: x[k+1] = 3*x[k] + 4*y[k] y[k+1] = 2*x[k] + 3*y[k] [8] As we have N = (x+1)/2, and N must be an integer, we only need the solutions with x odd, but, as [8] shows, if x[1] is odd (and this is the case), all subsequent values of x will also be odd. Starting with x[1] = y[1] = 1, we find the first few solutions: x y N --------------- 1 1 1 7 5 4 41 29 21 239 169 120 1393 985 697 We may also find an explicit form for the general solution. Note that, if u = (x+y*sqrt(2)), we have: x = (u + u')/2 y = (u - u')/(2*sqrt(2)) and, as we have: u[k] = u[1]*v^k = [1+sqrt(2)) * (3+2*sqrt(2)]^k we get: x[k] = [(1+sqrt(2))*(3+2*sqrt(2))^k + (1-sqrt(2))*(3-2*sqrt(2))^k]/2 In this particular case, as noted before, we have v = u[1]^2, and we may simplify the above expression as: x[k] = [(1+sqrt(2))^(2k+1) + (1-sqrt(2))^(2k+1)]/2 There is a whole theory about the solution of this type of equations, the theory of quadratic forms, developed by Gauss; this is only a very simple case. Please feel free to write back if you require further assistance. - Doctor Jacques, The Math Forum http://mathforum.org/dr.math/ Date: 01/18/2009 at 12:49:01 From: Dave Subject: Quadratic polynomial equals square of odd integer Thanks for the help! The problem was this: A drawer contains N socks, of which r are red and the rest are black. The probability of drawing 2 red socks is exactly 1/2. How many socks are there? And how many are red? r and N must be positive integers (r is at least 2) and must satisfy the equation 2*r*(r-1) = N*(N-1). I followed your method and found solutions for r and N in terms of odd powers of 1+sqrt(2). (Take x = 2*N-1, y = 2*r-1, u = x+y*sqrt(2), then N(u) = -1, etc.) To finish this off, is there any way to show that any solution of the equation N(u) = -1 must be of this form, without appealing to abstract algebra (rings, units, etc)? This is for a probability class in which most students have not taken abstract algebra. I searched through the resources on here and the links to external websites, but none of them have an answer to this one. Thanks again! Date: 01/19/2009 at 02:58:30 From: Doctor Jacques Subject: Re: Quadratic polynomial equals square of odd integer Hi Dave, Unfortunately, I don't believe that this can be proved in an elementary way. The main issue is to prove that all integer solutions of the equation x^2 - 2*y^2 = (+/-)1 come from powers of a single number, called a fundamental unit (in this case, 1+sqrt(2)). This is called Dirichlet's Unit theorem, and it requires some knowledge of algebraic number theory. - Doctor Jacques, The Math Forum http://mathforum.org/dr.math/ Date: 01/19/2009 at 06:41:58 From: Dave Subject: Thank you (Quadratic polynomial equals square of odd integer) Thanks for all your help with this problem! |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/