Is n a Perfect Square if No Prime Less Than Its Square Root Divides It?

[cragar]

Homework Statement

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]

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.

 

[HallsofIvy]

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.

 

[cragar]

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 .

 

[Dick]

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 .

Can you show that if xy=n then either x<sqrt(n) or y<sqrt(n)? Hint: use a proof by contradiction.

 

[cragar]

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 can't happen so x=y.

 

[Dick]

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)?

 

[cragar]

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 can't be less than sqrt(n). and if y was bigger than sqrt(n) then xy would not eqaul n therefore x=y.

 

[Dick]

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 can't be less than sqrt(n). and if y was bigger than sqrt(n) then xy would not eqaul n therefore x=y.

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 can't 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.