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
4 years ago

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 \( 2 \times 3 \)
2^{34} \( 2^{34} \)
a_{i-1} \( a_{i-1} \)
\frac{2}{3} \( \frac{2}{3} \)
\sqrt{2} \( \sqrt{2} \)
\sum_{i=1}^3 \( \sum_{i=1}^3 \)
\sin \theta \( \sin \theta \)
\boxed{123} \( \boxed{123} \)

Comments

There are no comments in this discussion.

×

Problem Loading...

Note Loading...

Set Loading...