Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. 31 Oct '07 13:21 / 2 edits
    n is a positive integer. Here is a proof that sqrt(n) can't be a non-integer rational number:
    Assume this is not the case. Then there is a minimal positive integer k such that k*sqrt(n) is an integer. But k*sqrt(n)-k*floor(sqrt(n)) is a smaller positive integer having the same property.

    My question: can you write a SIMILAR proof, that will show that for all positive integers m and n, the mth root of n can't be a non-integer rational? It is easy to prove this theorem if we are allowed to use the fundamental theorem of arithmetic (=every integer has a unique prime factorization). But I want a proof similar to the proof I gave for square roots.

    Thanx
  2. Standard member TheMaster37
    Kupikupopo!
    31 Oct '07 15:01 / 1 edit
    Originally posted by David113
    But k*sqrt(n)-k*floor(sqrt(n)) is a smaller positive integer having the same property.
    What property do you mean?
  3. 31 Oct '07 18:28
    Originally posted by TheMaster37
    What property do you mean?
    The property of being an integer when multiplied by sqrt(n).
  4. 31 Oct '07 20:56
    Originally posted by David113
    The property of being an integer when multiplied by sqrt(n).
    But that's not a contradiction, as k*sqrt(n)-k*floor(sqrt(n)) is not a multiple of sqrt(n).

    You haven't used any property of sqrt(n) in your proof.
  5. 01 Nov '07 10:42 / 1 edit
    Originally posted by mtthw
    But that's not a contradiction, as k*sqrt(n)-k*floor(sqrt(n)) is not a multiple of sqrt(n).

    You haven't used any property of sqrt(n) in your proof.
    Why does k*sqrt(n)-k*floor(sqrt(n)) need to be a multiple of sqrt(n)?

    Of course it is a contradiction:

    k*sqrt(n)-k*floor(sqrt(n)) is a positive integer, since k*sqrt(n) and k*floor(sqrt(n)) are integers and k*floor(sqrt(n)) < k*sqrt(n).

    It is smaller than k, since sqrt(n)-floor(sqrt(n)) < 1.

    When multiplied by sqrt(n), the result is an integer:
    [k*sqrt(n)-k*floor(sqrt(n))]sqrt(n)=kn-(k*sqrt(n))(floor(sqrt(n)))=difference between two integers=integer.

    But k was supposed to be the SMALLEST positive integer that gives an integer when multiplied by sqrt(n).

    Contradiction...

    Now I ask if this proof can be generalized to roots other than the square root.
  6. 01 Nov '07 11:09
    Originally posted by David113
    Of course it is a contradiction:

    ...(snip)...
    Now that's more like it. I think the steps you assumed (and have now provided) are the key parts of the proof. Certainly makes it a lot clearer!
  7. 01 Nov '07 13:17
    Originally posted by David113
    Why does k*sqrt(n)-k*floor(sqrt(n)) need to be a multiple of sqrt(n)?
    Incidentally, this was my misunderstanding. I thought you meant that k*sqrt(n)-k*floor(sqrt(n)) had the same property as k*sqrt(n), not the same property as k. Sorry!