Hard Made Easy

The following are examples of transforming hard problems into simpler problems.

Problem 1: If $A$ and $B$ are integers with $A \leq B$, how many integers $x$ satisfy $A \leq x \leq B$?

The possible integers are $A, A+1, A+2, \ldots, B$. But how many are there? To solve this, we consider the following simpler problem.

Problem 2: If $C$ is an integer greater than 1, how many integers $y$ satisfy $1 \leq y \leq C$?

The set of integers satisfying $1 \leq y \leq C$ is $\{ 1, 2, 3, \ldots C \}$, so there are $C$ such integers.

Now, to go from Problem 1 to Problem 2, we use the change of variables $x-A+1 = y$. Then

$A-A+1 \leq x-A+1 \leq B-A+1, \mbox { or } 1 \leq y \leq B-A+1.$

By Problem 2, there are $B-A+1$ possible values for $y$, hence there are $B-A+1$ possible values for $x= y+A-1$.

We now show how to transform questions over the rationals to questions over the integers.

Problem 3: If $x$ and $y$ are rational numbers that are not squares of other rational numbers, show that $\sqrt{x} + \sqrt{y}$ is not rational.

This may seem difficult to approach. Instead, consider the following simpler problem:

Problem 4: If $x$ and $y$ are integers that are not squares of other integers, show that $\sqrt{x} + \sqrt{y}$ is not an integer.

We can further simplify the problem:

Problem 5: If $x$ is an integer that is not the square of another integer, show that $\sqrt{x}$ is not an integer.

Now, this is a straightforward problem. The proof of Problem 5 is by contradiction: If $\sqrt{x}$ is equal to integer $n$, then $x=n^2$, implying $x$ is the square of an integer, a contradiction. $_\square$

Now, consider a generalized version of Problem 5.

Generalized Problem 5. If $x$ is a rational number that is not the square of another rational number, show that $\sqrt{x}$ is not a rational number.

Proof of Generalized Problem 5: If $\sqrt{x} = \frac{n}{m}$, then $x=\frac{n^2}{m^2}$, implying $x$ is the square of rational number $\frac{n}{m}$ .$_\square$

We then obtain the following corollary.

Corollary: If $y$ is an integer such that $\sqrt{y}$ is rational, then $y$ must be the square of an integer.

Proof: From Problem 5, $y$ is the square of a rational number $\frac {p}{q}$ with $\gcd(p,q)=1$. Hence $y = \frac {p^2} {q^2}$. Since $y$ is an integer, we have $q=1$, implying $y=p^2$. $_\square$

Now, back to Problem 4.

Proof of Problem 4:

Suppose $\sqrt{x} + \sqrt{y} = n$ is an integer. Consider $\sqrt{x} = n - \sqrt{y}$. Squaring both sides, we obtain $x = n^2 - 2n\sqrt{y} + y$, implying $\sqrt{y} = \frac {n^2 - x - y}{2n}$ is rational. By the corollary above, $y$ must be a square. Similarly, $x$ must be an square, a contradiction.$_\square$

Finally, we prove Problem 3.

Proof of Problem 3:

Suppose $x = \frac {p_x} {q_x}$ and $y = \frac {p_y} {q_y}$ satisfy $\sqrt{x} + \sqrt{y} = \frac {p_z} {q_z}$, where $p_x, p_y, p_z, q_x, q_y, q_z$ are all integers. Then

$\sqrt{ q_y ^2 q_z ^2 p_x q_x} + \sqrt{q_x ^2 q_z ^2 p_y q_y} = q_x q_y p_z.$

This is a contradiction to Problem 4. $_\square$

Corollary: If $x$ and $y$ are rational numbers such that $\sqrt{x} + \sqrt{y}$ is rational, then $\sqrt{x}$ and $\sqrt{y}$ are both rational.

The slightly surprising result is that in simplifying Problem 3 to Problem 4, we ended up using Problem 4 to prove Problem 3. In fact, as is often the case with rational numbers, it is sufficient to consider the integer case and then clear denominators by multiplication.