Monday, February 20, 2012

of roots and irrationals

I read a likable proof on Wikipedia about why the roots of an integer must either be an integer or irrational (I'm purposely excluding the complex roots from discussion). Unlike Wikipedia, I'm going to walk through it at an excruciatingly slow pace.
  1. 1) An integer root of a number x is relatively easy to find because the number of integers in a range is limited and powers preserve inequality. Raise an integer to the power. If it's greater than x, then raise a lesser integer. If it's lesser than x, then raise a greater integer. The range of possible integers steadily decreases until the integer root is either found or proven to not exist.
  2. 2) If no integer root exists, then for the sake of argument assume a rational root. Since this hypothetical rational root isn't equal to any integer (those were disqualified as roots after #1), its unique form is an irreducible fraction p divided by q. The fraction p/q would be reducible if p and q had any factors in common. In that case, dividing both p and q by all of those common factors would yield the desired irreducible fraction (or just an integer). Hence, in the final irreducible fraction, by definition p and q have no factors in common.
  3. 3) Raising the alleged rational root p/q to the power is equivalent to raising p and raising q, then dividing the p result by the q result. This is a straightforward application of the facts that the divisions can be rewritten as multiplication by the reciprocal, and then the multiplications can be reordered.
  4. 4) Raising p to a power means multiplying p by p one or more times. So all the same factors of p will be present afterward, but duplicated. To multiply by p is to multiply by all of p's factors. No "new" factors are introduced by raising to a power. Or rather, "Meet the new factors, same as the old factors."
  5. 5) #2 mentioned that p and q had no common factors. But #3 and #4 have shown that raising p/q to the power doesn't help. There wasn't any overlap in factors before, so duplicating the same two disagreeable sets of factors won't yield any overlap either. No matter what power of the irreducible fraction p/q, p and q will continue to have nothing in common.
  6. 6) In order for a fraction to simplify to an integer, the denominator q itself must be a factor of the numerator p. Yet #5 concluded that no powers of an irreducible fraction p/q will produce a fraction with any factors in common between p and q. Therefore no powers of an irreducible fraction can produce an integer. In contradiction with the assumption of #2, p/q cannot be a root of an integer.
  7. 7) Since all non-integer rational numbers must be irreducible fractions, #6 implies that the only possible rational roots can be integers. Integers without integers as roots must have ir-rational roots!
1An efficient way to factor large p or q is left as an exercise to the reader.