Chaitanya's Random Pages

September 30, 2012

When is a perfect square the difference of two consecutive cubes?

Filed under: mathematics — ckrao @ 12:13 pm

This post is inspired by an attempt at the final question of the 2008 AIME II.

We consider the question of when a perfect square is equal to the difference of two consecutive cubes. If we let the cubes be a^3 and (a+1)^3, we see that we require \displaystyle (a+1)^3 - a^3 = 3a^2 + 3a + 1 to be a perfect square, say {n^2}.

If you list the first cubes they are 0,1,8,27,64,125,216,343,512,729,1000 and their differences are 1,7,19,37,61,91,127,169,217,271. Of these the squares are 1 = 1^3 - 0^3 and 169 = 13^2 = 8^3 - 7^3. By continuing to list cubes it would take a while to find the next instance of a square as a difference – the next solution is 32761 = 181^2 = 105^3 - 104^3. 🙂

Initially I tried solving this problem by rearranging n^2 = 3a^2 + 3a + 1 as (n-1)(n+1) = 3a(a+1) but that did not take me far. Another approach was via congruences, noting that the right side is 1 \mod 6 so that n had to be of the form n = 6m \pm 1. The third and most fruitful approach for me was to view the equation as a quadratic in a.

\displaystyle 3a^2 + 3a + 1 - n^2 = 0 \quad \quad (1)

Since this has integer roots, its discriminant must be a perfect square. In other words, 9 - 4.3(1-n^2) = 3(4n^2 - 1) = t^2 for some integer t. This equation implies t must be a multiple of 3, so letting t = 3m we obtain 3(4n^2 - 1) = 9m^2, or

\displaystyle (2n)^2 - 3m^2= 1.

In other words, we need to find (positive) integer solutions to x^2 - 3y^2 = 1 where x is even. An equation of this form is known as Pell’s equation. We claim that solutions to this equation are of the form \pm (x_0 + y_0 \sqrt{3})^n, where x_0 + y_0 \sqrt{3}  is the smallest positive solution to x^2 - 3y^2 = 1 while x_0 > 1.

To see why this is so, firstly note that if (x_1, y_1) is another positive solution with x_1 > x_0, then the equation x_0^2 - 3y_0^2 = x_1^2 - 3y_1^2 = 1 leads to 0 < x_1^2 - x_0^2 = 3(y_1^2 - y_0^2), so y_1 > y_0 and x_0 + y_0\sqrt{3} < x_1 + y_1\sqrt{3}. Hence it makes sense to define the “smallest solution”.

Next, we know there exists some k for which

\displaystyle (x_0 + y_0\sqrt{3})^k \leq x_1 + y_1\sqrt{3} < (x_0 + y_0\sqrt{3})^{k+1}.

Multiplying all sides by (x_0 - y_0\sqrt{3})^k and using the fact that x_0^2 - 3y_0^2 = 1 gives us

\displaystyle 1 \leq (x_1 + y_1 \sqrt{3})(x_0 - y_0\sqrt{3})^k < x_0 + y_0\sqrt{3}.\quad \quad (2)

Define u + v\sqrt{3} := (x_1 + y_1 \sqrt{3})(x_0 - y_0\sqrt{3})^k. We can use norms in \mathbb{Z}[\sqrt{3}] or explicit computation to show that u^2 - 3v^2 = 1. Equation (2) then contradicts the minimality assumption on x_0 + y_0\sqrt{3} unless we have u =1, v= 0. We conclude that (x_1 + y_1 \sqrt{3}) = (x_0 + y_0 \sqrt{3})^k, so all solutions are of this form proving the claim.

In our case, the minimal solution is x_0 = 2, y_0 = 1, so we have the general solution

x_k + y_k \sqrt{3} = \pm (2 + \sqrt{3})^k, \quad k = 0, 1, 2, \ldots

We can use the recurrence x_{k+1} + y_{k+1}\sqrt{3} = (x_k + \sqrt{3}y_k)(2 + \sqrt{3}) = (2x_k + 3y_k) + (x_k + 2y_k)\sqrt{3} to see that x_{k+1} and y_k have the same parity (odd or even), as do y_{k+1} and x_k. Since initially x_0 = 2, y_0 = 1, we see that the solutions alternate in parity. Since we are looking for x being even, we are looking for odd k.

x_{2k+1} + y_{2k+1}\sqrt{3} = \pm (2 + \sqrt{3})^{2k+1} = \pm (2 + \sqrt{3})(7 + 4\sqrt{3})^k.

Using the same method as before this leads to the recurrences

\begin{aligned} x_{2k+3} &= 7x_{2k+1} + 12y_{2k+1}\\ y_{2k+3} &= 4x_{2k+1} + 7y_{2k+1}\end{aligned}

We can decouple these by taking 7 times the first equation minus 12 times the second to obtain 7x_{2k+3} - 12 y_{2k+3} = x_{2k+1}. Then x_{2k+3} = 7x_{2k+1} + 12y_{2k+1} = 7x_{2k+1} +(7x_{2k+1} - x_{2k-1}) = 14x_{2k+1} - x_{2k-1}. Similarly we find y_{2k+3} = 14y_{2k+1} - y_{2k-1}.

Initial solutions are (2,1), (26, 15), (362, 209), .... From (1) we have a = (-1 \pm t)/2 = (-1 \pm 3m)/2, so we require m = y to be odd. This will indeed be the case by our parity arguments from before (that x_k and y_k have different parity). We conclude that this recurrence gives us the entire solution set for (2n, m). The non-negative (a_k,n_k) solutions are (0, 1), (7,13), (104, 181), (1455, 2521), .... In other words,

\begin{aligned} 8^3 - 7^3 &= 13^2\\105^3 - 104^3 &= 181^2\\ 1456^3 - 1455^3 &= 2521^2, \ldots \end{aligned}

The recurrence linking these can be found to be a_{k+1} = 14a_k - a_{k-1} + 6 and n_{k+1} = 14 n_k - n_{k-1} and it can be verified that (a_k+1)^3 -a_k^3 = n_k^2. The factor of 14 in the recurrence indicates that the solution set is relatively sparse (though still infinite).

A similar approach is shown in [3], where the Pell’s equation is obtained by completing the square to obtain (2n)^2 - 3(2a+1)^2 = 1 rather than using the discrminant.

References

[1] Dušan Đukić, “Pell’s equation”, The IMO Compendium Group

[2] Matthew Wright, “Solving Pell’s equation”, available here.

[3] 2008 AIME II Problems/Problem 15 – AoPSWiki

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: