# Uhh! help with this proof then x is prime .

1. Apr 21, 2012

### charmedbeauty

uhh! help with this proof """" then x is prime""".

1. The problem statement, all variables and given/known data

For a positive integer x≥2.

"if x is not divisible by any positive integer n satisfying 2≤n≤√x then x is a prime number"

a) show that the above statement is true .

b) Is the statement still true if the condition on n is replaced by 2≤n<√x ??

2. Relevant equations

3. The attempt at a solution

Well firstly I really have problems with proofs in general, but

x≥4

so x can be [4,5,6,7,.....∞)

so by definition of prime number x--> x/x and x/1

but I really dont know how to approach this
I know its true because n= [2,3,4,5...∞)
and so the only numbers not possibly divisible by n are primes, Since n can be any positive integer ≥2, and Since x≠1.

But how do I put it in mathematical terms??
HELP!

2. Apr 21, 2012

### Dick

Re: uhh! help with this proof """" then x is prime""".

Try and prove the contrapositive. If x is NOT prime then there IS a positive integer satisfying 2≤n≤√x that divides x.

3. Apr 21, 2012

### D H

Staff Emeritus
Re: uhh! help with this proof """" then x is prime""".

An integer x>1 is composite if there exists some number 1<n<x that divides n. The integer x is prime if not such number n exists. What this is this theorem is telling you is that you don't have to look at all integers between 2 and x-1 (inclusive). You only need to look at those between 2 and √x (inclusive).

Hint: Suppose n is an integer that divides x. In other words, m=x/n is an integer. What can you say about m if √xn<x?

4. Apr 21, 2012

### charmedbeauty

Re: uhh! help with this proof """" then x is prime""".

Well mn=x so x is not a prime if this condition is satisfied.

and m can be any positive integer >1 since m=x/n which is greater than 1 since n<x, and n,x are positive integers.

But I dont really understand when exactly this condition satisfies, namely, mn=x, Since to me mn could be less than, equal, or greater than x.

Since m>1 and n<x. There are values of x,m,n that satisfy all three conditions ie, <,=,>.

5. Apr 21, 2012

### charmedbeauty

Re: uhh! help with this proof """" then x is prime""".

On second thoughts m>x so since n≥2 then mn>x.

So I think this tells me that if x does not divide some n≥2 then x is not prime?? Although I think for this to be true I need the eqn to be mn=x? Im confused.

6. Apr 21, 2012

### HallsofIvy

Staff Emeritus
Re: uhh! help with this proof """" then x is prime""".

Surely this is not what you meant to say? Any x, prime or not, divides 2x, for example.

It is true that if x is not divisible by some $n\ge 2$ (except x itself) then x is prime.

If x= mn and $m>\sqrt{x}$, what can you say about n?

As for "b) Is the statement still true if the condition on n is replaced by 2≤n<√x ??",
consider x= 9.

7. Apr 21, 2012

### charmedbeauty

Re: uhh! help with this proof """" then x is prime""".

if x=mn and m>√x

then all I can say from this statement is that mn is > √x. And that n is <√x, Since mn=x. I'm still really lost?

Last edited: Apr 21, 2012
8. Apr 21, 2012

### Office_Shredder

Staff Emeritus
Re: uhh! help with this proof """" then x is prime""".

If x is composite, we can factor it as x=mn we have two possibilities
1) m< √x
2) n< √x

In both cases, we see that if x is composite, it is divisible by a number which is no larger than √x, which is exactly what you wanted to prove (after you change some strict inequalities to weak inequalities)

9. Apr 22, 2012

### charmedbeauty

Re: uhh! help with this proof """" then x is prime""".

Ok thanks Office Shredder and others that helped...

so does this proof look correct now.

given ---> 2≤n≤√x and x≥2

So n≥2 from above inequality.

Suppose x is not prime, then, by definition of a prime

m = x/n for some integers m and x,n both≥2

hence, x=mn

Now either n< √x or m<√x or m=√x iff n=√x

In either case x/m or x/n

But if x is prime, by definition, x cannot divide m or n where m,n≥2

Hence m is prime iff x does not divide n where 2≤n≤√x

proof finished.

and for part b)

let x=9

therefore, 2≤n<3

Now x is prime iff x does not divide n for some integer n satisfying above inequality.

but 9 does not divide 2 and when x =9, n must =2 (satisfying the above inequality).

Hence x is prime. Contradiction. 9 is not prime. Therefore above inequality does not hold.

Last edited: Apr 22, 2012
10. Apr 22, 2012

### HallsofIvy

Staff Emeritus
Re: uhh! help with this proof """" then x is prime""".

I have no idea what you are trying to do. All you need to note is that 9 is not prime and $\sqrt{9}=3$. "$2\le x< \sqrt{9}= 3$" is true only for x= 2 and 2 does not divide 9. End of counter example.

11. Apr 22, 2012

### charmedbeauty

Re: uhh! help with this proof """" then x is prime""".

Ok thanks, undestood!