Monday, November 14, 2005

Diophantine Fun. Topic: Number Theory. Level: AIME.

Problem: Find all integer solutions $(m,n)$ to the equation

$n^4+n^3+2n^2+2n+1 = m^2$.

Solution: Let me introduce a technique used to solve diophantine equations with a power (square in this case) on one side and a multiple of that power (fourth power) on the other: Bounding.


Example - Suppose you had the equation $n^2+3n+3 = m^2$ (assume positive integers for the example; it is not necessary for the actual problem though). We can say

$(n+1)^2 < n^2+3n+3 < (n+2)^2$ which can be verified by expanding.

The LHS becomes $0 < n+2$ and the RHS becomes $0 < n+1$.

But there are no integer squares between $(n+1)^2$ and $(n+2)^2$ so we can conclude that there are no solutions.


Now back to the problem... we look for bounding squares; however, this requires some experimenting and matching coefficients. We want to match at least the first two terms - $n^4+n^3$.

After playing around with squares, we find a pretty good bound that works for $n \ge 4$ and $n \le 0$:

$\displaystyle \left(n^2+\frac{n}{2}+\frac{1}{2}\right)^2 \le n^4+n^3+2n^2+2n+1 \le \left(n^2+\frac{n}{2}+1\right)^2$.

The LHS becomes $\displaystyle 0 \le \frac{3}{4}(n+1)^2$ and the RHS $\displaystyle 0 \le n\left(\frac{n}{4}-1\right)$ (hence the restrictions on $n$).

Since there are no squares between $\displaystyle \left(n^2+\frac{n}{2}+\frac{1}{2}\right)^2$ and $\displaystyle \left(n^2+\frac{n}{2}+1\right)^2$, the only possible solutions are the equality conditions and $n=1,2,3$.

Checking those three, we find nothing, so we move to the equality conditions.

As noted above, the equality conditions are $\displaystyle 0 = \frac{3}{4}(n+1)^2$ and $\displaystyle 0 = n\left(\frac{n}{4}-1\right)$, giving the solutoins $n=-1, 0, 4$. Then $m = \pm 1, \pm 1, \pm 19$, respectively.

Hence our solutions are: $(m,n) = (-1, \pm 1); (0, \pm 1); (4, \pm 19)$. QED.


Practice Problem: Find all nonnegative integer solutions $(a,b)$ to the equation

$a^6+2a^4+2a^2+2a+1 = b^2$.


  1. Cool, I want to learn that method, but thank you for making this site exist, it's very useful....

  2. Bounding can be done with

    (a^3+a)^2 < a^6+2a^4+2a^2+2a+1 <(a^3+a+1/a)^2 [ <= (a^3+a+1)]

    This simplifies to 0< (a+1)^2 on the LHS
    and 0< (a+1)^2+1/a^2 on the RHS
    both equations are satisfied nonnegative values of a and "a^3+a" is an integer, so this problem has no nonnegative solutions.