Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Two Discrete Mathematic Proofs I Need Help With

  1. Sep 9, 2010 #1
    1. The problem statement, all variables and given/known data
    Prove that at least one of 2*10500 + 15 or 2*10500 + 16 is not a perfect square. Can you say specifically which one is not a perfect square?

    Consider the proof that √2 is irrational. Could you repeat the same proof for √3? What about √4?

    2. Relevant equations

    3. The attempt at a solution
    For the first problem I have no clue where to start. I'm thinking it has something to do with the +15 and +16 at the end, but I'm not 100% sure on that.

    For the second one I know that you can prove that the √n is irrational for all integers that are not a perfect square, I'm just not sure how to prove it. Would it be similar to the proof of the √2 being irrational, just tweaked a bit because of the variable n?

    √n = p / q (where p / q is expressed in its lowest terms)
    n = p2 / q2
    n * q2 = p2
    and this is where I get stumped :(
  2. jcsd
  3. Sep 9, 2010 #2
    So I think I figured out the first problem. You can prove that one of them is in fact not a perfect square because the only two perfect squares that differ by 1 are the numbers 1 and 0. Right?
  4. Sep 9, 2010 #3


    User Avatar
    Gold Member

    Hopefully you can prove that at least one of them is not a perfect square. To show which one is definitely not a perfect square, note that

    2*10500+15 = 20*10499+15 = 5[4*10499+3]

    And see if you can make something work with that.

    For the second problem, try starting with 3 before considering n. To prove the case for n you're going to want to use the fundamental theorem of arithmetic.
    Last edited: Sep 9, 2010
  5. Sep 9, 2010 #4


    User Avatar
    Science Advisor
    Homework Helper

    Right. To figure out which one is definitely not a perfect square, you might want to figure out what they are mod 4. For the second one you should review the proof sqrt(2) is irrational and see if it extends.
  6. Sep 10, 2010 #5
    I think I may have figured it out, but I am so sleep deprived at this point I'm not positive I didn't mess up algebra at some point.

    Assume [tex]\sqrt{n}[/tex] is rational
    [tex]\sqrt{n}[/tex] = p / q
    n = p2 / q2
    q2n = p2
    so p is a multiple of n
    so we can say p = an

    Therefore: p2 = a2 n2

    q2n = a2 n2
    q2 = (a2n2)/n
    q2 = n(a2)
    from this q is a multiple of n
    but if they were both multiple’s of n, that contradicts our original assumption that p/q was in its lowest terms
  7. Sep 10, 2010 #6


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    So the square root of 4 is not rational?
  8. Sep 10, 2010 #7


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Can you tell me why each step should be valid?
  9. Sep 10, 2010 #8
    sorry, I should have included for any integer n, [tex]\sqrt{n}[/tex] is irrational if and only if n is not a perfect square.

    As for validating each step:
    Assume [tex]\sqrt{n}[/tex] is rational
    [tex]\sqrt{n}[/tex] = p / q <--Definition of an integer
    n = p2 / q2 <--Squaring both sides
    q2n = p2 <--Multiplying both sides by q2
    so p is a multiple of n <--I believe p2 must be divisible by n, and thus so must p
    so we can say p = an <--defining a new variable for p in terms of n
    Therefore: p2 = a2 n2 <--Calculating p2

    q2n = a2 n2 <--Replacing p2in the equation
    q2 = (a2n2)/n <--dividing both sides by n
    q2 = n(a2) <-- the end result, where I believe q2 must now be divisible by n, and thus q is aw well
  10. Sep 10, 2010 #9


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You never use the hypothesis "n is not a perfect square" in the argument that follows -- so if it's valid, it will prove that sqrt(4) is irrational.

    So, this gives you something you can do yourself without relying on others to point out your mistakes -- check each rationale and see which one doesn't work if n happens to be a perfect square.

    How would you rank your confidence in the validity of each step?
  11. Sep 10, 2010 #10
    I'm fairly confident in most of my steps. The only one I'm unsure of is:

    I believe there is a theorem where if x2 is divisible by n then x is divisible by n
  12. Sep 10, 2010 #11


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Not coincidentally, that's the step that fails for n=4. :smile: (Well, and the similar step for q)

    You are remembering a theorem, but you have only remembered part of it.
  13. Sep 10, 2010 #12
    I'm going to have to find this theorem, i can't remember the rest for the life of me. However I think a little sleep would help clear my head out, so I will be back to work on this in a few hours. I greatly appreciate you steering me in the right direction!
  14. Sep 10, 2010 #13
    Yay sleep, i believe this proof will get me to the correct answer.

    The part of the theorem I forgot last night was that if x is prime and x | n2 then x | n

    By the way the theorem was euclid's first theorem(euclid's lemma), of which i use a corollary of in this proof.

    The corollary is: If a and c are relatively prime, then c|ab implies c|b.

    Anyway, here's my proof now:

    Assume √(n) = a / b where a and b are relatively prime and b ≠ 1 (a non-integer rational number).

    n = a2 / b2
    nb2 = a2

    From this we can conclude that because a2 is an integer multiple of b2, b2 divides a2.
    For any two integers, if b2 divides a2 then b divides a.
    Logically, if the two numbers are relatively prime and b divides a, then b must be 1.
    However, this contradicts with our above statement that b ≠ 1.
    Therefore, √(n) cannot equal any rational non-integer rational number.

    Since the realm of real numbers contains only irrational, rational and integer numbers, and we have eliminated the non-integer rational numbers, the √(n) must therefore be either irrational or an integer. The only way √(n) will be an integer is if n is a perfect square.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook