For any positive integer n, √(n) is either irrational or integral. The proof of this is fairly simple, but it's a good example of an elementary proof by contradiction.

Proof: Assume √(n) = a/b, where a and b are relatively prime and b ≠ 1. (In other words, assume √(n) is a nonintegral rational number.) From here, square both sides to achieve n = a2/b2. Then multiply both sides by b2 to get a2 = nb2. From this we can conclude that, because a2 is an integer multiple of b2, b2 | a2 (b2 divides a2).

Now we must get a little sidetracked and go on an exploration of elementary number theory. It so happens to be true that, for any integers m and n, m2 | n2 implies that m | n. The proof of this is rather more complex than can be gotten into now -- perhaps that's a node for another day. Another fact that we'll soon need to use is that, if m | n and m and n are relatively prime, m equals one.

Anyway, back to our proof. Since we have concluded that b2 | a2, we also know that b | a. Since we also know that a and b are relatively prime, we can conlude that b = 1. However, above we assumed that b ≠ 1 in order to make a/b nonintegral; thus, we have reached a contradiction and have proven that √(n) cannot possibly equal any rational nonintegral number. Since all real numbers are irrational, rational, or integral, this leaves the irrationals and the integers. (Yes, the integers are technically a subset of the rationals, so saying that a number is a "rational or an integer" is like saying a shape is a "rectangle or a square"; but for the purposes of this proof we had to differentiate.)

Thus, the square root of any positive integer is either an integer or an irrational number. QED.

More proofs---
1. A direct proof. Suppose the square root of a positive integer z is a rational x / y in lowest terms. Then xx = yyz which implies y divides xx. By a corollary of Euclid's First Theorem it follows that y divides x. The root x / y is therefore an integer.
2. A proof by contradiction. Assume that x/y is a non-integer rational in lowest terms. Define z := (x/y)², and q := floor (x/y). Then:
```    x/y - 1 <   q    < x/y
x - y <   yq   < x
-y < yq - x < 0
y > x - yq > 0

x/y = x(x - yq) / y(x-yq)
x/y = (xx -yqx) / y(x-yq)
x/y = (yyz-yqx) / y(x-yq)
x/y = (yz - qx) / (x-yq)
```
An equivalent fraction with a denominator lower than y has been found. Contradiction: x/y is not in lowest terms.
3. As a special case of the Rational Root Theorem (a.k.a. Rational Zeros Theorem).
Last update: June 22, 2005

Log in or register to write something here or to contact authors.