Waste less time on Facebook — follow Brilliant.

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.

Note by Calvin Lin
3 years, 7 months ago

No vote yet
1 vote


There are no comments in this discussion.


Problem Loading...

Note Loading...

Set Loading...