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: Proof about integers.

  1. Jun 24, 2011 #1
    1. The problem statement, all variables and given/known data
    Prove: If n is a composite integer larger than 1 and if no prime number less than [itex] \sqrt{n} [/itex] is a factor of n, then there is an integer m such that [itex] n=m^2 [/itex]
    3. The attempt at a solution
    Proof: Let n be a positive composite integer larger than 1. If n is composite then there exists an integer y such that y|n where y is larger than 1 but smaller than n . And if y divides n then there exists an integer x such yx=n . Now we take the square root of both sides to obtain
    [itex] \sqrt{xy} = \sqrt{n} [/itex]
    If there are no prime factors less than the square root of n that are a factor of n then the square root of n is prime. The only way the square root of n could be prime is if x=y .
    if x did not equal y then the square root of n would not be an integer. Because the only factors of prime numbers are 1 and them selves. the product of 2 different prime numbers would not be a square.
     
  2. jcsd
  3. Jun 24, 2011 #2

    HallsofIvy

    User Avatar
    Science Advisor

    You got the basic idea but you need to specify that one of [itex]\sqrt{x}[/itex] and [itex]\sqrt{y}[/itex] must be less than or equal to [itex]\sqrt{n}[/itex]. It's not difficult to show that but you should make it explicit.
     
  4. Jun 24, 2011 #3
    Could I just say that if [itex] \sqrt{x} [/itex] was eqaul to [itex] \sqrt{n} [/itex]
    then y would be one , or they are both less than root n because their product produces root n .
     
  5. Jun 24, 2011 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Can you show that if xy=n then either x<sqrt(n) or y<sqrt(n)? Hint: use a proof by contradiction.
     
  6. Jun 25, 2011 #5
    suppose x and y are bigger than sqrt(n) .
    then we would have 2 numbers bigger than sqrt(n) being multiplied together and this would be bigger than n.
    then xy would not equal n and this is a contradiction .
    therefore x or y is less than or equal to sqrt(n) .
    but if x does not equal y and x and y are integers larger than 1 there would exist prime factors less than sqrt(n) and by definition this cant happen so x=y.
     
  7. Jun 25, 2011 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    You've proved that if xy=n then either x or y is less than sqrt(n), but you didn't use it in your proof. Suppose x<=sqrt(n). If x=sqrt(n) then n is a square, right? So now suppose x<sqrt(n). Why does that show there is a prime factor of n less than sqrt(n)?
     
  8. Jun 25, 2011 #7
    thanks for your help by the way.
    suppose x<sqrt(n) this would mean that there is a prime factor less sqrt(n) that was also a factor of n, because either x is prime or composite, and if x is composite it is factorisable and then it would have prime factors less than sqrt(n). And because x if a factor of n, then by definition x cant be less than sqrt(n). and if y was bigger than sqrt(n) then xy would not eqaul n therefore x=y.
     
  9. Jun 25, 2011 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I know you've got the idea, but you just so sloppy with words. Not a good idea in a proof. My problems start here: "And because x if a factor of n, then by definition x cant be less than sqrt(n). and if y was bigger than sqrt(n) then xy would not eqaul n therefore x=y." Can you fix up the end of the proof? x isn't by DEFINITION less than n. It's not less than n by your previous arguments.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook