Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Digits Sums, Mod Proofs, Olympiad Squares, and Equal Roots

Date: 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.
Associated Topics:
High School Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/