1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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
    Staff Emeritus
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proof about integers.
  1. Proof about integers (Replies: 4)

Loading...