Digits Sums, Mod Proofs, Olympiad Squares, and Equal RootsDate: 12/15/2011 at 13:00:44 From: ARITRA Subject: NUMBER THEORY PROBLEM Find all numbers such that the cube of the sum of their digits equals the number itself. Routine methods have failed, so I have begun to consider that it must be impossible. Date: 12/15/2011 at 13:30:27 From: Doctor Carter Subject: Re: NUMBER THEORY PROBLEM Dear Aritra, Thank you for writing to Dr. Math! I'm happy to tell you just a little bit: 1) Both 0 and 1 have the desired property. 2) Suppose a_0, a_1, ..., a_n are the decimal digits of an n-digit number, least significant first. So each of a_0, a_1, ..., a_n is an integer between 0 and 9. Assume that a_n is not 0, (so that the number really takes n digits). You're interested in whether the following condition can hold: a_0 + 10 a_1 + ... + 10^n a_n = (a_0 + a_1 + ... + a_n)^3 Since we assume a_n is at least 1, the left hand side of this equation is at least 10^n. Since each of the a_i's is at most 9, the right hand side is at most (9 (n + 1))^3. 10^n gets big faster than (9 (n + 1))^3, so we can ask What is the largest n such that 10^n <= (9 (n + 1))^3? You can answer this question quickly; it turns out that this inequality is true only when n is less than or equal to 5. This means that no number with 6 or more digits can be equal to the cube of the sum of its digits. You can finish the problem by testing each of the 100,000 integers between 0 and 99,999. I'll leave this part to you. - Doctor Carter, The Math Forum http://mathforum.org/dr.math/ Date: 12/18/2011 at 05:57:58 From: ARITRA Subject: Thank you (NUMBER THEORY PROBLEM) Thank you very much, sir. I have written a computer program and that has helped me to know those numbers. I would be very happy if you would help me with the following problem: f(x) = ax^2 + bx + c modulus of f(x) <= 1 for x <= 1. Prove that mod(a) + mod(b) + mod(c) <= 7 Date: 12/18/2011 at 15:24:38 From: Doctor Carter Subject: Re: Thank you (NUMBER THEORY PROBLEM) Hi Aritra, I would start by noting that f(0) = c f(1) = a + b + c f(-1) = a - b + c. Thus, you know right away that mod(c) <= 1 mod(a + b + c) <= 1 mod(a - b + c) <= 1 Does this help? - Doctor Carter, The Math Forum http://mathforum.org/dr.math/ Date: 12/27/2011 at 09:11:06 From: ARITRA Subject: Thank you (NUMBER THEORY PROBLEM) Thank you, sir. Can you suggest a good number theory book which focuses on teaching and problem-solving simultaneously? Date: 12/28/2011 at 08:25:18 From: Doctor Carter Subject: Re: Thank you (NUMBER THEORY PROBLEM) Dear Aritra, There are many books I might recommend. Here are three: J. Leveque, Elementary Theory of Numbers, Dover J. Leveque, Fundamentals of Number Theory, Dover E. Landau, Elementary Number Theory, AMS Chelsea Publishing Here's another, which may be harder to find: J. Roberts, Elementary Number Theory, A problem Oriented Approach, MIT Press Good luck! - Doctor Carter, The Math Forum http://mathforum.org/dr.math/ Date: 12/29/2011 at 05:08:32 From: ARITRA Subject: Thank you (NUMBER THEORY PROBLEM) Thank you, again. Can you help me with another problem? For integers a, b, and q, show that this is always a perfect square: (a^2 + b^2)/(a*b + 1) This is an International Mathematical Olympiad (IMO) problem which is solved in Arthur Engel's "Problem Solving Strategies" using a weird method that involves a hyperbola. I wanted to give a better solution. I proceeded quite a bit, showing that the discriminant of the equation must be a perfect square, but ultimately I jumbled it up. Please help me with this. Date: 12/29/2011 at 07:59:41 From: Doctor Carter Subject: Re: Thank you (NUMBER THEORY PROBLEM) Dear Aritra, If I consider a = 3 and b = 4, then (a^2 + b^2)/(a*b + 1) = 25/13 This is not the square of a rational number. What is this q you are speaking of? I don't see any q in (a^2 + b^2)/(a*b + 1). Have you perhaps stated the problem slightly wrong? - Doctor Carter, The Math Forum http://mathforum.org/dr.math/ Date: 01/04/2012 at 23:48:42 From: ARITRA Subject: Thank you (NUMBER THEORY PROBLEM) Sir, you are not getting it.... I am saying let (a^2 + b^2)/(a*b + 1) = q There must be some integers a and b for which q is an integer. We have to prove that these integers are perfect squares in this case. Please prove this. Date: 01/05/2012 at 07:09:11 From: Doctor Carter Subject: Re: Thank you (NUMBER THEORY PROBLEM) Thank you for restating the question. I have found the following examples: a = 8, b = 2, q = 4 a = 27, b = 3, q = 9 I also notice that q is a square, although a and b are not. I can't yet prove that when q is an integer it must be a square, but I will continue to think about it. - Doctor Carter, The Math Forum http://mathforum.org/dr.math/ Date: 01/08/2012 at 11:27:42 From: Doctor Carter Subject: Re: Thank you (NUMBER THEORY PROBLEM) Dear Aritra, I don't have an answer yet, but I can report some progress. First Observation: Suppose that a >= b. Write q = b^2 (a^2/b^2 + 1)/(ab + 1) Is this true? a^2/b^2 + 1 = ab + 1 It turns out that this happens exactly when a = b^3. So whenever a = b^3, it's also the case that ... (a^2 + b^2)/(ab + 1) = b^2, ... which is the square of an integer. But there are other ways that (a^2 + b^2)/(ab + 1) can be an integer; for example, a = 30, b = 8 In this case, q = 4 -- a square again. Another example is a = 112, b = 30, q = 4. Second Observation: Let d be the greatest common divisor of a and b, and put e = a/d f = b/d Then (a^2 + b^2) = d^2 (e^2 + f^2) No prime factor of ab + 1 can be a factor of d. So if this ... (a^2 + b^2)/(ab + 1) ... is an integer q, then q is divisible by d^2; and this ... (e^2 + f^2)/(ab + 1) ... must also be an integer. In all cases I've found so far, whenever (a^2 + b^2)/(ab + 1) is an integer, it's the case that (a^2 + b^2)/(ab + 1) = d^2 where d is the GCD of a and b. I don't know yet whether this is always the case. - Doctor Carter, The Math Forum http://mathforum.org/dr.math/ Date: 01/10/2012 at 11:37:32 From: ARITRA Subject: number theory problem Suppose that this polynomial equation has all positive real roots: x^4 - 4x^3 + ax^2 + bx + 1 = 0 Show that all the roots of the polynomial are equal. Please help. Date: 01/11/2012 at 07:05:24 From: Doctor Carter Subject: Re: number theory problem Good morning! If you think about expanding ... (x - c)(x - d)(x - e)(x - f) ... you'll remember that the coefficient of x^3 is -(c + d + e + f) and the constant coefficient is cdef. For this problem, it follows that ... c + d + e + f = 4 ... and also that ... cdef = 1. If c, d, e, and f are positive numbers, we're in a good position to apply the arithmetic geometric mean inequality. By the way, another volunteer on this site has an excellent insight into your previous problem -- that (a^2 + b^2)/(ab + 1) is a square whenever it's an integer. I expect that you'll hear from him soon. Cheers - - Doctor Carter, The Math Forum http://mathforum.org/dr.math/ Date: 01/11/2012 at 15:26:47 From: Doctor Vogler Subject: Re: Thank you (NUMBER THEORY PROBLEM) Hi Aritra, Thanks for writing to Dr. Math. Your previous problem is a fairly complicated one. Since you meant "positive integers" rather than "positive real numbers," you are asking about the Diophantine equation a^2 + b^2 = q*(a*b + 1) A Diophantine equation is one where you are interested in integer solutions. Your question is: Prove that if a, b, and q are integers that solve the above Diophantine equation, then q is a perfect square (i.e., the square of an integer). This is one of those problems where you have a method of transforming one solution into another. In particular, say you have a solution of this form for integers a, b, and q: (a, b, q) Then you can find another such solution. The trick here is thinking of this as a quadratic polynomial in a: a^2 - (q*b)*a + (b^2 - q) = 0 Then this polynomial has two solutions (in a, for a given choice of b and q), the product of which is b^2 - q and the sum of which is q*b. For a particular choice of b and q, those two solutions might not be integers, or even rational. But if you have one solution in positive integers, (a, b, q), then another solution will be (qb - a, b, q). You can check this directly by substituting qb - a for a into the equation a^2 + b^2 = q*(a*b + 1). Then check that this simplifies to the same equation. So what does this tell us? Well, since the equation is also symmetric in a and b, we can get from one solution (a, b, q) to either (b, a, q) or (qb - a, b, q). For example, we can start with (0, 2, 4) and get to ... (2, 8, 4), (8, 30, 4), (30, 112, 4), (112, 418, 4), (418, 1560, 4), (1560, 5822, 4), (5822, 21728, 4), (21728, 81090, 4), (81090, 302632, 4), (302632, 1129438, 4), (1129438, 4215120, 4), (4215120, 15731042, 4), (15731042, 58709048, 4), ... and so on. In this way, we can keep getting more and bigger solutions. But the value of q doesn't change, and since you want to know about which q values you can get, these can all be considered as a single solution. Notice that we can get that q value with extremely large a and b values, which is annoying because it means that we can't rule out very large a and b values when trying to decide which q values are possible. But there is something else we can do that's just as good: Suppose there is some solution (a, b, q). Maybe a and b are very large, but if so, then we can do the same method of getting from one solution to another, but in the other direction, until we get to the smallest solution in that chain (for that q value). So we suppose that we have a solution in positive integers (a, b, q). If ... a < b, ... then we switch a and b, so that a >= b. And if ... a >= b and 0 < bq - a < a ... then we change a into bq - a and repeat. Since the positive integer a + 2b is getting strictly smaller at every step, this can't go on indefinitely, which means that eventually the process will stop at a solution which has both ... a >= b ... and either ... bq - a >= a or bq - a <= 0. So we have proven that if there is a positive integer solution (a, b, q) to the equation ... a^2 + b^2 = q*(a*b + 1), ... then there is another positive integer solution with possibly different a and b, but which has the same q and also satisfies these inequalities: a >= b and either bq - a >= a or bq - a <= 0. We might call such a solution a "minimal solution." So if we want to decide what q values are possible, then we only have to find all of the (minimal) solutions in positive integers to ... a^2 + b^2 = q*(a*b + 1), a >= b, ... and either ... bq >= 2a or bq <= a. In the case where bq >= 2a, we have (since b and ab + 1 are both positive) (a^2 + b^2)/(ab + 1) = q >= 2a/b, b(a^2 + b^2) >= 2a(ab + 1). Then since a >= b, we have a^2*b >= b^2*b = b^3, and therefore 2*a^2*b = a^2*b + a^2*b >= a^2*b + b^3 = b(a^2 + b^2) >= 2*a*(a*b + 1) = 2*a^2*b + 2*a This gives us 0 >= 2*a, contradicting that a is positive. So all minimal solutions must have bq <= a. I will demonstrate that all minimal solutions must have bq = a, because otherwise bq < a, so a >= bq + 1 a^2 >= abq + a q(ab + 1) = a^2 + b^2 >= abq + a + b^2 q >= a + b^2 a^2 + b^2 = q(ab + 1) >= (a + b^2)(ab + 1) = a^2*b + a + ab^3 + b^2 > a^2 + a + a + b^2 This is, again, impossible since a and b are positive. So all minimal solutions must have bq = a, which means that taking one more transformation would take our solution to one with a = 0 (but that's not positive, so we don't consider it a legal transformation). Either way, the point is that a^2 + b^2 = qab + q = a^2 + q Therefore, q = b^2. So the only possible values for q are perfect squares. And you can get all solutions in positive integers by starting with a solution of the form (0, b, b^2) and then repeatedly applying the transformations (a, b, q) -> (b, a, q) or (a, b, q) -> (qb - a, b, q). 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: 01/12/2012 at 11:17:42 From: ARITRA Subject: Thank you (NUMBER THEORY PROBLEM) Aha, thank you for the sum on (a^2 + b^2)/(ab + 1). I have seen the solution. It's quite long but very logical. Thank you. Date: 01/12/2012 at 11:32:44 From: ARITRA Subject: Thank you (NUMBER THEORY PROBLEM) Thank you. This is an excellent solution. |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/