The Sum of Squares and Its Square Integer QuotientDate: 07/19/2015 at 23:57:48 From: Roumya Subject: Help in number theory,plz..!! If (ab + 1) divides (a^2 + b^2), then prove that (a^2 + b^2) when divided by (ab + 1) gives a square of an integer. I tried using the Chinese remainder theorem but I couldn't find any way to solve this. Date: 07/20/2015 at 20:32:07 From: Doctor Vogler Subject: Re: Help in number theory,plz..!! Hi Roumya, Thanks for writing to Dr. Math. If a = -1 and b = 2, then ab + 1 divides a^2 + b^2, but this is not a square: (a^2 + b^2)/(ab + 1) = -5 So I'm going to assume that you mean that a and b are positive integers. Actually, I'm going to relax that slightly and only assume that a and b are non-negative integers (greater than or equal to zero). In fact, your question sounds rather like this one: http://mathforum.org/library/drmath/view/71597.html But there, I think a special technique applies, so here I'm going to use a somewhat different strategy. Suppose that there exist non-negative integers a, b, k such that (ab + 1)k = a^2 + b^2 Notice that this is symmetric in a and b, meaning that you can get from one (a, b, k) solution to another by swapping a and b: (b, a, k). Also notice that you can write this as a quadratic polynomial in a: a^2 - (bk)a + (b^2 - k) = 0. A quadratic equation has (in general) two solutions. Their sum is the negative of the coefficient of a, and their product is the constant term. That means that if you have one solution for a, then the other one is bk - a, since the two solutions have to sum to bk. So you can always get from one solution of your equation (a, b, k) to the solution (bk - a, b, k). By combining these two steps, you can get from one solution to infinitely many more. For example, pick an integer m and start with the integer solution a = m, b = 0, k = m^2. Now swap a and b, and replace a with bk - a. Then repeat. You get: (m, 0, m^2) (m^3, m, m^2) (m^5 - m, m^3, m^2) (m^7 - 2m^3, m^5 - m, m^2) (m^9 - 3m^5 + m, m^7 - 2m^3, m^2) ... Notice that you can also do this in reverse: From one solution (a, b, k), swap a and b if necessary to get a > b, and then replace a with bk - a, and repeat: (m^9 - 3m^5 + m, m^7 - 2m^3, m^2) (m^7 - 2m^3, m^5 - m, m^2) (m^5 - m, m^3, m^2) (m^3, m, m^2) (m, 0, m^2) Of course, k does not change during this process, so questions about k remain the same. Here's one way to solve this problem. Suppose that you have a solution (a, b, k) in non-negative integers. Swap a and b if necessary to get a >= b. Then replace a with bk - a if this results in a smaller non-negative value for a. And repeat. This process will not end until a >= b and either a <= bk - a or bk - a < 0. Now we prove the following: There are no solutions where a, b, and k are non-negative integers, and b <= a <= bk - a, and (ab + 1)k = a^2 + b^2. If a, b, and k are non-negative integers, with all three of ... b <= a bk < a (ab + 1)k = a^2 + b^2, ... then b = 0. Proof of first claim: b^2 <= a^2 <= a(bk - a) = b^2 - k This implies that k <= 0, which is impossible. Proof of second claim: Since bk < a, but both are integers, that means that a - bk >= 1. Then k - b^2 = (a - bk)a >= a. So k >= a + b^2. Then a^2 + b^2 = (ab + 1)k >= (ab + 1)(a + b^2) = ba^2 + a + ab^3 + b^2, 0 >= (b - 1)a^2 + a + ab^3 This is impossible when b >= 1. So we must conclude that b = 0. Of course, since b = 0, k = a^2 is a perfect square. We can also conclude that *every* solution in non-negative integers comes from starting with a non-negative integer m (necessarily, the square root of k), and the solution (m, 0, m^2), and then applying the transformation (a, b, k) -> (bk - a, a, k) some number of times. If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/ Date: 07/21/2015 at 00:00:07 From: Roumya Subject: Thank you (Help in number theory,plz..!!) Wow -- Thank you very much! I ... I don't know what to say. This has helped me a lot.... I would like to ask more questions in future. Thanks. |
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/