Introduction

This exercise appears in [1] and is numbered as P1966-1. It comes from a mathematics competition held in Indiana. The numbers mean it is problem 1 of the exam held in 1966 (which was the first such exam).

[ P1966-1 ]

Show that the equation x^2-y^2 = a^3 always has integer solutions for x and y whenever a is a positive integer.

Heuristic Analysis

After reading the problem we should immediately wonder why there would always exist two integers such that when you square them and take the difference you can always find a cube. In other words, for every cube derived from a positive integer such a pair x and y exists.

It’s obvious we can’t formulate a proof without understanding why this is true. After some study you might realize that the statement isn’t so mystical after all. First, let’s take a look at the inputs. They said x and y are integers, but since x and y are squared this means the result is always positive. Hence if x > y we have x^2 - y^2 > 0 which we need since a>0. So we might as well work our problem by assuming x > y.

The next part to consider is that the result of x^2 - y^2 is always an integer since the square of an integer always yields an integer. Since the problem states that a is a positive integer, by the same logic we have that a^3 is always a positive integer also. So after thinking about how the assumptions interact with the left hand side we see no contradiction with how the assumptions interact with the result of the right hand side. The problem seems logically sound so far! I would highly recommend always thinking through this type of logic prior to trying to formulate a proof! Always make sure you understand all the assumptions and how they interact with what you are trying to prove.

Further Analysis

After taking the steps to verify the assumptions we can begin to wonder why the statement we are trying to prove is true. We see a difference of squares, and could immediately begin by exploring the well known identity x^2-y^2=(x+y)(x-y). Another good approach is to plug in some values for x^2 and y^2 and see how the difference behaves. For example, consider the following table:

x y x^2 y^2 x^2-y^2
1 0 1 0 1
2 1 4 1 3
3 2 9 4 5
4 3 16 9 7
5 4 25 16 9
6 5 36 25 11

In the above table we simply explored what happens if we plug consecutive integers into x and y and take their difference. The result is that we seem to generate all of the odd integers. This means we can generate any odd cube by simply using the proper x and y, which are separated by 1.

Since we have all the odds, the next step would be to see if we can find a way to generate all even integers. Let’s try numbers that differ by two as follows:

x y x^2 y^2 x^2-y^2
2 0 4 0 4
3 1 9 1 8
4 2 16 4 12
5 3 25 9 16
6 4 36 16 20
7 5 49 25 24

This table looks close to what we want, but we seem to be generating multiples of 4, so we aren’t getting all of the even integers. This is a good time to conclude the heuristic experiment we are running, and start to look at some formulas.

Generalization: Explore the Equations

The next step is to generalize the results above by using the given assumptions to formulate the proof. First, let’s start with the consecutive integers case as follows:

Let x and y be consecutive integers such that x=k+1 and y=k where k \in \mathbb{Z}.

Next let’s substitute into our difference.

    \begin{align*} x^{2}-y^{2} &= \left(k+1\right)^{2}-\left(k\right)^{2} \\ &= k^{2}+2k+1-k^{2} \\ &= 2k+1 \end{align*}

Since every odd integer has the form 2k+1 we have the odd integers covered.

Next let’s consider the integers that differ by 2.

Let x and y be consecutive integers such that x=k+2 and y=k where k \in \mathbb{Z}.

    \begin{align*} x^{2}-y^{2} &= \left(k+2\right)^{2}-\left(k\right)^{2}\\ &= k^{2}+4k+4-k^{2}\\ &= 4k+4\\ &= 4\left(k+1\right) \end{align*}

Now we have all integers that are multiples of 4.

This is a sufficient condition once we realize that every even integer has the form 2k and if we cube them we have (2k)^{3} = 8k^{3} which always yields a multiple of 4.

The Proof

We’ve essentially got our proof now, and I’ve taken what’s above and tucked it away neatly in this pdf for your convenience.

Conclusion

I hope that by the end of this you’ve gained some insight into some of the logical thinking that’s used to put together proofs. First you start by considering the basic assumptions the proof provides you with. Next you put those assumptions to work by playing with heuristic or experimental cases within the proofs assumptions. That part might take a while, but eventually you’ll hopefully gain some insight into the structure of the problem. Once that insight is gained you can begin to generalize your proof using mathematical constructs, and ultimately type up your final proof.


Sources

[1] A Friendly Mathematics Competition, Rick Gillman, Editor