# Homework Help: Proof about integers.

1. Jun 24, 2011

### cragar

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 $\sqrt{n}$ is a factor of n, then there is an integer m such that $n=m^2$
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
$\sqrt{xy} = \sqrt{n}$
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. Jun 24, 2011

### HallsofIvy

You got the basic idea but you need to specify that one of $\sqrt{x}$ and $\sqrt{y}$ must be less than or equal to $\sqrt{n}$. It's not difficult to show that but you should make it explicit.

3. Jun 24, 2011

### cragar

Could I just say that if $\sqrt{x}$ was eqaul to $\sqrt{n}$
then y would be one , or they are both less than root n because their product produces root n .

4. Jun 24, 2011

### Dick

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

5. Jun 25, 2011

### 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 cant happen so x=y.

6. Jun 25, 2011

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

7. Jun 25, 2011

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

8. Jun 25, 2011

### Dick

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.